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

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

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

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

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

 БІЛЕТ  № 1

1. NP-полнота задач

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

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

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

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

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

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

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

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

 БІЛЕТ  № 2

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

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

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

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

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

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

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

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

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

 БІЛЕТ  № 3

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

2.  Задана Т-программа: q₁1Rq₂, q₂1Rq₃, q₃10q₃, q₃0Rq₄, q₄10q₄. Применить  ее  к  слову : 1111111.

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

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

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

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

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

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

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

 БІЛЕТ  № 4

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

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

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

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

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

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

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

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

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

 БІЛЕТ  № 5

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

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

B	1	2	3	4	5	6	7
1	5 / 2	6 / 2	5 / 2	5 / 2	6 / 1	6 / 2	6 / 2
2	3 / 2	4 / 1	1 / 2	4 / 2	1 / 1	4 / 2	1 / 1
3	2 / 1	3 / 2	2 / 1	7 / 1	6 / 2	6 / 1	4 / 2

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

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

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

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

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

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

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

 БІЛЕТ  № 6

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

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

B	1	2	3	4	5	6	7
1	6 / 2	7 / 2	6 / 2	6 / 2	7 / 2	7 / 1	7 / 2
2	1 / 2	1 / 1	4 / 2	3 / 2	3 / 1	3 / 1	1 / 2
3	5 / 1	4 / 2	2 / 1	2 / 1	1 / 2	7 / 2	7 / 1

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

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

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

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

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

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

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

 БІЛЕТ  № 7

1. Описание работы машины Тьюринга.

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

B	1	2	3	4	5	6	7
1	7 / 2	6 / 2	7 / 2	7 / 2	6 / 2	6 / 2	6 / 1
2	1 / 2	1 / 1	4 / 2	3 / 2	4 / 1	1 / 2	4 / 1
3	5 / 1	3 / 2	2 / 1	2 / 1	1 / 2	6 / 1	6 / 2

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

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

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