Структуры и алгоритмы компьютерной обработки данных Петухин Вячеслав Алексеевич 1 семестр, 17 часов лекций, 17 часов лабораторных.
Литература Ахо, Хопкропфт, Ульман. Построение и анализ вычислительных алгоритмов. 1979
Сложность алгоритмов Функция сложности f(x) Для любых входных данных размером не более чем x время работы алгоритма не больше чем f(x) Классы сложности: полиномиальные экспоненциальные
Классы сложности Вычислительные устройства: Машина Тьюринга и эквивалентные ей устройства Недетерминированная машина Тьюринга Класс NP-сложных задач.
Структуры данных и алгоритмы Массив – итеративные алгоритмы Рекурсивные структуры данных (списки, деревья и т.д.) – рекурсия Язык программирования Паскаль
Алгоритмы сортировки Квадратичной сложности: Выборкой максимального Метод пузырька Быстрая сортировка (quicksort) Оптимальные алгоритмы O(n log 2 n) С помощью двоичного дерева