Лекции

Все ссылки и материалы курса

№1: Основы C++

Переменные, ввод-вывод, арифметические операции. Условия. Циклы

Документы: Презентация

№2: Основы C++

Циклы. Динамические массивы

Документы: Презентация

№3: Основы C++. Функции

Объявление и вызов функций, передача аргументов по значению, ссылке и указателю, возвращаемые значения

Документы: Презентация • Конспект

№4: Сложность алгоритмов и сортировки

Оценка сложности алгоритмов, квадратичные сортировки

Документы: Презентация • Конспект

№5: Рекурсия. Быстрые сортировки

Рекурсия, сортировка слиянием, быстрая сортировка, сортировка подсчётом

Документы: Презентация • Конспект

№6: Двоичный поиск

Стандартный двоичный поиск, бинарный поиск по ответу, вещественный бинарный поиск. Поиск минимума выпуклой функции методом дихотомии

Документы: Презентация • Конспект

№7: Указатели, ссылки. Стек и очередь

Модель памяти, указатели и разыменование, ссылки, стек и очередь

Документы: Презентация

№8: Динамическая память. Основы ООП. Связные списки

Выделение и освобождение памяти (new/delete), классы и структуры, односвязные и двусвязные списки

Документы: Презентация

№9: Сортировка событий

Лямбда-функции, пользовательские компараторы, метод сканирующей прямой (sweep line)

Документы: Презентация • Конспект

№10: Графы. Обход в глубину

Представление графов в памяти, алгоритм обхода в глубину (DFS), время входа и выхода

Документы: Презентация • Конспект

№11: Обход в глубину: применения

Компоненты связности, поиск цикла в ориентированном графе, классификация рёбер, проверка двудольности, топологическая сортировка

Документы: Презентация

№12: Обход в ширину

Алгоритм обхода в ширину (BFS), кратчайшие пути в невзвешенном графе, восстановление пути

Документы: Презентация • Конспект

№13: Мосты, точки сочленения. Конденсация графа

Поиск мостов, точек сочленения, конденсация

Документы: Презентация • Конспект

№14: Алгоритм Дейкстры

Кратчайшие пути от одной вершины в графе с неотрицательными весами, реализации за O(n²) и O(m log n), восстановление пути

Документы: Презентация • Конспект

№15: Алгоритмы Флойда-Уоршелла и Форда-Беллмана

Кратчайшие пути между всеми парами вершин за O(n³), кратчайшие пути при отрицательных весах, обнаружение циклов отрицательного веса

Документы: Презентация • Конспект

№16: Минимальное остовное дерево

Лемма о безопасном ребре, жадная стратегия построения MST, алгоритм Прима за O(n²) и O(m log n)

Документы: Презентация • Конспект

№17: Куча

Двоичная куча, хранение в массиве, sift_up и sift_down, построение кучи за O(n), priority_queue в STL

Документы: Презентация • Конспект

№18: Двоичное дерево поиска

Поиск, вставка и удаление в BST, обходы дерева (inorder = сортированный порядок), сбалансированные деревья, std::set и std::map

Документы: Презентация • Конспект
No matching items