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

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

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

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

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. Префиксные деревья (trie).
4. Слоеные списки (skip list).

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. Отличия абстрактных типов данных от структур данных.
11. Очередь с приоритетом.

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

1. Поиск подстроки в строке — метод грубой силы и идеи его ускорения.
2. Алгоритм Боуэра-Мура.
3. Алгоритм Рабина-Карпа.