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

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

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

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

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

 БІЛЕТ  № 21

1. Достижимость. Классы достижимости.

2.  Составить Т – программу для преобразования слова «голова» в слово «нога».

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

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

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

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

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

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

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

 БІЛЕТ  № 29

1. Гомоморфность автоматов. Изоморфизм автоматов

2.  Составить Т-программу,  преобразующую  слово аааааа в слово ааааааа.

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

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

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

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

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

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

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

 БІЛЕТ  № 23

1. Задача минимизации автоматов.

2. Составить Т-программу,  преобразующую  слово 222 в слово 2222.

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

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

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

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

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

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

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

 БІЛЕТ  № 24

1. Автономный автомат. Периоды в выходной цепочке автономного автомата

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

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

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

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

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

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

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

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

 БІЛЕТ  № 14

1. Машина с неограниченными регистрами. Набор основных операций.

2. Сократить произведение дробей:

10109609/139335181 и 71776157/10660327 .

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

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

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

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

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

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

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

 БІЛЕТ  № 27

 1. Аксиоматическое определение функций и операций формальной теории рекурсий

2.  Сократить произведение дробей:

103207991/182564747 и 181004023/102967693 .

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

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

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

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

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

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

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

 БІЛЕТ  № 28

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

2. Минимизировать автомат: