Материалы лекций

Материалы лекций текущего семестра (осень 2017).

  1. Вводная лекция. Цели и задачи курса. Характеристика разделов курса. Алгоритмы. Формализация понятия алгоритма. Машина Тьюринга (МТ). (6 сентября, PDF).
  2. Нормальные МТ. Диаграммы Тьюринга: диаграммы элементарных МТ, правила композиции диаграмм, примеры диаграмм, построение таблицы МТ по диаграмме. Моделирование МТ. Универсальная МТ. Построение универсальной МТ. (9 сентября, PDF).
  3. Проблемы останова и самоприменимости. Нормальные алгоритмы Маркова. Примеры других алгоритмических систем. Тезис Тьюринга-Черча. Язык программирования Си. (13 сентября, PDF).
  4. Стандарты и роль стандартизации. Первая программа на Си. Структура программного файла. Системные библиотеки и их использование. Описание Си-машины: процессор, классы памяти (регистровые, автоматические и статические переменные). Типы данных языка Си: целые, логические, символьные, с плавающей точкой. Представление в памяти переменных целочисленных типов. (20 сентября, PDF).
  5. Переменные: класс памяти, область действия. Инициализация переменных. Арифметические и логические выражения. Ленивое вычисление логических выражений. Операции присваивания. (23 сентября, PDF).
  6. Точки следования. Форматный ввод-вывод. Приведение типов при вычислении выражений (явное и неявное). Операторы. (27 сентября, PDF).
  7. Операторы (окончание). Символьный тип и обработка символьных данных. Массивы. Инициализация массивов.  Строки. Обработка строк. Операция sizeof. (30 сентября, PDF.)
  8. Указатели. Адресная арифметика. Массивы и указатели. Преобразования типа указателей. Функции. Определение и объявление функции. Передача параметров. (04 октября, PDF).
  9. Функции (окончание). Передача массивов в функции. Рекурсия. Хвостовая рекурсия. Встраивание функций. Указатели на функцию. (07 октября, PDF).
  10. Побитовая обработка данных. Абстрактный тип данных «множество» и его реализация. Структуры. Указатели на структуры. Составные инициализаторы структур. Объединения. Анонимные объединения и структуры. Битовые поля. Перечисления. (11 октября, PDF).
  11. Представление данных с плавающей точкой. Стандарт IEEE 754. Вычисление сумм и произведений данных с плавающей точкой. Потеря точности при сложении и вычитании. Выбор правильной последовательности вычислений. Опции компилятора gcc для вычислений с плавающей точкой. Схема компиляции программ на языке Си. Препроцессор. Директивы препроцессора. Компоновка. Классы памяти и компоновки. (14 октября, PDF).
  12. Динамическое выделение и освобождение памяти. VLA-массивы и их выделение в динамической памяти. Массив переменного размера в составе структуры. (18 октября, PDF).
  13. Организация типа данных «стек» на динамической памяти. Использование стека для построения обратной польской записи. Очередь. (25 октября, PDF).
  14. Списки. Добавление нового элемента в начало и в конец списка. Поиск элемента в списке. Удаление заданного элемента из списка: через возврат указателя на новый список, через передачу двойного указателя. Алгоритм топологической сортировки Вирта. (28 октября, PDF).
  15. Понятие о сложности алгоритмов. Поиск подстроки по образцу. Простейший алгоритм. Алгоритм Кнута – Морриса – Пратта (КМП). Префикс-функция и ее вычисление. Сложность вычисления префикс-функции и алгоритма КМП. (1 ноября, PDF).
  16. Простейшие алгоритмы сортировки (выбором, вставками, обменами).  Оценка сложности алгоритмов сортировки. Быстрая сортировка. (8 ноября, PDF).
  17. Двоичные деревья и его обходы (сначала в глубину, сначала в ширину). Нерекурсивный симметричный обход двоичного дерева. «Прошитое» двоичное дерево и его обход. (11 ноября, PDF).
  18. Двоичные деревья поиска и операции над ними (поиск элемента, минимальный и максимальный элементы, следующий элемент, вставка и удаление элемента). Деревья Фибоначчи. Оценка высоты дерева Фибоначчи. (15 ноября, PDF).
  19. АВЛ-деревья. Базовые операции над АВЛ-деревьями. Балансировка АВЛ-дерева. Вставка и удаление элемента в/из АВЛ-дерева. Оценка высоты АВЛ-дерева по дереву Фибоначчи. (18 ноября, PDF).

Leave a Reply