Математика \ Математическая логика и теория алгоритмов

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

Страницы работы

7 страниц (Word-файл)
Скачать файл

Содержание работы

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

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

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

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

 БІЛЕТ  № 1

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

2.  Задана Т-программа: q1KBq1, q1BRq2, q2ORq2, q2PRq2, q2BHq2, q2HRq2, q2A^q1 . Применить  ее  к  слову : KOPOBA.  Составить   Т-программу для обратного преобразования

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

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

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

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

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

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

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

 БІЛЕТ  № 2

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

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

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

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

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

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

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

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

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

 БІЛЕТ  № 3

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

2.  Задана Т-программа: q11Rq2, q21Rq3, q310q3, q30Rq4, q410q4. Применить  ее  к  слову : 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 р..

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

Похожие материалы

Информация о работе

ВУЗ:
Национальный аэрокосмический университет имени Н. Е. Жуковского (ХАИ)
Предмет:
Математическая логика и теория алгоритмов
Тип:
Экзаменационные вопросы и билеты
Категория:
Математика (Естествознание)
Размер файла:
125 Kb
Скачали:
0
Скачать файл