Гбоу спо «Осташковский техникум»

Рассмотрено предметной комиссией 15 ноября 2013 г. Председатель: ____________Суркова М.В.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 5 По предмету: Теория алгоритмов Специальность: 230115 Курс: III группа: 36-П

«УТВЕРЖДЕНО» Зам.директора по учебной работе: __________ Потоцкая Е.А. 16 ноября 2013 г.

1. Машина Тьюринга.

2. Методы сортировки данных: сортировка методом пузырька.

3. В алгоритмах Маркова дана система подстановок в алфавите А={a, b, c}:

abc – c

ba – cb

ca – ab

Преобразуйте с помощью этой системы слово bacaabc:

1. cbc

2. ccbcbbc

3. cbacba

4. cbabc

Преподаватель: Суркова М.В.

Гбоу спо «Осташковский техникум»

Рассмотрено предметной комиссией 15 ноября 2013 г. Председатель: ____________Суркова М.В.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 6 По предмету: Теория алгоритмов Специальность: 230115 Курс: III группа: 36-П

«УТВЕРЖДЕНО» Зам.директора по учебной работе: __________ Потоцкая Е.А. 16 ноября 2013 г.

1. Нормальные алгоритмы Маркова.

2. Методы сортировки данных: линейная сортировка (сортировка отбором).

3. В алгоритмах Маркова дана система подстановок в алфавите А={a, b, c}:

cb – abc

bac – ac

cab – b

Преобразуйте с помощью этой системы слово bacaabc:

1. ccb

2. cab

3. cbc

4. bcaab

Преподаватель: Суркова М.В.

Гбоу спо «Осташковский техникум»

Рассмотрено предметной комиссией 15 ноября 2013 г. Председатель: ____________Суркова М.В.

ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ № 7 По предмету: Теория алгоритмов Специальность: 230115 Курс: III группа: 36-П

«УТВЕРЖДЕНО» Зам.директора по учебной работе: __________ Потоцкая Е.А. 16 ноября 2013 г.

1. Модели вычислений: эквивалентность различных теорий алгоритмов.

2. Методы перебора: метод ветвей и границ.

3. Способ композиции нормальных алгоритмов будет суперпозицией, если:

   1. выходное слово первого алгоритма является входным для второго;

   2. существует алгоритм С, преобразующий любое слово p, содержащееся в пересечении областей определения алгоритмов А и В;

   3. алгоритм D будет суперпозицией трех алгоритмов А В С, причем область определения D является пересечением областей определения алгоритмов А В и С, а для любого слова р из этого пересечения D(р)=A(p), если С(р)=е, D(р)=В(p), если С(р)=е, где е – пустая строка;

   4. существует алгоритм С, являющийся суперпозицией алгоритмов А и В, такой, что для любого входного слова р С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В.

Преподаватель: Суркова М.В.