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

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

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

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

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

 БІЛЕТ  № 8

1. Алгоритмы сложения и перемножения многочленов.

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

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

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

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

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

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

 БІЛЕТ  № 9

1. Табличное задание конечного автомата.

2. Сократить произведение дробей: 19858609 / 36853543 и 14437751 / 4508627.

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

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

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

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

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

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

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

 БІЛЕТ  № 10

1. Классификация состояний автомата: преходящие, тупиковые, изолированные.

2. Сократить произведение дробей: 158416301 / 527487523 и 353533093 / 135463357.

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

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

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

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

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

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

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

 БІЛЕТ  № 11

1. Внешнее поведение автомата. Автоматность отображения.

2. Сократить произведение дробей: 52839667 / 320693027 и 219422741 / 66724543.

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

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

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

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

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

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

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

 БІЛЕТ  № 17

1. Задача проверки четности. Эквивалентные автоматы.

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

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

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

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

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

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

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

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

 БІЛЕТ  № 13

1. Соизмеримость отрезков. Алгоритм Евклида.

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

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

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

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

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

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

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

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

 БІЛЕТ  № 20

1. Автомат Мура. Графическое и табличное описание автомата Мура

2. Построить автомат, который после прочтения слова из нулей и единиц после каждой тройки битов записывал бы символ «а», если сумма единиц в тройке четна, и символ «б» - если эта сумма нечетна