Algorithms-and-Programming-in-C-pptx

Здесь работаю над презентациями, которые потом использую для чтения лекции по дисциплине Программирование ФИТ НГУ.

Ставьте звезды, создавайте issue, делайте пул-реквесты

Лекция 1 Понятие программы

• Информация о курсе
• Понятие программы
• Понятие компиляции, сборки, системы контроля версий
• Понятие отладки, оптимизации, тестирования
• Как выполнять лабораторные работы на gitlab.ccfit.nsu.ru

Лекция 2 Лексика и концепции языка Си

• Язык Си и современное программирование
• Пространства имён, области видимости имён и связывание имён
• Время жизни и продолжительность хранения переменных в памяти
• Лексемы языка Си -- ключевые слова, операторы, синтаксис констант

Лекция 3 Типы языка Си

• Понятие типа и системы типов языка программирования
• Семейства типов языка Си -- функциональные/полные/неполные, целые/с плавающей точкой/производные и т.д.
• Представление типов языка Си в памяти -- целые знаковые/беззнаковые, с плавающей точкой, производные и т.д.

Лекция 4 Выражения в языке Си

• Общие правила построения выражений
• Приоритет, ассоциативность и неявная расстановка скобок
• Понятие l-value
• Понятие точки следования
• Обзор операторов -- требования к операндам, исполнение, побочные эффекты, условия возникновения implementation-specific behavior, условия возникновения undefined behavior

Лекция 5 Преобразования типов в языке Си

• Общие свойства всех преобразований типов
• Преобразования целых и типов с плавающей точкой -- общий тип, целочисленное повышение (integer promotion), протяжка знака (sign propagation/extension)
• Преобразование l-value
• Преобразования массивов -- генерация указателя (pointer generation)
• Преобразования функциональных типов
• Преобразования с типом void
• Преобразования указателей

Лекция 6 Функции в языке Си

• Понятие подпрограммы -- граф вызовов, стековый кадр, стек вызовов
• Функции в языке Си -- формальные и фактические параметры, возвращаемое значение, вариадические функции

Лекция 7 Размещение типов в памяти

• Размещение в стековом кадре -- выравнивание, связь выравниваний производного типа и его элементов, выравнивающие байты
• Размещение в динамической памяти -- Doug Lea's malloc, накладные расходы, фрагментация памяти, виды ошибок, Address Sanitizer

Лекция 8 Абстрактные типы данных

• Понятие абстрактного типа данных (АТД) и реализации абстратного типа данных
• АТД список
• АТД стек -- реализация через список, через массив
• Алгоритм построения польской записи арифметического выражения и вычисления польской записи

Лекция 9 Очередь, дек, граф

• АТД очередь -- реализации через список, через циклический буфер, через два стека
• АТД дек -- реализация через двусвязный список
• Граф -- определения, реализация через матрицу смежности, через списки смежности, через упакованные списки смежности
• Свойства матрицы смежности

Лекция 10 Деревья

• Использование деревьев в программировании
• Определения -- дерево, поддерево и т.п.
• Обходы деревьев в глубину и в ширину
• Дерево двоичного поиска -- поиск вершины, вставка и удаление вершины
• АВЛ деревья -- поиск вершины, вставка вершины, короткий и длинный поворот

Лекция 11 Алгоритмы поиска

• Общая постановка задачи поиска
• Поиск ключа в массиве и списке -- линейный, бинарный, хэш-таблицы
• Поиск подстроки в строке -- наивный, алгоритм Бойера-Мура, алгоритм Рабина-Карпа, алгоритм Кнута-Морриса-Пратта

Лекция 12 Алгоритмы сортировки

• Понятие сортировки
• Сортировка вставками, сортировка бинарными вставками, устойчивая сортировка
• Сортировка выбором, пирамидальная сортировка
• Быстрая сортировка, неустойчивость быстрой сортировки
• Оценка числа действий и объёма дополнительной памяти в алгоритмах сортировки

Лекция 13 Кодирование

• Исторические факты о кодировании
• Определения -- алфавит, кодирование и декодирование, код, двоичный код, префиксный код
• Однозначная декодируемость префиксного кода
• Оптимальный двоичный префиксный код Хаффмана
• Префиксный код Фано
• Префиксный код Шеннона, оценка сверху для длины закодированного сообщения через частоты символов, формулировка теоремы Шеннона

