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