ПРАКТИЧЕСКАЯ РАБОТА №2

Практическая работа №2 (2 часа)

Тема: «Оценка сложности алгоритмов поиска»

Цель: Изучить алгоритмы линейного и двоичного поиска, провести исследование временных характеристик, сравнить полученные результаты.

Задачи:
1.                ппп
2.
Формируемые компетенции: ПК 1.1., ОК 1-10.
Материально-техническое обеспечение: доска, учебники, сборник практических работ, комплект нормативных документов; классификация объектов технического регулирования, Общероссийский классификатор стандартов (ОКС), приложение 2-3.
Обеспечивающие средства: компьютеры, совместимые с IBM PC.

Ход работы:
1.                   Проверка готовности к ПР: тестирование
2.                   Выполнение заданий
3.                   Заполнение отчета

Задания:
1.        Написать программы работы алгоритмов оптимального и неоптимального, последовательного поиска для неупорядоченного массива с оценкой временных характеристик
2.        Написать программы работы алгоритмов последовательного оптимального и бинарного (оптимального и неоптимального) поиска в упорядоченном массиве с оценкой временных характеристик.
3.        Для проведения исследований временных характеристик написать программный код формирования одномерного массива, содержащего заданное количество различных элементов целого типа.
Структура программы должна включать 6 функций (две последовательного поиска для неупорядоченного массива, последовательного оптимального поиска в упорядоченном массиве две бинарного поиска, сортировки массива). Массив передается в функцию в качестве параметра
4.       Провести анализ и оценку временной сложности алгоритма.

Технология выполнения задания 1.
1.Прочитайте внимательно задание
2. Выполните задание 1-4.

Контрольные вопросы
1.     Каково среднее количество сравнений при поиске в неупорядоченном массиве: если поиск неудачен, если поиск удачен?
2.     Каково среднее количество сравнений при поиске в упорядоченном массиве: если поиск неудачен, если поиск удачен?
3.     Каково среднее количество сравнений для алгоритма бинарного поиска, если поиск удачен?
4.     Каково число сравнений для алгоритма бинарного поиска, если поиск неудачен?
5.     В чем отличие алгоритма бинарного поиска от алгоритма оптимального бинарного поиска?

Форма отчетности: работа, оформленная на листах формата А4, устная защита
1.                Название и цель работы.
2.                Схемы всех исследуемых алгоритмов в соответствии с ГОСТ 19.701-90 (ИСО 5807-85).
3.                Теоретические оценки исследуемых алгоритмов.
4.                Таблица сравнительных характеристик работы алгоритмов для различных по размеру массивов данных (не менее 10 различных размеров от 10 до 100000) в худшем, лучшем и среднем случае расположения ключа.
5.                Выводы по работе.
6.                При сдаче работы требуется демонстрация работы всех алгоритмов с выводом результатов и времени работы.