Высшая школа экономики

Лектор: Борисенко Владимир Витальевич

Материалы по курсу «Математические методы в программировании»
2012-13 уч. г.

• Программа курса.
• flex & bison для MS Windows.
• Описание Lex и Yacc.
• Примеры сканеров, реализованных при помощи LEX:
  • выделение имен и целых констант из входного потока;
  • удаление комментариев из C и C++ программ;
  • выделение имен, целых и вещественных констант из входного потока;
  • раскрашивание лексем в C/C++ программе;
  • сканер для калькулятора формул, реализованного с помощью YACC.
• LL(1)-разбор (рекурсивный разбор):
  • LL(1)-парсер для перевода формулы из прямой польской записи в обычную;
  • LL(1)-парсер для языка арифметических формул.
• LR(1)-разбор (восходящий разбор с помощью конечного автомата со стеком)
  • Калькулятор арифметических формул, реализованный с помощью системы Lex и YACC:
    • архив со всеми исходными файлами "YaccCalc.zip";
    • исходный текст сканера (файл "scan.l");
    • исходный текст парсера (файл "calc.y").
  • Парсер описаний переменных языка C, реализованный с помощью Lex и YACC:
    • архив со всеми исходными файлами "CTypes.zip";
    • исходный текст сканера (файл "scan.l");
    • исходный текст парсера (файл "ctypes.y").
  • Парсер логических выражений:
    • архив со всеми исходными файлами "LParser.zip";
    исходный текст сканера (файл "lscan.l");
    • исходный текст парсера;
    дерево логических выражений (файл "ltree.c").
  • Учебный компилятор, реализованный с помощью Lex и YACC.
    • Список задач по проекту "Учебный компилятор".
  • Примеры программ для лабораторных работ.
• 3D-графика с использованием библиотеки OpenGL и Qt
  • Простой пример: изображение тетраэдра со сферой. Файл Tetrahed.zip (проект для QtCreator'а).
  • Изображение икосаэдра. По нажатию клавиши "w" переключаются режимы рисования wireframe/faces, по нажатию "s" (split) каждая треугольная грань многогранника делится на 3 грани, в пределе получаем триангуляцию сферы; нажатие на "c" (colors) включает/выключает использование цветов. Файл Icosahed.zip (проект для QtCreator'а).
  • Простейший пример с анимацией при помощи классов QTimer и QTime: вращение луны вокруг земли. Файл Moon.zip (проект для QtCreator'а).
  • Список задач по теме OpenGL.

Материалы по курсу «Алгоритмы и структуры данных»
(«Практикум на ЭВМ») 2011-12 уч. г.

• Программа курса.
  Программа прошлого года (2010-11) в виде doc-файла.
• Задачи для решения на компьютере.
• Учебные проекты.
• Программа экзамена 2011-12 уч. года.
• Экзаменационные задачи (типичные примеры).
• Билеты экзамена 2010-2011 уч. года.

Некоторые лекции

• Основы языка C++. Понятие класса. Правильное написание прототипов методов класса, переопределение операторов. Реализация простых классов, представляющих математические объекты (вектор на плоскости, точка, матрица и т.п.).
• Сравнение традиционных языков программирования (C, C++) и объектно-ориентированных в узком смысле (Java, C#, Visual Basic) по методам организации памяти и размещения объектов в ней (понятия контролируемой динамической памяти, объектные ссылки и handl'ы объектов, сборка мусора).
• Проект "Текстовый редактор" (вариант для X-Window и операционной системы Unix).
• Деревья поиска, реализация множества и нагруженного множества (map) на их основе. Почти сбалансированные деревья, AVL и красно-черные деревья. Алгоритм восстановления балансировки красно-черного дерева при добавлении элемента.

Темы курсовых и дипломных работ