Министерство образования и науки украины

ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К ВЫПОЛНЕНИЯ КУРСОВОЙ РАБОТЫ ПО КУРСУ

ТЕОРИЯ АЛГОРИТМОВ И ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ

(для студентов специальности 7.080403 «Программное обеспечение вычислительной техники и автоматизированных систем», «Компьютерный эколого-экономический мониторинг»)

Рассмотрено на заседании кафедры

Прикладной математики и информатики

Протокол № __9__ от «4»_02______2009г.

Донецк 2009

Методические указания к выполнению курсовой работы по курсу «Теория алгоритмов и вычислительных процессов» (для студентов специальностей «Программное обеспечение вычислительной техники и автоматизированных систем», «Компьютерный эколого-экономический мониторинг»)

Сост.: Коломойцева И. А., Назарова И.А.

Тема курсовой работы: «Построение аналитических моделей алгоритмов и оценка их сложности

Задание на курсовую работу:

1. Рекурсивные функции

Разработать алгоритм вычисления в виде рекурсивной функции. Проверить модель алгоритма на множестве тестовых примеров. Определить к какому классу рекурсивных функций принадлежит : примитивно-рекурсивна, частично рекурсивна или общерекурсивна.

2. Машины Тьюринга

2. 1.Описать системой команд, функциональной таблицей и диаграммой переходов работу машины Тьюринга, реализующую заданный вариантом алгоритм. Начальная и конечная конфигурации стандартны. Проверить модель алгоритма на множестве тестовых примеров. Привести последовательности конфигураций машины Тьюринга для различных тестовых исходных слов.

2.2. Построить машину Тьюринга, вычисляющую функцию из задания №1 “Рекурсивные функции”. Машину Тьюринга представить как композицию элементарных МТ, выполняющих операции: копирование аргумента, сложение, умножение, арифметическое вычитание, нахождение целой части и остатка от деления, сравнения чисел, выделение аргумента. Недостающие элементарные МТ описать любым известным способом.

2.3. Определить машину Тьюринга, распознающую заданный язык. Программно реализовать эту машину и построить график ее временной сложности T(n) (для n, требующих 3-5 мин. счета).

3. Нормальные алгоритмы Маркова

Составить нормальный алгоритм Маркова над алфавитом А. На конкретных примерах исходных слов продемонстрировать работу составленных алгоритмов.

Варианты заданий к заданию №1

1. Сумма всех делителей числа .

2. Количество делителей числа .

3. Количество нулей в двоичной записи .

4. Сумма цифр в двоичной записи .

5. Количество взаимно-простых с чисел,

6. Максимум из двух чисел и ,

7. Минимум из двух чисел и ,

8. Модуль разности двух чисел и ,

9. Максимальная цифра в 8-ричной записи числа .

10. Минимальная цифра в 8-ричной записи числа .

11. Количество четных цифр в 8-ричной записи числа .

12. Количество нечетных цифр в 8-ричной записи числа .

13. Сумма простых делителей числа .

14. Количество простых делителей числа .

15. Количество простых чисел,

16. Количество чисел, являющихся полными квадратами,

17. Сумма чисел, являющихся степенью двойки,

18. Максимальная цифра в 16-ричной записи числа .

19. Минимальная цифра в 16-ричной записи числа .

20. Ближайшее к простое число.

21. Произведение делителей числа .

22. Произведение простых делителей числа .

23. Произведение взаимно-простых с чисел,

24. Наименьшее общее кратное двух чисел, ,

25. Наибольший общий делитель двух чисел,

26. Целая часть от деления на , или .

27. Остаток от деления на ,

28. “Ступенька”: .

29. Функция, отличная от нуля в конечном числе точек.

30. Номер наибольшего простого делителя числа

31. Функция .

Варианты заданий к заданию 2.1

1. Реализовать функцию арифметическое вычитание в унарном коде.

2. Реализовать функцию выбор максимального из двух чисел над числами в унарном коде.

3. Реализовать функцию над числами в унарном коде.