теория алгоритмов задания



Задания для самостоятельной работы учащихся по дисциплине «Теория алгоритмов»

Раздел 1. Основные понятия теории алгоритмов

Составить презентацию об истории развития теории алгоритмов

Конспект по теме «Формальные системы»

[1], [6], [5]

Раздел 2. Конечные автоматы

Конспект и презентация:

«Двухвходовый триггер»

«Конечные и бесконечные машины»

Реферат по темам:

«Компьютер фон Неймана»

«Исследования М.Л. Цетлина»

[4], [3], [5]

Раздел 3.

Индивидуальная домашняя работа по теме «Машина Поста» (Приложение 1)

Презентация по теме «Доказательство теоремы о самоприменимости с привлечением машины Тьюринга»

[1], [2], [5]

Раздел 4. Теория сложности вычислений

Конспект тем:

Доказательство правильности программ

Доказательное программирование

Рефераты по темам:

Поисковые серверы

Алгоритмы работы поисковых машин

Алгоритмы формирования базы указателей

Хеширование

Проектная работа по теме «Культурное значение формализации понятия алгоритма»

[1], [2], [6], [4]

Литература:

Андреева Е.В., Математические основы информатики

В.И. Игошин «Задачи и упражнения по математической логике и теории алгоритмов»

Ю.М. Келим «Вычислительная техника»

М.С. Спирина, П.А. Спирин «Дискретная математика»



Мальцев Г.Н. Конспект лекций по курсу «Теория алгоритмов»

Канцедал С.А. Дискретная математика: учебное пособие

Кузин А.В. Жаворонков М.А. Микропроцессорная техника



Приложение 1

Индивидуальная домашняя работа по теме «Машина Поста»

На ленте имеется массив из n ячеек. Составьте для машины Поста программу, копирующую массив и записывающую его через пустую ячейку справа. Каретка стоит на самой левой метке, входящей в число (copy.pst)

На ленте расположен массив, состоящий из нечетного количества идущих подряд меток. Каретка стоит у самой левой метки массива. Составьте для машины Поста программу для нахождения средней метки массива и ее удаления.(middle. pst)

На ленте записаны два числа как цепочки идущих подряд меток. Числа разделены одной пустой ячейкой, над ней находится каретка. Число справа от каретки больше числа слева от каретки. Составьте для машины Поста программу для нахождения разности «правого» числа и «левого».minus.pst



Составьте для машины Поста программу умножения числа, представленного в виде цепочки идущих подряд меток, на 2. Каретка находится на первом знаке числа.(mult2.pst)

Составьте для машины Поста программу для сложения двух чисел, записанных виде цепочки идущих подряд меток. Числа расположены на неизвестном расстоянии друг от друга. Каретка находится над левой границей первого (левого) числа. (plus_dist.pst)

Составьте для машины Поста программу сложения нескольких натуральных чисел. Каждое число кодируется как последовательность расположенных рядом отметок. Числа отделены друг от друга пробелами. Каретка находится справа от первого числа.(plusN.pst)

На ленте располагается группа меток, отделенных друг от друга пустыми секциями (V_V_V_V_V). Написать программу для машины Поста, которая «уплотнит» метки таким образом, чтобы самая левая из них осталась на месте. Каретка расположена над самой левой меткой.(uplotnenie.pst)








sitemap
sitemap