Презентация на тему «Алгоритмы и структуры данных»

Слайд 1. Алгоритмы и структуры данных

• Основы алгоритмического мышления: базовые структуры хранения, оценка вычислительной сложности и классические методы решения задач

Доклад: Тема нашей презентации — алгоритмы и структуры данных. Это базовый раздел информатики, который объясняет, как организовать хранение данных и как за приемлемое время получить из них нужный ответ. Разберём основные структуры, научимся оценивать сложность и рассмотрим классические методы разработки алгоритмов.

Слайд 2. Содержание

• Введение
• Алгоритм и его свойства
• Блок-схема: двоичный поиск
• История алгоритмов
• Учёные, определившие направление
• Оценка вычислительной сложности
• Классы сложности от лучшего к худшему
• Классификация структур данных
• Массив и связный список
• Стек и очередь
• Хеш-таблица
• Деревья: виды и назначение
• Графы: от мостов Кёнигсберга
• Алгоритмы на графах
• Сравнение алгоритмов сортировки
• Как растёт время квадратичной сортировки
• Методы разработки алгоритмов
• Рекурсия и Ханойская башня
• Алгоритмы в цифровых сервисах
• Выводы
• Список литературы

Доклад: Работа построена от общего к частному. Сначала определим само понятие алгоритма и его свойства, затем перейдём к оценке вычислительной сложности, разберём основные структуры данных, алгоритмы сортировки и поиска, а завершим методами разработки и примерами из реальных цифровых сервисов.

Слайд 3. Введение

• Алгоритмы и структуры данных — фундамент программирования: от них зависит, отработает программа за доли секунды или за сутки.
• Объём хранимых человечеством данных растёт на десятки процентов в год, поэтому цена неудачного алгоритмического решения постоянно увеличивается.
• Удачно выбранная структура хранения сокращает поиск в миллионе записей с миллиона сравнений до двадцати.
• Алгоритмическая подготовка — обязательная часть обучения по направлениям «Информатика и вычислительная техника» и «Прикладная математика».

Доклад: Алгоритмы и структуры данных определяют, будет программа работать доли секунды или сутки. Объём данных растёт быстрее, чем производительность процессоров, поэтому цена неудачного алгоритмического решения только увеличивается. Хорошо подобранная структура хранения сокращает поиск в миллионе записей с миллиона сравнений всего до двадцати.

Слайд 4. Алгоритм и его свойства

• Дискретность — алгоритм разбит на отдельные завершённые шаги, каждый выполняется за конечное время.
• Детерминированность — при одних и тех же исходных данных результат всегда получается одинаковым.
• Конечность — исполнение завершается за конечное число шагов, а не длится бесконечно.
• Массовость — алгоритм решает не единственную задачу, а целый класс однотипных задач.
• Результативность — по завершении выдан ответ либо обоснованное сообщение о его отсутствии.

Доклад: Алгоритм — это конечная последовательность точно определённых действий, приводящая к решению задачи. Классически выделяют пять его свойств: дискретность, детерминированность, конечность, массовость и результативность. Если хотя бы одно нарушено — перед нами не алгоритм, а лишь описание намерений.

Слайд 5. Блок-схема: двоичный поиск

• Начало: отсортированный массив
• Взять средний элемент рабочего отрезка
• Средний элемент равен искомому? — отбросить половину отрезка, где искомого заведомо нет
• Отрезок ещё не пуст? — сообщить, что элемент отсутствует
• Итог: элемент найден
• Блок-схема — стандартная графическая запись алгоритма: овал обозначает начало и конец, прямоугольник — действие, ромб — проверку условия.
• Двоичный поиск применим только к упорядоченным данным — это плата за скорость.
• Каждый шаг отбрасывает ровно половину оставшихся элементов.
• В массиве из миллиона элементов ответ находится максимум за 20 сравнений.

