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