Материалы лекций

Материалы лекций текущего семестра (осень 2016).

  1. Вводная лекция. Цели и задачи курса. Характеристика разделов курса. Алгоритмы. Формализация понятия алгоритма. Машина Тьюринга (МТ). (7 сентября, PDF).
  2. Нормальные МТ. Диаграммы Тьюринга: диаграммы элементарных МТ, правила композиции диаграмм, примеры диаграмм. Диаграммы Тьюринга: построение таблицы МТ по диаграмме. Моделирование МТ. Универсальная МТ. (10 сентября, PDF).
  3. Проблемы останова и самоприменимости. Нормальные алгоритмы Маркова. Примеры других алгоритмических систем. Тезис Тьюринга-Черча. Язык программирования Си. Место языка Си в современной индустрии ПО. Стандарты и роль стандартизации. (14 сентября, PDF).
  4. Первая программа на Си. Структура программного файла. Системные библиотеки и их использование. Описание Си-машины: процессор, классы памяти (регистровые, автоматические и статические переменные). Типы данных языка Си: целые, логические, символьные, с плавающей точкой, беззнаковые целые. Переменные: класс памяти, область действия. (21 сентября, PDF).
  5. Инициализация переменных. Арифметические и логические выражения. Ленивое вычисление логических выражений. Старшинство операций. Операции присваивания. Точки следования. Форматный ввод-вывод. Приведение типов при вычислении выражений (явное и неявное). (24 сентября, PDF).
  6. Операторы. Символьный тип и обработка символьных данных. Массивы. Многомерные массивы. (28 сентября, PDF).
  7. Инициализация массивов.  Строки. Обработка строк. Операция sizeof. (01 октября, PDF).
  8. Указатели. Адресная арифметика. Массивы и указатели. Преобразования типа указателей. Функции. Определение и объявление функции. Передача параметров. (05 октября, PDF).
  9. Рекурсия. Хвостовая рекурсия. Встраивание функций. Указатели на функцию.Побитовая обработка данных. Абстрактный тип данных «множество» и его реализация. (08 октября, PDF).
  10. Представление данных с плавающей точкой. Стандарт IEEE 754. Вычисление сумм и произведений данных с плавающей точкой. Потеря точности при вычитании. Выбор правильной последовательности вычислений. Опции компилятора gcc для вычислений с плавающей точкой (12 октября, PDF).
  11. Структуры. Указатели на структуры. Составные инициализаторы структур. Объединения. Анонимные объединения и структуры. Битовые поля. Перечисления. (15 октября, PDF).
  12. Динамическое выделение и освобождение памяти. VLA-массивы и их выделение в динамической памяти. Массив переменного размера в составе структуры. Инструменты поиска ошибок доступа к памяти: valgrind, address sanitizer. (19 октября, PDF).
  13. Схема компиляции программ на языке Си. Препроцессор. Директивы препроцессора. Компоновка. Классы памяти и компоновки. Отладка программ. Понятие об отладчике gdb. (22 октября, PDF).
  14. Организация типа данных «стек» на динамической памяти. Использование стека для построения обратной польской записи. Очередь. (26 октября, PDF).
  15. Списки. Добавление нового элемента в начало и в конец списка. Поиск элемента в списке. Удаление заданного элемента из списка: через возврат указателя на новый список, через передачу двойного указателя. Алгоритм топологической сортировки Вирта. (2 ноября, PDF).
  16. Понятие о сложности алгоритмов. Поиск подстроки по образцу. Простейший алгоритм. Алгоритм Кнута – Морриса – Пратта (КМП). Префикс-функция и ее вычисление. Сложность вычисления префикс-функции и алгоритма КМП. (9 ноября, PDF).
  17. Простейшие алгоритмы сортировки.  Оценка сложности алгоритмов сортировки. Быстрая сортировка. (12 ноября, PDF).
  18. Двоичные деревья. Обход двоичного дерева (сначала в глубину, сначала в ширину). Нерекурсивный симметричный обход двоичного дерева. «Прошитое» двоичное дерево и его обход. (16 ноября, PDF).
  19. Двоичные деревья поиска и операции над ними (поиск элемента, минимальный и максимальный элементы, следующий элемент, вставка и удаление элемента). Деревья Фибоначчи. Оценка высоты дерева Фибоначчи. (19 ноября, PDF).
  20. АВЛ-деревья. Базовые операции над АВЛ-деревьями. Балансировка АВЛ-дерева. Вставка и удаление элемента в/из АВЛ-дерева. Оценка высоты АВЛ-дерева по дереву Фибоначчи. Красно-черные деревья. Оценка высоты красно-черного дерева. Операции при вставке в красно-черное дерево. (23 ноября, PDF).
  21. Самоперестраивающиеся деревья (splay trees). Операция splay (перестраивание). Реализация словарных операций через операцию splay. Реализация операции splay. Сложность словарных операций в splay-деревьях. Обобщение сбалансированных деревьев поиска: ранговые деревья, понятие ранга и ранговой разницы. Ранговые правила для АВЛ-деревьев и красно-черных деревьев. Слабые АВЛ-деревья. Структура данных «куча» (heap) и сортировка heapsort (пирамидальная сортировка). Сложность пирамидальной сортировки (26 ноября, PDF).
  22. Хеш-таблицы. Хеширование. Хеширование цепочками. Хеширование с открытой адресацией. Сложность словарных операций для хеш-таблиц.  Методы построения хеш-функций: деление с остатком, умножение, линейная/квадратичная последовательность проб, двойное хеширование. (30 ноября, PDF).
  23. Цифровой поиск. Задача цифрового поиска. Деревья цифрового поиска. Вставка в дерево цифрового поиска. Алгоритмы перебора множеств. Рекурсивный алгоритм генерации перестановок. Нерекурсивный алгоритм: генерация лексикографически следующей перестановки (алгоритм Нарайаны). (7 декабря, PDF).

Leave a Reply