- •1. Основы теории сложности. Классы сложности np и p.
- •2. Сортировка и поиск . Проверка упорядоченности массива. Способы сортировки.
- •3.Обменная сортировка (метод "пузырька", шейкер-сортировка)
- •4. Сортировка разделением (быстрая сортировка). Распределяющая сортировка.
- •5. Сортировка подсчётом. Сортировка выбором (прямой выбор, линейный выбор, квадратичная )
- •7. Пирамидальная сортировка. Сортировка слиянием (однократное и циклическое)
- •8. Стек. Основные базисные операции для работы со стеком. Организация стека на основе массива и связного списка.
- •9. Очередь. Основные операции для работы с очередью
- •10. Очередь с приоритетом. Основные операции для работы с очередью с приоритетом.
- •11. Деки. Логическая структура дека.
- •12. Списки как динамические структуры данных. Виды линейных списков. Способы формирования односвязных списков. Оценка сложности.
- •13. Односвязный список. Включение элемента в начало списка. Удаление элемента из списка по заданному номеру.
- •14. Односвязный список. Включение элемента в конец списка. Слияние 2 списков.
- •15. Двухсвязный список. Удаление и вставка элемента в список.
- •16. Циклические списки. Просмотр циклического списка.
- •17. Мультисписки. Нелинейные разветвлённые списки.
- •18. Особенности программирования рекурсивных функций. Линейная рекурсия (пример).
- •19. Смешанная, ветвящаяся и бинарная рекурсия. (примеры)
- •20. Рекурсия и поисковые задачи. Результат функции рекурсивного поиска, возврат последовательности, правила разработки.
- •21. Рекурсия и поисковые задачи. Ханойские башни. Генераторы перестановок, сортировки, алгоритмы с матрицами и др.
- •22. Деревья как рекурсивные структуры данных. Основные определения и свойства. Логическое представление и изображение деревьев.
- •23. Бинарные деревья. Вставка элемента
- •24. Бинарные деревья. Удаление элемента
- •25. Бинарные деревья. Поиск . Алгоритм представления любого дерева и леса бинарными деревьями.
- •26. Способы обхода бинарного дерева: нисходящий, восходящий, смешанный.
- •28. Сбалансированные деревья. Показатель сбалансированности. Avl-деревья.
- •29.Виды балансировки деревьев. Балансировка через массив.
- •30. Красно-чёрные деревья.
- •31. Приложения деревьев.Дерево Хаффмана. (оставь здесь 10 шрифт!!!)
- •32. Бинарная куча. Проверка основного свойства кучи.
- •33. Бинарная куча. Определение родительской и дочерних вершин.
- •34. Бинарнаякуча. Алгоритм построения кучи из произвольного массива.
- •36. Бинарная куча. Добавление элемента.
- •39. Алгоритмы вычисления хэш-функции.
- •44. Задача поиска подстрок, простейший алгоритм.
- •47. Методы разработки алгоритмов. Метод декомпозиции, динамическое программирование
- •48. Методы разработки алгоритмов. Жадные алгоритмы, поиск с возвратом, локальный поиск.
1. Основы теории сложности. Классы сложности np и p.
Теория алгоритмов — наука, изучающая общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. Она включает классическую теорию алгоритмов, теорию асимптотического анализа алгоритмов, теорию практического анализа вычислительных алгоритмов. В информатике и теории алгоритмов вычислительная сложность алгоритма — это функция, определяющая зависимость объёма работы, выполняемой некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную сложность, называется теорией сложности вычислений. Рассмотрение входных данных большого размера и оценка роста времени работы алгоритма (T(n)) приводят к понятию асимптотической сложности алгоритма. Ее цель - сравнение затрат времени и других ресурсов различными алгоритмами, предназначенными для решения одной и той же задачи, при больших объемах входных данных. Оценка функции трудоёмкости - сложность алгоритма. О – верхнее ограничение трудоемкости алгоритма, которое показывает, как быстро растет трудоемкость алгоритма с увеличением объема данных. Запись вида f(n) = O(g(n)) означает, что ф-ия f(n) возрастает медленнее чем ф-ия g(n) при с = с1 и n = N, где c1 и N могут быть сколь угодно большими числами, т.е. При c = c1 и n >= N, c*g(n) >=f(n). Соотношения прим.: O(1) < O(log2n) < O(n) < O(nlog2n) < O(n2) < O(n3) < O(2n). Для нижней асимптотической оценки роста функции T(n) используется Ω (омега). T(n) = Ω (nlogn) обозначает класс функций, которые растут не медленнее, чем f(n) nlogn. Для задания одновременно верхней и нижней оценки роста функции T(n) используется Θ (тэтта). Равенство T(n) = Θ(f(n)) выполняется тогда и только тогда, когда T(n)=O(f(n)) и T(n) = Ω (f(n)).f(n) = Ω(n2) даже в самом удачном случае будет произведено не менее n2 действий. f(n) = O(n2) гарантирует, что в самом худшем случае действий будет порядка n2, не больше. Θ(n2) всегда будет выполняться порядка n2 операций. Существует только тогда, когда O() и Ω() совпадают и равна им.
Алгоритм называется полиномиальным, если время его работы оценивается некоторым полиномом(многочленом) от размерности задачи n. Полиномиальные алгоритмы считаются «хорошими», практически эффективными. При разработке алгоритмов можно наблюдать, что для некоторых задач удается построить алгоритмы полиномиальной сложности. Такие задачи называют полиномиально разрешимыми. Полиномиально разрешимые задачи можно успешно решать на компьютере даже в тех случаях, когда они имеют большую размерность.
Множество всех распознавательных задач, для которых существует полиномиальный разрешающий алгоритм, образует класс P (время работы не слишком сильно зависит от размера входных данных). Задачи, принадлежащие классу P: целочисленное сложение, умножение, деление, взятие остатка от деления, умножения матриц. Распознавательные задачи, которые можно решить за полиномиальное время на недетерминированной машине Тьюринга, входят в класс NP(сильно зависят от размера входных данных). Для некоторых задач из этого класса обнаружено удивительное свойство. Оказалось, что некоторые из них универсальны в том смысле, что построение полиномиального алгоритма для любой такой задачи влечет за собой возможность построения такого же алгоритма для всех остальных задач класса NP. Такие задачи называются NP-полными. Класс NP включает в себя класс P, а также некоторые проблемы, для решения которых известны лишь алгоритмы, экспоненциально зависящие от размера входа (то есть неэффективные для больших входов). В класс NP входят многие знаменитые проблемы, такие как задача коммивояжёра, задача выполнимости булевых формул, факторизация и др.