Архив содержит все лекции ОПК 2016-го года и две лекции с прошлосеместрового ОП.

1. Что такое хорошая программа (хороший проект)?
2. Основные принципы отладки программ.
3. Хорошие и плохие интерфейсы (модулей и программ).
4. Тестирование и документирование.
5. Краткое содержание курса.
6. Формальности про экзамен.

1. Спектр задач, в которых появляется трансляция.
2. Виды анализа: лексический, синтаксический, семантический.
3. Лексические анализаторы (сканеры).
4. Интерфейс сканера.
5. Ручная реализация сканера для вычисления арифметических выражений.
6. Недетерминированные конечные автоматы (НКА).
7. Регулярные выражения.
8. Трансформация регулярных выражений в НКА.
9. Понятие порождающей грамматики.
10. Пример грамматики для скобочных выражений.
11. Контекстно-свободные грамматики и деревья разбора.
12. Построение грамматики для разбора арифметических выражений.
13. Отражение приоритетов операций в грамматике выражений.
14. Метод рекурсивного спуска.
15. Реализация разбора арифметических выражений с помощью рекурсивного спуска, обработка ошибок.

1. Библиотека console_graphics.
2. Пример использования SDL.
3. Зачем сжимать информацию?
4. Сжатие с потерями и без потерь.
5. Алгоритм RLE.
6. Алгоритм Хаффмана: построение кодового дерева, упаковка и распаковка.
7. Алгоритм LZ77 (скользящее окно).
8. Алгоритм LZW.
9. Исключительный случай при распаковке LZW.
10. Сжатие с потерями и функциональный анализ.

1. Общий принцип работы хеш-таблицы.
2. Требования к хеш-функции.
3. Интерфейс хеш-таблицы.
4. Размещение в массиве: метод деления, метод умножения.
5. Тривиальные хеш-функции.
6. Хеш-функции Дженкинса и Фаулера-Нолла-Во.
7. Хеш-функция для набора элементов.
8. Конфликты и способы их разрешения.
9. Списки коллизий.
10. Открытая адресация: линейное, квадратичное исследование, двойное хеширование.
11. Кукушиное хеширование (cuckoo hash).
12. Хеш vs. дерево.
13. Криптографические хеш-функции.
14. Контрольные суммы.
15. Принцип адресации по содержимому.
16. Фильтр Блума.
17. Генерация хеш-функций для фильтра Блума.

1. 2-3-4 деревья.
2. Красно-черные деревья (red-black trees).
3. Слоеные списки.
4. Префиксные деревья.
5. Очередь с приоритетом и двоичная куча («пирамида»).

1. Структура данных дерево.
2. Представление деревьев в C.
3. Двоичные деревья.
4. Обходы двоичных деревьев, связь обходов с древовидным представлением арифметических выражений.
5. Преобразование произвольного дерева в двоичное.
6. Интерфейс и применение деревьев поиска.
7. Высота дерева поиска.
8. Удаление элемента.
9. Оптимальные деревья поиска.
10. Выворачивание (splay trees).
11. АВЛ-деревья.

• Тонкости считывания чисел с консоли
• Работа с файлами
• Работа с аргументами командной строки
• Использование кода возврата

Код:

• Устойчивый ввод
• Копирование файлов

1. Записи
2. Массивы.
3. Адресация в многомерных массивах: C-style, FORTRAN-style, Java-style.
4. Данные как «белый ящик» и как «черный ящик».
5. Стеки, очереди и их применение в различных задачах.
6. Реализация стека с помощью динамического массива.
7. Связные списки: структура и свойства.
8. Операции над списками.
9. Двусвязные списки, кольцевые списки, двусвязные кольцевые списки.
10. Отличия абстрактных типов данных от структур данных.

1. Поиск подстроки в строке — метод грубой силы и идеи его ускорения.
2. Алгоритм Боуэра-Мура.
3. Алгоритм Рабина-Карпа.
4. Программирование как борьба со сложностью.
5. Программа как один большой черный ящик.
6. Декомпозиция на модули.
7. Пример модульной структуры: скачивалка изображений.
8. На что указывает граф связей между модулями?
9. Модуль = Интерфейс + Реализация.
10. Устройство модулей в C: заголовочный файл, исходный файл, использование модуля.
11. Стандартная библиотека C как набор модулей.
12. Почему интерфейс важнее реализации?
13. Операционная система как интерфейс.
14. Признаки хорошего интерфейса.