Лекция 14 Обходы и каркасы графа

• Использование графов в программировании, понятие обхода вершин графа
• Обход вершин графа в глубину, подграф предшествования, типы дуг графа при обходе в глубину, оценка числа действий при обходе всех вершин графа
• Обход вершин графа в ширину на основе очереди, свойство очереди вершин при обходе в ширину
• Компоненты связности графа, АТД система непересекающихся множеств (СНМ), реализации СНМ через массив и через деревья, оценка числа действий
• Каркас графа, минимальный каркас графа
• Алгоритм Краскала, оценка числа действий
• Алгоритм Прима, оценка числа действий, доказательство корректности

Лекция 15 Кратчайшие пути в графе. Топологическая сортировка

• Определение длины пути, кратчайшего пути, примеры
• Алгоритм Дейкстры, число действий при хранении кратчайших расстояний в массиве, пирамиде и Фибоначчиевой куче
• Кратчайший путь в графе без циклов отрицательной длины
• Алгоритм Беллмана-Форда для графов с произвольными длинами дуг
• Алгоритм Флойда-Уоршелла вычисления кратчайших расстояний между всеми парами вершин графа и его применения (построение транзитивного замыкания графа, подсчёт путей с фиксированным числом вершин)
• Определение топологической сортировки графа
• Нерекурсивный алгоритм топологической сортировки графа на основе матрицы смежности и списков смежности
• Алгоритм топологической сортировки на основе поиска в глубину
• Связь алгоритма топологической сортировки и теоремы о продолжении частичного порядка до линейного

Лекция 16 Б деревья и красно-чёрные деревья

• Общие сведения о Б деревьях (B trees)
• Определение Б дерева, оценка высоты Б дерева с заданным числом вершин
• Алгоритмы поиска и вставки вершины в Б дерево
• Общие сведения о красно-чёрных деревьях
• Определение красно-чёрного дерева, оценка высоты красно-чёрного дерева с заданным числом вершин
• Алгоритм вставки вершины в красно-чёрное дерево
• Сравнение красно-чёрных и АВЛ деревьев по числу действий в алгоритмах поиска и вставки
• Красно-чёрные деревья как частный случай Б деревьев
• Применение красно-чёрных деревьев в С++

Лекция 17 Алгоритмы с возвратом

• Элементы теории сложности вычислений: задача, исполняющее устройство, классы задач P и NP, NP-полные задачи
• Поиск с возвратом как обход в глубину
• Поиск с возвратом как эмуляция работы недетерминированного исполняющего устройства
• Понятие эвристического поиска с возвратом
• Решение задач обхода шахматной доски конём и расстановки ферзей методом поиска с возвратом

Лекция 18 Динамическое программирование

• Динамическое программирование как метод решения задач оптимального управления -- управляемая система, целевая функция, оптимальное управление
• Принцип оптимальности Беллмана
• Прямой и обратный ход
• Примеры решения задач методом динамического программирования -- суммирование набора, задача о рюкзаке, оптимальное произведение матриц
• Связь метода динамического программирования и метода поиска с возвратом

Лекция 19 Оценка вычислительной сложности алгоритмов

• Практический смысл оценки сложности
• Понятие размера данных, объёма используемой памяти и вычислений на примерах (умножение матриц, сортировка вставками, проверка на простоту)
• Понятие сложности по памяти и по времени в худшем случае и в среднем
• Связь сложности в худшем случае и в среднем, связь сложности по времени и памяти
• Пример получения оценки сложности по времени в среднем для алгоритма возведения в целую степень методом повторных квадратов
• Особенности оценки вычислительной сложности на практике
• Оценка сверху сложности по времени в худшем случае на основе исходного кода без рекурсии
• Понятие оптимальной программы и асимптотически оптимальной программы
• Понятие дерева трасс исполнения программы
• Пример доказательства оптимальности по числу сравнений в худшем случае для алгоритма быстрого поиска минимума и максимума в массиве

Лекция 20 Перестановки