Доклад: На схеме показан двоичный поиск — эталонный пример эффективного алгоритма. Мы берём средний элемент отрезка, сравниваем его с искомым и каждым шагом отбрасываем ровно половину оставшихся данных. Именно поэтому в массиве из миллиона элементов ответ находится не более чем за двадцать сравнений, но работает это только на отсортированных данных.

Слайд 6. История алгоритмов

• Само слово «алгоритм» произошло от латинской формы имени среднеазиатского учёного аль-Хорезми.
• До XX века алгоритмы описывали словесно; строгое математическое определение появилось лишь в работах Тьюринга, Чёрча и Поста.
• Теория алгоритмов и теория сложности сложились во второй половине XX века вместе с электронными вычислительными машинами.
• 300 до н. э. — алгоритм Евклида для наибольшего общего делителя
• 825 — трактат аль-Хорезми о вычислениях
• 1843 — первая программа Ады Лавлейс
• 1936 — машина Тьюринга и понятие вычислимости
• 1959 — алгоритм Дейкстры о кратчайшем пути
• 1968 — первый том «Искусства программирования»

Доклад: История алгоритмов насчитывает больше двух тысяч лет: алгоритм Евклида для наибольшего общего делителя описан ещё около трёхсот года до нашей эры. Само слово «алгоритм» пришло от латинской формы имени учёного аль-Хорезми, чей трактат познакомил Европу с позиционным счётом. Строгое математическое определение алгоритма появилось только в тридцатые годы XX века в работах Тьюринга, Чёрча и Поста.

Слайд 7. Учёные, определившие направление

• Ада Лавлейс, 1815–1852, Составила первую в истории программу — вычисление чисел Бернулли для аналитической машины Бэббиджа.
• Эдсгер Дейкстра, 1930–2002, Автор алгоритма кратчайшего пути и один из создателей структурного программирования.
• Дональд Кнут, род. 1938, Автор многотомника «Искусство программирования» — энциклопедии алгоритмов и их точного анализа.

Доклад: За ключевыми идеями стоят конкретные люди. Ада Лавлейс в 1843 году составила первую в истории программу для аналитической машины Бэббиджа. Эдсгер Дейкстра дал нам алгоритм кратчайшего пути и принципы структурного программирования, а Дональд Кнут в многотомнике «Искусство программирования» превратил анализ алгоритмов в строгую научную дисциплину.

Слайд 8. Оценка вычислительной сложности

• T(n) = O(f(n))
• T(n) — число элементарных операций, выполняемых алгоритмом
• n — размер входных данных: длина массива, число вершин графа
• f(n) — функция роста, задающая верхнюю границу трудоёмкости
• O — асимптотическая оценка «растёт не быстрее, чем»

Доклад: Чтобы сравнивать алгоритмы независимо от языка и компьютера, используют асимптотическую оценку. Запись T(n) = O(f(n)) означает, что число операций растёт не быстрее заданной функции от размера входных данных. Константы и слагаемые низшего порядка отбрасываются: на больших объёмах данных всё решает старший член.

Слайд 9. Классы сложности от лучшего к худшему

• Константы и слагаемые низшего порядка при оценке отбрасываются: на больших данных решает старший член.
• Разница между O(n log n) и O(n²) на миллионе элементов — это секунды против нескольких суток.
• Кроме времени оценивают и дополнительную память, которую алгоритм требует сверх входных данных.
• O(1) — постоянное время: обращение к элементу массива по индексу
• O(log n) — логарифм: двоичный поиск, операции в сбалансированном дереве
• O(n) — линейно: один проход по всем данным, поиск максимума
• O(n log n) — предел для сортировки сравнениями: слияние, быстрая сортировка
• O(n²) и хуже — квадратичные и переборные методы, пригодны лишь для малых объёмов

Доклад: Ступени сложности выстраиваются от постоянного времени до квадратичного и хуже. Обращение к элементу массива по индексу — это O(1), двоичный поиск — O(log n), один проход по данным — O(n), лучшие сортировки сравнениями — O(n log n). Разница между O(n log n) и O(n²) на миллионе элементов — это секунды против нескольких суток работы.

