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

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

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

Leave a Reply