Лекция по теории чисел и графам✏️

План лекции

1. Теория чисел
2. Графы и их алгоритмы

Разбор задач по теории чисел

Задача 1: НОД соседних чисел

• НОД соседних чисел (GCD) всегда равен 1, если числа последовательности различны
• Если числа равны, то GCD равен числу

Задача 2: Последовательность чисел

• Рассчитать GCD для последовательностей A и B
• Цель: максимально оптимизировать вычисления

Задача 3: Экран и фильм

• Вписать фильм в экран по пропорциям
• Проверка отношения сторон
• Оценка результата деления и приведение к простым дробям

Задача 4: Модифицированное НОД

• Найти максимальный общий делитель в заданном интервале
• Использование алгоритма Евклида
• Обработка и повторение запросов с оптимизацией

Задача 5: Наполнители воды

• Два насоса с разной скоростью
• Нужно восстановить данные по скорости заполнения с использованием диафантовых уравнений

Задача 6: Таблица НОД

• Восстановление массива по таблице НОД
• Упорядочение массива, использование связей НОД для вычисления значений

Задача 7: Значения длинных путей

• Алгоритм Евклида и его применения
• Разбор всех возможных случаев изменения чисел

Задача 8: Различные делители

• Найти наименьшее число, обладающее заданными делителями
• Асимптотика решения ибыстрота реализации

Задача 9: Перекачивание воды

• Стратегия деления на простые множители для эффективного вычисления

Разбор алгоритмов на графах

Алгоритм DFS (Depth-First Search)

• Обход графа в глубину
• Рекурсивная реализация
• Использование массива посещённых вершин
• Применение на ориентированных и неориентированных графах

Мосты в графах

• Определение и нахождение
• Разбиение графа на компоненты при удалении мостов

Точки сочленения

• Определение и нахождение
• Удаление вершин и проверка связности графа

Компоненты сильной связности

• Определение и нахождение в ориентированном графе
• Алгоритм Тарьяна используемый для нахождения таких компонент

Алгоритмы кратчайших путей

Алгоритм Деикстры

• Найти кратчайший путь от одной вершины до всех остальных
• Ограничение: Ребра с не отрицательными весами
• Использование priority queue для оптимизации

Алгоритм Беллмана-Форда

• Решение задачи с произвольными весами рёбер (включая отрицательные)
• Возможность работы с отрицательными циклами
• Проверка наличия таких циклов

Алгоритм Флойда-Уоршелла

• Нахождение кратчайших путей между всеми парами вершин
• Обработка разряжённой таблицы для ускорения вычислений

Деревья отрезков и работа с ними

Разбиение на центроиды

• Оптимизация деревообразных структур
• Разбиение на компоненты для упрощения обработки данных
• Нахождение центроидов и выполнение вычислений

Система Непересекающихся Множеств (Union-Find)

• Операции объединения и нахождения
• Оптимизации с сжатием путей и ранговой эвристикой

Паросочетания в двудольных графах

• Определения и нахождение максимального паросочетания
• Оптимизация и доказательство корректности алгоритмов

Эйлеров цикл и путь

• Определение и нахождение
• Критерии существования и алгоритм построения

Заключение

• Обзор основных алгоритмов и структур данных
• Применение алгоритмов на практике
• Подготовка к сложным задачам и олимпиадам по программированию