Слайд 10. Классификация структур данных

• Структуры данных различают по способу организации связей между элементами и по типу доступа к ним.
• Массив
• Связный список
• Стек
• Очередь
• Дек
• Дерево поиска
• Куча
• Граф
• Префиксный бор
• Хеш-таблица
• Словарь
• Множество

Доклад: Структуры данных удобно делить на три группы. Линейные — массивы, списки, стеки и очереди — хранят элементы в виде последовательности. Нелинейные — деревья, кучи и графы — задают отношения ветвления и связей. Ассоциативные — хеш-таблицы, словари и множества — обеспечивают доступ по ключу.

Слайд 11. Массив и связный список

• Обе структуры хранят последовательность элементов, но по-разному размещают их в памяти — отсюда и разная стоимость операций.
• Элементы лежат в памяти подряд, адрес вычисляется по индексу
• Доступ к любому элементу за постоянное время O(1)
• Вставка в середину требует сдвига — O(n)
• Размер задаётся заранее, расширение означает копирование
• Каждый узел хранит значение и ссылку на следующий узел
• Доступ к k-му элементу только перебором — O(n)
• Вставка и удаление при известном узле — O(1)
• Растёт по мере надобности, но тратит память на ссылки

Доклад: Массив и связный список решают одну задачу, но по-разному размещаются в памяти. У массива элементы лежат подряд, поэтому доступ по индексу мгновенный, зато вставка в середину требует сдвига всех последующих элементов. Список, наоборот, легко перестраивается за счёт ссылок, но добраться до k-го элемента можно только перебором.

Слайд 12. Стек и очередь

• Это структуры с намеренно ограниченным доступом: работать разрешено только с одним концом последовательности, зато все операции выполняются за постоянное время.
• Добавление и извлечение идут только через вершину
• Хранит адреса возврата и локальные данные при вызове функций
• Обеспечивает отмену действий и обход графа в глубину
• Используется при разборе выражений и проверке скобок
• Добавление в хвост, извлечение из головы
• Планирование задач и буферизация входящих запросов
• Основа обхода графа в ширину
• Кольцевая реализация экономит память при постоянном потоке

Доклад: Стек и очередь — структуры с намеренно ограниченным доступом, и в этом их сила: все операции выполняются за постоянное время. Стек работает по принципу «последним пришёл — первым ушёл» и лежит в основе вызова функций и обхода в глубину. Очередь работает по принципу «первым пришёл — первым ушёл» и применяется в планировщиках задач и обходе графа в ширину.

Слайд 13. Хеш-таблица

• Хеш-функция превращает ключ в номер ячейки, поэтому нужная запись находится напрямую, а не перебором.
• Среднее время поиска, вставки и удаления — O(1), в вырожденном случае массовых совпадений — O(n).
• Совпадения адресов (коллизии) разрешают методом цепочек или открытой адресацией.
• При заполнении выше 70–75 % таблицу перестраивают с удвоением размера, иначе скорость падает.

Доклад: Хеш-таблица работает как библиотечная картотека: по ключу мы сразу знаем нужный ящик, а не перебираем все подряд. В среднем поиск, вставка и удаление занимают постоянное время, но при массовых коллизиях таблица вырождается в список. Поэтому важны качественная хеш-функция, разрешение коллизий и своевременная перестройка таблицы при заполнении выше семидесяти процентов.

Слайд 14. Деревья: виды и назначение

• Двоичное дерево поиска — слева меньшие ключи, справа большие; поиск за O(log n) при сбалансированности.
• АВЛ-дерево — самобалансирующееся дерево, высоты поддеревьев различаются не более чем на единицу.
• Красно-чёрное дерево — основа упорядоченных словарей в стандартных библиотеках языков программирования.
• Куча — дерево, в котором родитель не меньше потомков; даёт очередь с приоритетом.
• Префиксный бор — хранит строки посимвольно, ускоряет автодополнение и словарный поиск.

