Войти
Информатика 25 лекций
Алгоритмы и алгоритмические языки
3479
Лектор
Белеванцев Андрей Андреевич
#лекции
ВМК
I семестр
Осень 2019

Курс читается в качестве вводного программистского курса на факультете ВМК МГУ и состоит из трех разделов: введение в теорию алгоритмов, язык программирования Си, и алгоритмы и структуры данных.

Список всех тем лекций

Лекция 1. Машина Тьюринга.
Элементы теории алгоритмов Машина Тьюринга Алфавиты и отображения Кодирование Обработка информации Машина Тьюринга

Лекция 2. Машина Тьюринга. Часть 2.
Машина Тьюринга Разбор задач на МТ Машина с лентой с одним ограниченным концом

Лекция 3. Универсальная машина Тьюринга и нормальные алгоритмы Маркова.
Моделирование Машины Тьюринга Универсальная Машина Тьюринга Останов Машины Тьюринга Нормальные алгоритмы Маркова

Лекция 4. НАМ и введение в язык С.
Нормальные алгоритмы Маркова Общая классификация и характеристика языков программирования Язык Си Характеристика языка Си

Лекция 5. Типы данных в С.
Стандартные библиотеки. Разбор первой программы. Си-машина. Классы памяти. Базовые типы. Представление целых чисел. Размеры типов. Тип Bool,Complex

Лекция 6. Переменные. Ввод-вывод в С.
Переменные. Область действия переменных. Классы памяти и область действия. Инициализация переменных. Литералы. Операция над целочисленными данными. Операция присваивания. Точки следования. Форматный ввод-вывод. Спецификатор ввода-вывода.

Лекция 7. Операции и операторы Си.
Присваивания Неявное приведение типов Приоритеты операций Операторы

Лекция 8. Строки и массивы Си.
Символьный тип данных Преобразование строк цифр в целое число Массивы Строки

Лекция 9. Строки и указатели.
Строки. Sizeof. Указатели. Адресная арифметика.

Лекция 10. Функции.
Указатели и Массивы. Функции Вызов Функции и указатели функций.

Лекция 11. Рекурсия и указатели на функции.
Возврат из функции Результат выполнения функции Рекурсия Встраиваемые функции Указатели на функции.

Лекция 12. Структуры и объединения.
Побитовые операции Структуры Указатели на структуры Составные инициализаторы структур Старшинство операций Объединения Битовые поля Перечисления

Лекция 13. Препроцессор и распределение динамической памяти.
Схема раздельной компиляции Препроцессор Компоновка и классы памяти: переменные Динамическое распределение памяти

Лекция 14. Отладка программы.
Динамическое выделение памяти для двумерного массива. VLA-массивы Динамическое распределение памяти Массив переменного размера в структуре Отладка программы Поиск ошибок работы с памятью

Лекция 15. Вещественные числа в Си.
Вычисления ошибок с плавающей точкой Дробные двоичные числа Представление чисел с плавающей точкой Типы плавающей арифметики Арифметические операции с плавающей точкой Умножение и сложение чисел с плавающей точкой Вещественные типы языка Си

Лекция 16. Введение в алгоритмы. Сложность алгоритмов и алгоритм Кнута-Морриса-Пратта.
Сложность алгоритмов Лемма о двух суффиксах. Простой алгоритм и алгоритм Кнутта-Морриса-Пратта

Лекция 17. Стэк, очередь, список.
Стэк и очередь Работа со стэком в СИ Очередь в Си Список

Лекция 18. Графы, топологическая сортировка.
Списки Графы Топологическая сортировка на СИ

Лекция 19. Сортировки в Си.
Топологическая сортировка Сортировки в Си Оценка сложности алгоритмов сортировки

Лекция 20. Двоичные деревья.
Быстрая сортировка Двоичное дерево Способы обхода двоичного дерева Нерекурсивный симметричный обход двоичного дерева "Прошитое" двоичное дерево и его обходы

Лекция 21. Дерево поиска.
"Прошитое" двоичное дерево и его обходы Дерево поиска Двоичное дерево поиска:вставка и удаление

Лекция 22. АВЛ деревья.
Построение двоичного дерева поиска Деревья Фибоначчи АВЛ деревья Включение узла в АВЛ-дерево Построение АВЛ дерева

Лекция 23. Красно-черные деревья и самоперестраивающиеся деревья.
Красно-черные деревья. Вставка вершины Самоперестраивающиеся деревья

Лекция 24. Сбалансированные деревья и Хеш-функции.
Сбалансированные деревья: понятие ранга Пирамидальная сортировка Хэш-таблицы Хэш-функции и методы их построения

Лекция 25. Цифровой поиск.
Хэширование с открытой адресацией Хэширование других данных Цифровой поиск