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