• Определение перестановки и инверсии
• Алгоритм восстановления перестановки по таблице инверсий
• Определение факториальной системы счисления; алгоритм перечисления таблиц инверсий
• Алгоритм перечисления перестановок на основе таблицы инверсий
• Алгоритм Дейкстры непосредственного перечисления перестановок в алфавитном порядке
• Оценка сложности по времени в среднем для алгоритма Дейкстры

Лекция 21 Элементы теории формальных языков

• Использование формальных грамматик в программировании, БНФ как прототип формальной грамматики
• Определение грамматики, вывода в грамматике, языка, описываемого грамматикой
• Пример грамматики, описывающей язык с цепочками квадратичной длины
• Классификация грамматик по Хомскому и связь типов грамматик с алгоритмической вычислимостью
• Пример классической грамматики типа 1 aⁿbⁿcⁿ
• Метод построения LL(1) анализатора грамматик типа 2 -- алгоритм анализа на основе таблицы, алгоритмы построения первого и следующего набора

Лекция 22 Препроцессор языка Си

• Понятие препроцессирования исходного кода, несколько фактов о создании препроцессора языка Си
• Этапы работы препроцессора языка Си
• Директивы препроцессора языка Си и выполняемые ими преобразования исходного кода, общие правила записи директив
• Алгоритм исполнения директив препроцессора языка Си
• Объединение единиц трансляции -- примеры, синтаксис, правило поиска единиц трансляции в файловой системе
• Условная компиляция -- примеры, синтаксис, вычисление условий в директивах if и elif
• Макроподстановка -- примеры, синтаксис, алгоритм макроподстановки
• Служебные макроподстановки и вспомогательные директивы

Лекция 23 Совершенный код

• Особенности работы с большим исходным кодом
• Понятие модуля (части) программы
• Понятие зацепления модулей программы
• Виды зацепления модулей программы -- патологическое, по содержимому (content), по общей области (common), смешанное (hybrid), по управлению (control), по данным (data)
• Примеры кода на языке Си с зацеплением и пути устранения зацепления
• Рекомендации по именованию переменных и функций -- профилактика смешанного зацепления
• Рекомендации по повышению локальности переменных и фукнций -- профилактика патологического зацепления

Лекция 24 Эффективность вычислений

• Понятие эффективности вычислений -- виды вычислительных ресурсов, виды требований к использованию ресурсов
• Факторы, влияющие на эффективность -- скорость работы процессора и памяти, виды узких мест
• Устранение узких мест -- использование специализированных библиотек и узнаваемых компилятором паттернов управления и зависимостей по данным, параллелизация
• Пример повышения эффективности умножения матриц на процессоре Intel с 5% до 85% от пика ядра
• Пример повышения эффективности транспонирования больших матриц на процессоре Intel с 20% до 60% от пика памяти

Лекция 25 Многопоточный код

• Понятие многопоточности -- контекст исполнения, поток исполнения, многопоточное исполнение, отличия от многозадачности
• Краткий обзор ранней (до 1997 года) вычислительной техники, ОС и библиотек, поддерживающих многопоточность
• Примеры простого многопоточного кода на основе POSIX threads, OpenMP
• Многопоточность в стандарте языка Си C11 -- потоки, атомарные переменные, взаимное исключение потоков, сигналы (события)
• Понятие конфликта обращений к памяти, виды упорядочения доступов к атомарным переменным (memory order) в стандарте С11
• Примеры использования атомарных переменных -- синхронизация потоков producer-consumer, асинхронный счётчик
• Использование взаимного исключения потоков при доступе к ресурсам, взаимная блокировка потоков, примёмы её устранения
• Использование сигналов (событий) для передачи владения ресурсом другому потоку
• Эффективное использование многопоточности

Лекция 26 Элементы машинного обучения

• Основные понятия и определения машинного обучения, примеры задач регрессии, классификации и ранжирования -- на основе 1-й лекции из курса по машиинному обучению Воронцова К.В.
• Построение классификаторов изображений с помощью нейронных сетей -- примеры простых нейронных сетей Tiny VGG, CIFAR-10, GoogleNet
• Алгоритмы работы основных типов слоёв -- свёртка (convolution), пулинг (pooling), положительная срезка (ReLU)
• Обучение нейронных сетей методами спуска по градиенту
• Вычисление градиента методом автоматического дифференцирования