Билеты № 1-32 к экзамену по дисциплине "Математическая логика и теория алгоритмов" (NP-полнота задач. Описание работы машины Тьюринга), страница 3

Затверджено  на  засіданні  кафедри інформатики (№ 304)

 Протокол №  7   від  «29 ” січня 2013 р..

Зав. кафедрою              /КАРТАШОВ О.В./     Екзаменатор        /ЧЕРНИШОВ Ю.К./

***************************************************************************

Національний аерокосмічний університет ім. М.Є.Жуковського  “ХАІ”

Спеціальність :   прикладна  математика. Ректорська перевірка знань

 групи 325,325а,420м.Учбова  дисципліна «Матем.логика и теория алгоритмов”.

 БІЛЕТ  № 22

1. Машина с неограниченными регистрами. Примеры алгоритмизации вычисления функций.

2. Дана таблица кодов: a(00), e(2), м(01), г(10), о(11), н(12), л(02). Составить автомат-декодировщик и декодировать строку: 0012110202

Затверджено  на  засіданні  кафедри інформатики (№ 304)

 Протокол №  7   від  «29 ” січня 2013 р..

Зав. кафедрою              /КАРТАШОВ О.В./     Екзаменатор        /ЧЕРНИШОВ Ю.К./

***************************************************************************

***************************************************************************

Національний аерокосмічний університет ім. М.Є.Жуковського  “ХАІ”

Спеціальність :   прикладна  математика. Ректорська перевірка знань

 групи 325,325а,420м.Учбова  дисципліна «Матем.логика и теория алгоритмов”.

 БІЛЕТ  № 16

1. Распознавание подстрок с помощью конечных автоматов.

2. Дана таблица кодов: a(00), и(2), м(01), г(10), о(11), н(12), л(02). Составить автомат-декодировщик и декодировать строку: 100221200

Затверджено  на  засіданні  кафедри інформатики (№ 304)

 Протокол №  7   від  «29 ” січня 2013 р..

Зав. кафедрою              /КАРТАШОВ О.В./     Екзаменатор        /ЧЕРНИШОВ Ю.К./

***************************************************************************

Національний аерокосмічний університет ім. М.Є.Жуковського  “ХАІ”

Спеціальність :   прикладна  математика. Ректорська перевірка знань

 групи 325,325а,420м.Учбова  дисципліна «Матем.логика и теория алгоритмов”.

 БІЛЕТ  № 26

1. Формальная теория машины Тьюринга. Структура команд

2. Лифт в пятиэтажнои доме управляется кнопками с номером этажа; выходной сигнал-«вверх», «вниз», «не двигаться». Построить автомат

Затверджено  на  засіданні  кафедри інформатики (№ 304)

 Протокол №  7   від  «29 ” січня 2013 р..

Зав. кафедрою              /КАРТАШОВ О.В./     Екзаменатор        /ЧЕРНИШОВ Ю.К./

***************************************************************************

Національний аерокосмічний університет ім. М.Є.Жуковського  “ХАІ”

Спеціальність :   прикладна  математика. Ректорська перевірка знань

 групи 325,325а,420м.Учбова  дисципліна «Матем.логика и теория алгоритмов”.

 БІЛЕТ  № 18

1. Цель работы машины Тьюринга. Примеры вычислимых по Тьюрингу функций

2. Построить автомат для поиска в тексте подстроки  «квадрат». Проверить.

Затверджено  на  засіданні  кафедри інформатики (№ 304)

 Протокол №  7   від  «29 ” січня 2013 р..

Зав. кафедрою              /КАРТАШОВ О.В./     Екзаменатор        /ЧЕРНИШОВ Ю.К./

***************************************************************************

Національний аерокосмічний університет ім. М.Є.Жуковського  “ХАІ”

Спеціальність :   прикладна  математика. Ректорська перевірка знань

 групи 325,325а,420м.Учбова  дисципліна «Матем.логика и теория алгоритмов”.

 БІЛЕТ  № 19

1. Определение конечного автомата.

2. Построить автомат для поиска в предложении подстроки  «колокол». Проверить.

Затверджено  на  засіданні  кафедри інформатики (№ 304)

 Протокол №  7   від  «29 ” січня 2013 р..

Зав. кафедрою              /КАРТАШОВ О.В./     Екзаменатор        /ЧЕРНИШОВ Ю.К./

***************************************************************************

Національний аерокосмічний університет ім. М.Є.Жуковського  “ХАІ”

Спеціальність :   прикладна  математика. Ректорська перевірка знань

 групи 325,325а,420м.Учбова  дисципліна «Матем.логика и теория алгоритмов”.

 БІЛЕТ  № 12

1.  Размеченный граф для задания автомата.

2. Задана Т-программа: q₁KBq₁, q₁BRq₂, q₂ORq₂, q₂PRq₂, q₂BHq₂, q₂HRq₂, q₂A^q₁ . Применить  ее  к  слову : KOPOBA.  Составить   Т-программу для обратного преобразования

Затверджено  на  засіданні  кафедри інформатики (№ 304)

 Протокол №  7   від  «29 ” січня 2013 р..

Зав. кафедрою              /КАРТАШОВ О.В./     Екзаменатор        /ЧЕРНИШОВ Ю.К./