Материалы лекций 2013 года.
- Вводная лекция. Цели и задачи курса. Характеристика разделов курса – введение в алгоритмы, язык программирования, структуры данных. Алгоритмы. Формализация понятия алгоритма. Машина Тьюринга. Примеры МТ. [PDF]
- Диаграммы Тьюринга. Построение языка описания МТ. Композиция алгоритмов. Универсальная МТ. [PDF]
- Универсальная МТ (окончание). Проблемы останова и самоприменимости. Нормальные алгоритмы Маркова. Примеры других алгоритмических систем. Основная гипотеза теории алгоритмов. Тезис Тьюринга-Черча. [PDF]
- Общая классификация и характеристики языков программирования. Место языка Си в современной индустрии ПО. Стандарты и роль стандартизации. Язык программирования Си. Описание Си-машины: процессор, классы памяти (регистровые, автоматические и статические переменные, глобальные переменные), структура программного файла. Системные библиотеки и их использование. [PDF]
- Типы данных языка Си: целые, логические, символьные, с плавающей точкой, беззнаковые целые. Арифметические и логические выражения. Старшинство операций. Операции присваивания. [PDF]
- Форматный ввод-вывод. Приведение типов при вычислении выражений (явное и неявное). Операторы. [PDF]
- Обработка символьных данных. Массивы. Многомерные массивы. Строки. Обработка строк. Системная библиотека работы со строками. [PDF]
- Указатели. Адресная арифметика. Массивы и указатели. Оператор sizeof и его тип. Функции. Определение и объявление функции. Передача параметров. [PDF]
- Рекурсия. Хвостовая рекурсия. Представление данных с плавающей точкой. [PDF]
- Вычисление сумм и произведений данных с плавающей точкой. Потеря точности при вычитании. Выбор правильной последовательности вычислений. Побитовая обработка данных. Беззнаковые целые типы. Абстрактный тип данных «множество» и его реализация. Структуры. Указатели на структуры. [PDF]
- Объединения. Анонимные структуры и объединения. Битовые поля. Перечисления. [PDF]
- Динамическое выделение и освобождение памяти. VLA-массивы и их выделение в динамической памяти. Массив переменного размера в составе структуры. Схема компиляции программ на языке Си. Препроцессор. Директивы препроцессора. [PDF]
- Директивы препроцессора (окончание). Компоновка. Классы памяти и компоновки. Отладка программ. Понятие об отладчике gdb. Организация типа данных «стек» на динамической памяти. [PDF]
- Использование стека для построения обратной польской записи. Очередь. Списки. Алгоритмы работы со списками: вставка элемента в начало и конец списка. [PDF]
- Алгоритмы работы со списками: поиск и удаление элемента. Алгоритм топологической сортировки Вирта. [PDF]
- Понятие о сложности алгоритмов. Простейшие алгоритмы сортировки. Оценка сложности алгоритмов сортировки. Быстрая сортировка. [PDF]
- Поиск подстроки по образцу. Простейший алгоритм. Алгоритм Кнута – Морриса – Пратта (КМП). Префикс-функция и ее вычисление. Сложность вычисления префикс-функции и алгоритма КМП. [PDF]
- Двоичные деревья. Обход двоичного дерева (сначала в глубину, сначала в ширину). Нерекурсивный обход двоичного дерева. «Прошитое» двоичное дерево и его обход. [PDF]
- Двоичные деревья поиска и операции над ними (поиск элемента, минимальный и максимальный элементы, следующий элемент, вставка и удаление элемента). Деревья Фибоначчи. Оценка высоты дерева Фибоначчи. [PDF]
- АВЛ-деревья. Базовые операции над АВЛ-деревьями. Балансировка АВЛ-дерева. Вставка и удаление элемента в/из АВЛ-дерева. Оценка высоты АВЛ-дерева по дереву Фибоначчи. [PDF]
- Красно-черные деревья. Структура данных «куча» (heap) и сортировка heapsort (пирамидальная сортировка). [PDF]
- Хеш-таблицы. Хеширование. Хеширование цепочками. Хеширование с открытой адресацией. [PDF]
- Цифровой поиск. Задача цифрового поиска. Деревья цифрового поиска. Алгоритмы перебора множеств. Рекурсивный алгоритм генерации перестановок. Нерекурсивный алгоритм: генерация лексикографически следующей перестановки (алгоритм Нарайаны). [PDF]
- Самоперестраивающиеся деревья (splay trees). Операция splay (расширение). Реализация словарных операций через операцию splay. Реализация операции splay. Сложность словарных операций в splay-деревьях. [PDF]