Задания к контрольной работе по дисциплине «Теория алгоритмов»

ЗАДАНИЯ К КОНТРОЛЬНОЙ РАБОТЕ

ПО ДИСЦИПЛИНЕ

«Теория алгоритмов»

ДЛЯ СТУДЕНТОВ ЗФО

НАПРАВЛЕНИЯ 230700.62 – Прикладная информатика

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ К ВЫПОЛНЕНИЮ

КОНТРОЛЬНОЙ РАБОТЫ ПО ДИСЦИПЛИНЕ

«Теория алгоритмов»

Правила оформления контрольных работ

Письменная контрольная работа студента является одной из форм контроля учебного процесса. Ее назначение - показать и доказать, что автор владеет научным материалом и может объяснять полученные научные данные. При этом студент должен проявить: умение самостоятельно собирать материал, анализировать его и делать выводы;

умение подбирать специальную литературу и другие источники, критически осмысливать их в сравнении с собственными данными; умение прилежно и грамотно оформить свой труд. Темы письменных работ разрабатываются преподавателем и выбирается студентом по последней цифре зачетной книжки. При этом их тематика самовольно изменяться не может. Содержание выполненной работы должно строго соответствовать заявленной теме.

Общие требования к оформлению

Оформление заслуживает особого внимания со стороны студента. Работа должна быть выполнена в соответствии с требованиями Госстандарта.

Чистовой вариант работы выполняют в одном экземпляре, на белой бумаге форматом стандартного листа (формат А-4, 210 х 297 мм). Работа предоставляется в печатном варианте, на одной стороне листа. Приемлема печать черного цвета, шрифтом размером 14, предпочтительнее Times New Roman, обычным начертанием и с обычным буквенным интервалом.

Весь текст набирается через полуторный междустрочный интервал. На каждой странице следует оставлять поля: левое – 30 мм; правое – 20 мм; верхнее – 15-20 мм; нижнее – 20-25 мм.

Все страницы работы нумеруются по порядку. Первой страницей считается титульный лист, на котором цифра «1» не проставляется*. На следующей странице (оглавление) ставится цифра «2» и т. д. Номер страницы рекомендуется проставлять в середине верхнего поля

Оформление библиографического списка

Все источники, на которые ссылается автор, включаются в Список литературы. Литературные источники приводятся в алфавитном порядке по фамилии автора или заглавной букве названия, если это сборник статей.

Образцы оформления списка литературы

1. Фамилия, инициалы автора. Основной заголовок работы. Место издания: Издательство, Год издания. - Количество страниц. Петрухин : время реформ.- Г.: Наука, 1990. – 167с.

2. Основной заголовок. /Фамилия инициалы Автора 1, Фамилия инициалы Автора 2, Фамилия инициалы Автора 3, Фамилия инициалы Автора 4 и др. Место издания: Издательство, Год издания. - Количество страниц.

ВАРИАНТЫ КОНТРОЛЬНЫХ РАБОТ

Вариант 1

1.  Проблема алгоритмической разрешимости в математике.

2.  Основатели теории алгоритмов – Клини, Черч, Пост, Тьюринг.

Выбери правильный ответ

3.  Команда машины Поста имеет структуру nKm, где:

n - действие, выполняемое головкой; K - номер следующей команды, подлежащей выполнению; m - порядковый номер команды n - порядковый номер команды; K - действие, выполняемое головкой;m - номер следующей команды, подлежащей выполнению выполнению; m - действие, выполняемое головкой n - порядковый номер команды; K - действие, выполняемое головкой; m - номер клетки, с которой данную команду надо произвести

Вариант 2

Основные определения и теоремы теории рекурсивных функций Тезис Черча.

Выберите правильный ответ

Способ композиции нормальных алгоритмов будет суперпозицией, если:

Существует алгоритм С, преобразующий любое слово р, содержащееся в пересечении областей определения алгоритмов А и В Выходное слово первого алгоритма является входным для второго Алгоритм D будет суперпозицией трех алгоритмов ABC, причем область определения D является пересечением областей определения алгоритмов A B и C, а для любого слова р из этого пересечения D(p)= A(p), C(p)=e, D(p)=B(p), если C(p)=е, где е - пустая строка Существует алгоритм С, являющийся суперпозицией алгоритмов А и Д такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

Вариант 3

Проблемы вычислимости в математической логике. Машина Поста. Машина Тьюринга. Нормальные алгоритмы Маркова и ассоциативные исчисления в исследованиях по искусственному интеллекту.

Выбери правильный ответ

В машине Поста останов будет результативным:

При выполнении недопустимой команды Если результат выполнения программы такой, какой и ожидался По команде "Стоп"

Вариант 4

Неформальные аксиоматические теории Формальные аксиоматические теории

Выбери правильный ответ

В ассоциативном исчислении два слова называются смежными:

Если одно из них может быть преобразовано в другое применением подстановок Когда существует цепочка от одного слова к другому и обратно Если одно из них может быть преобразовано в другое однократным применением допустимой подстановки

Вариант 5

Неразрешимые алгоритмические проблемы Свойства аксиоматических теорий

Выбери правильный ответ

В алгоритме Маркова дана цепочка Р Р1, Р2,..., Рn. Если слова Р1, Р2,..., Рn смежные, то цепочка называется:

Ассоциативной Эквивалентной Индуктивной Дедуктивной

Вариант 6

1.  Интуитивное представление об алгоритмах. Неформальное понятие алгоритма.

2.  Свойства алгоритмов

Выбери правильный ответ

3.  В машине Поста некорректным алгоритм будет в следующем случае:

При выполнении недопустимой команды Результат выполнения программы такой, какой и ожидался Машина не останавливается никогда По команде "Стоп"

Вариант 7

Тьюрингов подход к понятию «алгоритм». Алгоритмически разрешимые и неразрешимые проблемы. Рекурсивные функции. Тезис Черча.

Выбери правильный ответ

В машине Тьюринга предписание L для лентопротяжного механизма означает:

Переместить ленту вправо Переместить ленту влево Остановить машину Занести в ячейку символ

Вариант 8

Вычислимые по Тьюрингу функции. Основная гипотеза теории алгоритмов. Машины Тьюринга и современные ЭВМ. Конструирование машин Тьюринга.

Выбери правильный ответ

В машине Тьюринга предписание R для лентопротяжного механизма означает:

Переместить ленту вправо Переместить ленту влево Остановить машину Занести в ячейку символ

Вариант 9

Примеры алгоритмической неразрешимости Виды алгоритмов, их свойства. Блок-схема. Алгоритмизация при решении задач.

Выбери правильный ответ

В машине Тьюринга предписание S для лентопротяжного механизма означает:

Переместить ленту вправо Переместить ленту влево Остановить машину Занести в ячейку символ

Вариант 0

1.  Теорема о неподвижной точке. Общее понятие исчисления. Грамматики.

2.  Оценка эффективности и сложности алгоритмов

Выбери правильный ответ

3.  В алгоритме Маркова ассоциативным исчислением называется:

Совокупность всех слов в данном алфавите Совокупность всех допустимых подстановок Совокупность всех слов в данном алфавите вместе с допустимой системой подстановок Когда все слова в алфавите являются смежными