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

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

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

Leave a Reply