Доклад: Деревья дают компромисс между скоростью поиска и удобством вставки. Двоичное дерево поиска ищет за логарифм, но только пока остаётся сбалансированным — за этим следят АВЛ-деревья и красно-чёрные деревья. Куча обеспечивает очередь с приоритетом, а префиксный бор используют для автодополнения и словарного поиска.

Слайд 15. Графы: от мостов Кёнигсберга

• Граф — множество вершин и связывающих их рёбер; так описывают дороги, социальные связи и зависимости задач.
• В 1736 году Леонард Эйлер доказал, что обойти семь мостов Кёнигсберга ровно по одному разу невозможно.
• Из этой задачи выросла теория графов — язык маршрутизации, планирования и анализа сетей.
• Граф хранят матрицей смежности (мгновенная проверка ребра) или списками смежности (экономия памяти на разреженных сетях).

Доклад: Теория графов началась с бытовой задачи: можно ли обойти семь мостов Кёнигсберга, пройдя по каждому ровно один раз. В 1736 году Леонард Эйлер доказал, что нельзя, и заодно создал целый раздел математики. Сегодня графами описывают дорожные сети, социальные связи и зависимости работ, а хранят их матрицей или списками смежности.

Слайд 16. Алгоритмы на графах

• Большинство прикладных задач сводится к обходу графа или поиску в нём оптимального пути.
• Выбор алгоритма определяют два вопроса: есть ли у рёбер веса и могут ли эти веса быть отрицательными.
• Обход в ширину — послойный обход, даёт кратчайший путь в невзвешенном графе
• Обход в глубину — уход вглубь ветви, находит компоненты связности и циклы
• Алгоритм Дейкстры — кратчайшие пути при неотрицательных весах рёбер
• Алгоритм Краскала — минимальное остовное дерево через сортировку рёбер
• Топологическая сортировка — корректный порядок выполнения зависимых работ

Доклад: Прикладные задачи на графах решаются небольшим набором классических алгоритмов. Обход в ширину даёт кратчайший путь в невзвешенном графе, обход в глубину находит циклы и компоненты связности. Алгоритм Дейкстры строит кратчайшие маршруты при неотрицательных весах, Краскал — минимальное остовное дерево, а топологическая сортировка задаёт корректный порядок зависимых работ.

Слайд 17. Сравнение алгоритмов сортировки

• Сортировка — самая изучаемая задача: на ней удобно видеть цену выбора алгоритма.
• Устойчивая сортировка сохраняет исходный порядок равных элементов — это важно при многоуровневой сортировке таблиц.

Доклад: Таблица сравнивает пять классических сортировок по времени, дополнительной памяти и устойчивости. Квадратичные методы просты в реализации и хороши только на малых массивах. Сортировка слиянием устойчива, но требует дополнительной памяти, быстрая сортировка экономнее по памяти и в среднем быстрее, а пирамидальная работает почти без дополнительной памяти.

Слайд 18. Как растёт время квадратичной сортировки

• При удвоении массива время сортировки пузырьком увеличивается примерно вчетверо — это и есть квадратичная зависимость.
• Быстрая сортировка на тех же 160 тысячах элементов укладывается в доли секунды.

Доклад: График наглядно показывает квадратичный рост: при каждом удвоении массива время сортировки пузырьком увеличивается примерно вчетверо — с десятых долей секунды до тридцати секунд. Быстрая сортировка на тех же ста шестидесяти тысячах элементов справляется за доли секунды. Это и есть практический смысл асимптотических оценок.

Слайд 19. Методы разработки алгоритмов

• Разделяй и властвуй — дробим задачу на подзадачи и объединяем решения
• Динамическое программирование — сохраняем ответы подзадач и не считаем их дважды
• Жадные алгоритмы — на каждом шаге берём локально лучший вариант
• Перебор с отсечениями — обходим варианты, отбрасывая заведомо безнадёжные ветви

