Контрольные вопросы
1. Назовите основные виды универсальных алгоритмических моделей.
2. Что представляет собой первая алгоритмическая модель?
3. В чем заключается преобразование слов в произвольных абстрактных алфавитах?
4. Что такое алфавитный оператор?
5. Дайте различные определения алгоритма на основе первой алгоритмической модели.
6. Какие алгоритмы являются равными, а какие – эквивалентными?
7. Определите вторую алгоритмическую модель.
8. Каким образом строятся рекурсивные алгоритмы?
9. Что такое алгоритмы, сопутствующие рекурсивным функциям?
10. Что такое рекурсивные и частично рекурсивные функции?
11. Определите операторы суперпозиции, подстановки и рекурсии.
12. Сформулируйте тезис Черча.
13. В чем заключается метод «разделяй и властвуй»?
14. Постройте третью алгоритмическую модель
15. Опишите принцип работы машины Тьюринга.
16. Приведите правила построения алгоритмов Ван-Хао.
17. Приведите основные правила построения логических схем алгоритмов (ЛСА).
18. В чем заключаются правила построения алгоритмов Маркова?
19. Определите основную идею графических схем алгоритмов (ГСА).
20. Приведите основные правила построения структурных схем алгоритмов.
21. В чем основная идея словесного описания алгоритма?
22. Что представляют собой «жадные» алгоритмы?
23. Для каких задач целесообразно применять «жадные» алгоритмы?
24. Дайте определение нечеткого (расплывчатого) алгоритма.
25. Что такое расплывчатая и лингвистическая переменные?
Задания для самостоятельной работы
Постройте пример первой алгоритмической модели.
Постройте пример второй алгоритмической модели.
Постройте пример третьей алгоритмической модели.
4. Запишите словесный алгоритм упорядочивания массива из n чисел в порядке возрастания.
5. Запишите словесный алгоритм для вычисления среднего арифметического и наибольшего значений элементов массива целых чисел размерностью до 70.
6. Запишите алгоритм Ван-Хао для вычисления среднего арифметического значения элементов массива чисел размерностью до 20.
7. Составить словесный алгоритм определения элементов множества Z, если Z = X \ Y, где X, Y - множества (|X| = N, |Y| = M).
8. Составить ЛСА поиска наибольшего элемента массива Aij, где i = 1, 2, ...,10; j = 1, 2, ..., 20.
9. Составить ГСА вычисления по формуле K!
10. Составить ГСА нахождения одинаковых чисел в одномерном массиве длины n.
11.
Запишите ГСА
вычисления по формуле:
.
12.
Составить структурную схему алгоритма
вычисления по формуле:
.
13.
Составить ЛСА
вычисления по формуле:
.
14.
Составить структурную схему алгоритма
вычисления по формуле:
,
где
.
15.
Составить ЛСА
алгоритма вычисления по формуле:
.
16. Составьте логическую схему алгоритма сортировки для массива А = (3, 41, 52, 26, 38, 57, 9, 49).
17. Приведите пример использования «жадного» алгоритма для решения задачи нахождения наибольшего числа в массиве А = (13, 41, 89, 26, 38, 57, 9, 49).
18. Составьте нечеткий алгоритм перехода перекрестка с односторонним движением.
19. Составьте нечеткий алгоритм перехода перекрестка с двусторонним движением.
Модель – это копия или аналог изучаемого явления или процесса, отражающая существенные свойства моделируемого объекта с точки зрения исследователя. Математическая модель – это приближенное описание какого-либо класса явлений внешнего мира, выраженное с помощью математической символики. Использование таких моделей позволяет строить эффективные схемы алгоритмов.
Глава 11. Сложность алгоритмов
Не рассуждайте о том, почему происходит какое-то явление – описывайте его количественно.
Галилей
Временная сложность алгоритма, полиномиальные и экспоненциальные алгоритмы, анализ алгоритмов
ЦЕЛИ
Освоив эту главу, учащиеся должны уметь и знать:
определять временную сложность алгоритмов;
определять полиномиальные и экспоненциальные алгоритмы;
анализировать алгоритмы.