19.12.2016. Все лекции 2016

Развернуть

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

28.11.2016. №13. Проекты, отладка, тестирование, документирование

Развернуть

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

21.11.2016. № 12. Трансляция

Развернуть

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

14.11.2016. № 11. Графические библиотеки, упаковка данных

Развернуть

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

07.11.2016. № 10. Хеш-таблицы

Развернуть

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

31.10.2016. № 9. Красно-черные деревья, очередь с приоритетом

Развернуть

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

24.10.2016. № 8. Деревья, бинарные деревья поиска, АВЛ-деревья

Развернуть

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

17.10.2016. № 7. Практика, взаимодействие с внешим миром

Развернуть

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

Код:

10.10.2016. № 6. Составные типы данных, стек, очередь, списки

Развернуть

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

03.10.2016. № 5. Алгоритмы поиска подстроки в строке, модули

Развернуть

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

Действия