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

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

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

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

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

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

Задания:
1. Разработайте рекурсивную функцию, подсчитывающую количество способов разбиения выпуклого многоугольника на треугольники непересекающимися диагоналями.
2. В Фибоначчиевой системе счисления числа формируются по правилам.
o Используются только символы 0 и 1;
o Каждый разряд соответствует элементу последовательности Фибоначчи 1, 2, 3, 5, 8, …, то есть указывает на наличие или отсутствие такового;
o В соседних разрядах не могут стоять символы 1, так как это автоматически означает формирование следующего за ними разряда. Например, 17₁₀ = 13₁₀ + 3₁₀ + 1₁₀ = 100101_ф.
Составьте программу перевода числа из десятичной системы в Фибоначчиевую. Считать входные данные введенными корректно.
3. Найдите походящие дроби рационального числа x/y ( x – неотрицательно, y – положительно). Например,
, то есть для х = 5, y = 6 ответом будет последовательность [0; 1, 5].
4. Вычислите определитель квадратной матрицы размера nxn.
5. Провести анализ и оценку сложности алгоритма.

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

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