Структуры и алгоритмы компьютерной обработки данных Петухин Вячеслав Алексеевич 1 семестр, 17 часов лекций, 17 часов лабораторных. - презентация

1 Структуры и алгоритмы компьютерной обработки данных Петухин Вячеслав Алексеевич 1 семестр, 17 часов лекций, 17 часов лабораторных.

2 Литература Ахо, Хопкропфт, Ульман. Построение и анализ вычислительных алгоритмов. 1979

3 Сложность алгоритмов Функция сложности f(x) Для любых входных данных размером не более чем x время работы алгоритма не больше чем f(x) Классы сложности: полиномиальные экспоненциальные

4 Классы сложности Вычислительные устройства: Машина Тьюринга и эквивалентные ей устройства Недетерминированная машина Тьюринга Класс NP-сложных задач.

5 Структуры данных и алгоритмы Массив – итеративные алгоритмы Рекурсивные структуры данных (списки, деревья и т.д.) – рекурсия Язык программирования Паскаль

6 Алгоритмы сортировки Квадратичной сложности: Выборкой максимального Метод пузырька Быстрая сортировка (quicksort) Оптимальные алгоритмы O(n log 2 n) С помощью двоичного дерева