Доклад: Разработка алгоритма опирается на несколько универсальных приёмов. Разделяй и властвуй дробит задачу на подзадачи, динамическое программирование запоминает их решения и не считает дважды, жадные алгоритмы выбирают локально лучший шаг. Перебор с отсечениями остаётся последним средством там, где точное решение иначе не найти.

Слайд 20. Рекурсия и Ханойская башня

• Рекурсия — приём, при котором функция вызывает сама себя с уменьшенной задачей до простейшего случая.
• Ханойская башня из n дисков требует ровно 2ⁿ − 1 перекладываний: для 64 дисков это более 18 квинтиллионов ходов.
• Каждый вызов хранится в стеке, поэтому глубина рекурсии ограничена объёмом памяти.
• Повторные вычисления убирает запоминание промежуточных результатов, а простые случаи переписываются в обычный цикл.

Доклад: Ханойская башня — классическая иллюстрация рекурсии: чтобы переложить башню из n дисков, нужно сначала переложить башню из n минус одного диска. Число ходов равно двум в степени n минус один, поэтому для шестидесяти четырёх дисков задача практически невыполнима. Каждый вызов занимает место в стеке, и глубина рекурсии всегда ограничена памятью.

Слайд 21. Алгоритмы в цифровых сервисах

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

Доклад: В реальных сервисах алгоритмы работают незаметно, но постоянно. Поисковые системы используют обратный индекс и графовое ранжирование, навигаторы — алгоритм Дейкстры с эвристиками, архиваторы — коды Хаффмана, а базы данных ускоряют выборки деревьями индексов. За каждым привычным нажатием кнопки стоит десяток классических алгоритмов.

Слайд 22. Выводы

• Алгоритм и структура данных — две стороны одного решения: способ хранения определяет набор доступных операций и их скорость.
• Асимптотическая оценка позволяет предсказать поведение программы на больших данных ещё до её запуска.
• Базовый набор структур — массивы, списки, стеки, очереди, хеш-таблицы, деревья и графы — покрывает подавляющее большинство прикладных задач.
• Классические приёмы разработки остаются рабочим инструментом инженера независимо от языка программирования и модной технологии.

Доклад: Подведём итоги. Алгоритм и структура данных неразделимы: способ хранения определяет, какие операции окажутся дешёвыми, а какие — разорительными. Асимптотическая оценка позволяет предсказать поведение программы на больших данных заранее, а базовый набор структур и классических приёмов покрывает большинство прикладных задач.

Слайд 23. Список литературы

• Ахо, А. В. Структуры данных и алгоритмы : учебное пособие / А. В. Ахо, Д. Э. Хопкрофт, Д. Д. Ульман. — Москва : Вильямс, 2016. — 400 с.
• Вирт, Н. Алгоритмы и структуры данных : учебное издание / Н. Вирт. — Санкт-Петербург : Невский Диалект, 2008. — 352 с.
• Кнут, Д. Э. Искусство программирования. Том 1. Основные алгоритмы : монография / Д. Э. Кнут. — 3-е изд. — Москва : Вильямс, 2019. — 720 с.
• Кормен, Т. Алгоритмы: построение и анализ : учебник / Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн. — 3-е изд. — Москва : Вильямс, 2013. — 1328 с.
• Седжвик, Р. Фундаментальные алгоритмы : учебное пособие / Р. Седжвик. — Москва : Вильямс, 2011. — 1056 с.

Доклад: В основу работы легли признанные учебники по алгоритмам. Это классические труды Кормена, Кнута, Вирта, Ахо и Седжвика — источники, по которым алгоритмы преподают в университетах по всему миру. Они рекомендуются для самостоятельного углублённого изучения темы.

Слайд 24. Спасибо за внимание!

Доклад: На этом доклад завершён. Мы рассмотрели понятие алгоритма, способы оценки его сложности, основные структуры данных и классические методы разработки. Благодарю за внимание, готов ответить на вопросы.