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