Теория алгоритмов вопросы к экзамену

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель _________ /Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__1__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Неформальное понятие
алгоритма. Алгоритм как формальная математи­ческая система.

2.    
Основные понятия
структурного программирования. Использование метода пошаговой детализации при
проектировании структуры программного обеспечения

3.    
Даны два натуральных числа
m и n, представленные в унарной системе счисления. Соответствующие наборы
символов «|»  разделены пустой клеткой. Автомат в состоянии q₁ обозревает
самый правый символ входной последовательности. Разработать машину Тьюринга,
которая на ленте оставит сумму чисел m и n.

Преподаватель ______________ / Максимова О.Г.

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель ________ / Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__2__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Основные требования к
алгоритмам. Формы представления алгоритмов.

2.     Понятие рекурсии. Глубина
рекурсии. Рекурсивные методы.

3.    
Дано число n в десятичной
системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное
число n на 1. Автомат в состоянии q₁ обозревает некую цифру
входного слова.

Преподаватель ______________ / Максимова О.Г

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель _________ /Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__3__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Эффективность, сходимость,
сложность, надежность алгоритмов.

2.    
Задачи поиска по критерию.
Полный перебор. Перебор с возвратом.

3.    
Дано натуральное число n
> 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на
1, при этом в выходном слове старшая цифра не должна быть 0. Автомат в
состоянии q₁ обозревает правую цифру числа.

Преподаватель ______________ / Максимова О.Г.

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель ________ / Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__4__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Машина Тьюринга. Примеры
схем машины Тьюринга.  Вычислимые по Тьюрингу функции. Основная гипотеза теории
алгоритмов

2.    
Сортировка данных
Алгоритмы внутренней и внешней сортировки.

3.    
Дано число n в
восьмеричной системе счисления. Разработать машину Тьюринга, которая
увеличивала бы заданное число n на 1. Автомат в состоянии q₁
обозревает некую цифру входного слова.

Преподаватель ______________ / Максимова О.Г.

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель _________ /Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__5__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Рекурсивные  функции, 
примитивно-рекурсивные  функции  и  операторы,  схемная интерпретация
примитивной рекурсии, частично рекурсивные и общерекурсивные функции. Тезис
Черча.

2.    
Сложность алгоритмов.
Временная сложность алгоритма. Объемная сложность алгоритма.

3.    
На ленте машины Тьюринга
находится десятичное число. Определить, делится ли это число на 5 без остатка.
Если делится, то записать справа от числа слово «да», иначе — «нет». Автомат
обозревает некую цифру входного числа.

Преподаватель ______________ / Максимова О.Г.

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель ________ / Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__6__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Нормальные алгорифмы
Маркова. Способы композиции нормальных алгорифмов Маркова

2.    
Сложность алгоритмов.
Оценка порядка. Определение сложности алгоритмов.

3.    
На ленте машины Тьюринга
находится число, записанное в десятичной системе счисления. Умножить это число
на 2. Автомат в состоянии q₁ обозревает крайнюю левую цифру
числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной
в каждом состоянии.

Преподаватель ______________ / Максимова О.Г.

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель _________ /Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__7__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Понятие эвристики.
Эвристические методы в программировании.

2.    
Абстрактные машины.
Система команд. Примеры схем машины Тьюринга.  Вычислимые по Тьюрингу функции.
Основная гипотеза теории алгоритмов

3.    
Дано число n в шестнадцатеричной
системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное
число n на 1. Автомат в состоянии q₁ обозревает некую цифру
входного слова.                                     

Преподаватель ______________ / Максимова О.Г.

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель ________ / Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__8__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Эффективность, сходимость,
сложность, надежность алгоритмов

2.    
Сортировка
данных Алгоритмы внутренней и внешней сортировки.

3.    
Дан
массив из открывающих и закрывающих скобок. Построить машину Тьюринга, которая
удаляла бы пары взаимных скобок, т.е. расположенных подряд «( )» .

Преподаватель ______________ / Максимова О.Г.

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель _________ /Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__9__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Рекурсивные  функции, 
примитивно-рекурсивные  функции  и  операторы,  схемная интерпретация
примитивной рекурсии, частично рекурсивные и общерекурсивные функции. Тезис
Черча.

2.    
Сложность алгоритмов.
Оценка порядка. Определение сложности алгоритмов.

3.    
На ленте машины Тьюринга
находится десятичное число. Определить, делится ли это число на 2 без остатка.
Если делится, то записать справа от числа слово «yes», иначе — «no».
Автомат обозревает некую цифру входного числа.

Преподаватель ______________ / Максимова О.Г.

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель ________ / Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__10__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Эффективность, сходимость,
сложность, надежность алгоритмов.

2.    
Задачи поиска по критерию.
Полный перебор. Перебор с возвратом.

3.    
Дано натуральное число n
> 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на
1, при этом в выходном слове старшая цифра не должна быть 0. Автомат в
состоянии q₁ обозревает некоторую   цифру числа.

Преподаватель ______________ / Максимова О.Г.

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель _________ /Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__11__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Неформальное понятие
алгоритма. Алгоритм как формальная математи­ческая система.

2.    
Основные понятия
структурного программирования. Использование метода пошаговой детализации при
проектировании структуры программного обеспечения

3.    
Даны два натуральных числа
m и n, представленные в унарной системе счисления. Соответствующие наборы
символов «|»  разделены пустой клеткой. Автомат в состоянии q₁ обозревает
самый правый символ входной последовательности. Разработать машину Тьюринга,
которая на ленте оставит сумму чисел m и n.

Преподаватель ______________ / Максимова О.Г.

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель ________ / Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__12__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Основные требования к
алгоритмам. Формы представления алгоритмов.

2.     Понятие рекурсии. Глубина
рекурсии. Рекурсивные методы.

3.    
Дано число n в десятичной
системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное
число n на 1. Автомат в состоянии q₁ обозревает некую цифру
входного слова.

Преподаватель ______________ / Максимова О.Г

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель _________ /Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__13__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Эффективность, сходимость,
сложность, надежность алгоритмов.

2.    
Задачи поиска по критерию.
Полный перебор. Перебор с возвратом.

3.    
Дано натуральное число n
> 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на
1, при этом в выходном слове старшая цифра не должна быть 0. Автомат в
состоянии q₁ обозревает правую цифру числа.

Преподаватель ______________ / Максимова О.Г.

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель ________ / Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__14__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Машина Тьюринга. Примеры
схем машины Тьюринга.  Вычислимые по Тьюрингу функции. Основная гипотеза теории
алгоритмов

2.    
Сортировка данных
Алгоритмы внутренней и внешней сортировки.

3.    
Дано число n в
восьмеричной системе счисления. Разработать машину Тьюринга, которая
увеличивала бы заданное число n на 1. Автомат в состоянии q₁
обозревает некую цифру входного слова.

Преподаватель ______________ / Максимова О.Г.

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель _________ /Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__15__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Рекурсивные  функции,  примитивно-рекурсивные 
функции  и  операторы,  схемная интерпретация примитивной рекурсии, частично
рекурсивные и общерекурсивные функции. Тезис Черча.

2.    
Сложность алгоритмов.
Временная сложность алгоритма. Объемная сложность алгоритма.

3.    
На ленте машины Тьюринга
находится десятичное число. Определить, делится ли это число на 5 без остатка.
Если делится, то записать справа от числа слово «да», иначе — «нет». Автомат
обозревает некую цифру входного числа.

Преподаватель ______________ / Максимова О.Г.

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель ________ / Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__16__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Нормальные алгорифмы
Маркова. Способы композиции нормальных алгорифмов Маркова

2.    
Сложность алгоритмов.
Оценка порядка. Определение сложности алгоритмов.

3.    
На ленте машины Тьюринга
находится число, записанное в десятичной системе счисления. Умножить это число
на 2. Автомат в состоянии q₁ обозревает крайнюю левую цифру
числа.

Преподаватель ______________ / Максимова О.Г.

Автономная некоммерческая
организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель _________ /Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__17__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Понятие эвристики. Эвристические
методы в программировании.

2.    
Абстрактные машины.
Система команд. Примеры схем машины Тьюринга.  Вычислимые по Тьюрингу функции.
Основная гипотеза теории алгоритмов

3.    
Дано число n в шестнадцатеричной
системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное
число n на 1. Автомат в состоянии q₁ обозревает некую цифру
входного слова.                                     

Преподаватель ______________ / Максимова О.Г.

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель ________ / Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__18__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Эффективность, сходимость,
сложность, надежность алгоритмов

2.    
Сортировка
данных Алгоритмы внутренней и внешней сортировки.

3.    
Дан
массив из открывающих и закрывающих кавычек. Построить машину Тьюринга, которая
удаляла бы пары взаимных скобок, т.е. расположенных подряд «» .

Преподаватель ______________ / Максимова О.Г.

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель _________ /Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__19__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Рекурсивные  функции, 
примитивно-рекурсивные  функции  и  операторы,  схемная интерпретация
примитивной рекурсии, частично рекурсивные и общерекурсивные функции. Тезис
Черча.

2.    
Сложность алгоритмов.
Оценка порядка. Определение сложности алгоритмов.

3.    
На ленте машины Тьюринга
находится десятичное число. Определить, делится ли это число на 2 без остатка.
Если делится, то записать справа от числа слово «ДА!», иначе — «НЕТ!». Автомат
обозревает некую цифру входного числа.

Преподаватель ______________ / Максимова О.Г.

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель ________ / Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__20__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Эффективность, сходимость,
сложность, надежность алгоритмов.

2.    
Задачи поиска по критерию.
Полный перебор. Перебор с возвратом.

3.    
Дано натуральное число n
> 1 в восьмеричной системе счисления. Разработать машину Тьюринга, которая
уменьшала бы заданное число n на 1, при этом в выходном слове старшая цифра не
должна быть 0. Автомат в состоянии q₁ обозревает некоторую   цифру
числа.

Преподаватель ______________ / Максимова
О.Г.

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель _________ /Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__21__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Неформальное понятие
алгоритма. Алгоритм как формальная математи­ческая система.

2.    
Основные понятия
структурного программирования. Использование метода пошаговой детализации при
проектировании структуры программного обеспечения

3.    
Даны два натуральных числа
m и n, представленные в унарной системе счисления. Соответствующие наборы
символов «|»  разделены пустой клеткой. Автомат в состоянии q₁ обозревает
самый некий  символ входной последовательности. Разработать машину Тьюринга,
которая на ленте оставит сумму чисел m и n.

Преподаватель ______________ / Максимова О.Г.

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель ________ / Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__22__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Основные требования к
алгоритмам. Формы представления алгоритмов.

2.     Понятие рекурсии. Глубина
рекурсии. Рекурсивные методы.

3.    
Дано число n в шестеричной
системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное
число n на 1. Автомат в состоянии q₁ обозревает некую цифру
входного слова.

Преподаватель ______________ / Максимова О.Г

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель _________ /Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__23__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Эффективность, сходимость,
сложность, надежность алгоритмов.

2.    
Задачи поиска по критерию.
Полный перебор. Перебор с возвратом.

3.    
Дано натуральное число n
> 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на
1, при этом в выходном слове старшая цифра не должна быть 0. Автомат в
состоянии q₁ обозревает левую  цифру числа.

Преподаватель ______________ / Максимова О.Г.

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель ________ / Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__24__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Машина Тьюринга. Примеры
схем машины Тьюринга.  Вычислимые по Тьюрингу функции. Основная гипотеза теории
алгоритмов

2.    
Сортировка данных
Алгоритмы внутренней и внешней сортировки.

3.    
Дано число n в пятеричной
системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное
число n на 1. Автомат в состоянии q₁ обозревает некую цифру
входного слова.

Преподаватель ______________ / Максимова О.Г.

Автономная
некоммерческая организация среднего профессионального образования

«Уральский
промышленно-экономический техникум»

 

РАССМОТРЕНО Цикловой комиссией «Информатики и программирования» Председатель _________ /Максимова О.Г. « 16 » октября 2019 г.

Специальность  09.02.03 «Программирование в компьютерных системах» Дисциплина: Теория алгоритмов ЭКЗАМЕНАЦИОННЫЙ БИЛЕТ №__25__

УТВЕРЖДАЮ Заместитель директора по учебной работе ________ / « __ » _________ 2019 г.

1.    
Рекурсивные  функции,  примитивно-рекурсивные 
функции  и  операторы,  схемная интерпретация примитивной рекурсии, частично
рекурсивные и общерекурсивные функции. Тезис Черча.

2.    
Сложность алгоритмов.
Временная сложность алгоритма. Объемная сложность алгоритма.

3.    
На ленте машины Тьюринга
находится десятичное число. Определить, делится ли это число на 5 без остатка.
Если делится, то записать справа от числа слово «YES!», иначе — «NO!».
Автомат обозревает некую цифру входного числа.

Преподаватель ______________ / Максимова О.Г.

Задание №1 (теоретическое – тест)

1. Впишите правильный ответ.

Раздел математики, в котором изучаются теоретические возможности эффективных процедур (алгоритмов) и их приложения – ___________.

2. Выберите правильный ответ.

Предложение “При точном исполнении всех команд алгоритма процесс должен прекратиться за конечное число шагов, приведя к определенному результату”, — фиксирует такое свойство алгоритма как:

1. Массовость.

2. Понятность.

3. Результативность

4. Дискретность.

5. Определенность.

3. Выберите правильные ответы.

Алгоритм обладает свойствами:

1. Дискретность.

2. Достоверность.

3. Объективность.

4. Понятность.

5. Полезность.

4. Выберите правильный ответ.

Алгоритм называется линейным,

1. если он составлен так, что его выполнение предполагает многократное повторение одних и тех же действий;
2. если ход его выполнения зависит от истинности тех или иных условий;
3. если его команды выполняются в порядке их естественного следования друг за другом независимо от каких-либо условий;
4. если он представим в табличной форме;
5. если он включает в себя вспомогательный алгоритм.

5. Выберите правильный ответ.

Алгоритм включает в себя ветвление,

1. если он составлен так, что его выполнение предполагает многократное повторение одних и тех же действий;
2. если ход его выполнения зависит от истинности тех или иных условий;
3. если его команды выполняются в порядке их естественного следования друг за другом независимо от каких-либо условий;
4. если он представим в табличной форме;
5. если он включает в себя вспомогательный алгоритм.

6. Выберите правильный ответ.

Алгоритм называется циклическим,

1. если он составлен так, что его выполнение предполагает многократное повторение одних и тех же действий;
2. если ход его выполнения зависит от истинности тех или иных условий;
3. если его команды выполняются в порядке их естественного следования друг за другом независимо от каких-либо условий;
4. если он представим в табличной форме;
5. если он включает в себя вспомогательный алгоритм.

7. Впишите правильный ответ.

Система обозначений и правил, предназначенная для единообразной записи алгоритмов – ___________ .

8. Выберите неправильный ответ.

Способы представления алгоритмов

1. Словесный.
2. Графический.
3. Линейный.
4. Псевдокод.
5. Программный.

9. Выберите правильный ответ.

Направление поиска моделей алгоритмов, связанное с системой подстановок над некоторым алфавитом, привело к созданию модели

1. Машина Поста.
2. Рекурсивные функции.
3. Нормальные алгоритмы Маркова.
4. Машина Тьюринга.
5. Примитивно-рекурсивные функции.

10. Впишите правильный ответ.

Первое направление поиска моделей алгоритмов – ____________  алгоритмов – использовало связь с традиционными понятиями математики – вычислениями и числовыми функциями.

11. Выберите правильный ответ.

Какой вид будет иметь машина Поста после выполнения указанной программы?

1. 
2. 
3. 
4. 

12. Выберите правильный ответ.

Начальное  состояние головки машины Поста:

1. Против самой левой метки на ленте.
2. Против пустой клетки левее самой левой метки на ленте.
3. Против пустой клетки правее самой правой метки на ленте.
4. Против самой правой метки на ленте.

13. Выберите правильный ответ.

На рисунке показана алгоритмическая структура:

1. Следование.  
2. Ветвление.
3. Цикл-пока.
4. Цикл-до.
5. Цикл с параметром.

14. Выберите правильный ответ.

На рисунке показана алгоритмическая структура:

1. Следование.
2. Ветвление.
3. Цикл-пока.
4. Цикл-до.
5. Цикл с параметром.

15. Выберите правильный ответ.

Какой оператор реализует данную структуру

1. while условие do серия

2. repeat … until …

3.if … then …

4. if … then …else …

5. for … to  …do …

16. Выберите правильные ответы.

Укажите номера верных предложений:

1. Вспомогательные  алгоритмы – алгоритмы, решающие одну и ту же задачу

2. Кодирование – составление текста программы на языке программирования.

3. Эквивалентные алгоритмы – алгоритмы решения подзадач

4. Рекурсивный метод – сведение задачи к самой себе.

17. Выберите правильные ответы.

Укажите номера верных предложений:

1. Технология программирования – определенный общепринятый способ создания программ.

2. Цикл — алгоритмическая альтернатива.

3. Ветвление — повторение некоторой группы действий по условию.

4. Рекурсия – определение очередного значения функции через ранее вычисленные значения этой же функции.

18. Выберите правильный ответ.

 

На рисунке показан:

1. Сборочный метод.
2. Эвристический метод.
3. Рекурсивный метод.
4. Метод последовательной детализации.
5. Метод сортировки.

19. Выберите правильный ответ.

Определите название блок-схемы:

1. Вложенные ветвления.
2. Цикл-пока с вложенным ветвлением.
3. Вложенные циклы-пока.
4. Следование ветвления и цикла-до.
5. Вложенные циклы. Внешний – цикл-пока, внутренний – цикл-до.

20. Выберите правильный ответ.

Определите название блок-схемы:

1. Вложенные ветвления.
2. Цикл-пока с вложенным ветвлением.
3. Вложенные циклы-пока.
4. Следование ветвления и цикла-до.
5. Вложенные циклы. Внешний – цикл-пока, внутренний – цикл-до.

21. Выберите правильный ответ.

Определите название блок-схемы:

1. Вложенные ветвления.
2. Цикл-пока с вложенным ветвлением.
3. Вложенные циклы-пока.
4. Следование ветвления и цикла-до.
5. Вложенные циклы. Внешний – цикл-пока, внутренний – цикл-до.

22. Впишите правильный ответ.

Какое количество тестов необходимо для отладки данного алгоритма?

23. Выберите неправильные ответы.

Фрагменты программы записаны в соответствии со структурным подходом

1. k:= 1;s:= 0;while k < 7 do k:= k + 1; s:= s + 2*k ;

2. k:= 1;

   s:= 0;

   while k < 7 do k:= k + 1;

   s:= s + 2*k ;

3. k:= 1;s:= 0;

   while k < 7 do

         k:= k + 1;

   s:= s + 2*k ;

4. k:= 1;

   s:= 0;

   while k < 7 do

         k:= k + 1;

   s:= s + 2*k ;

24. Выберите правильный ответ.

Пространственная эффективность (объемная сложность) характеризует

1. Длину входных данных.
2. Время, необходимое для выполнения программы.
3. Зависимость длины от времени.
4. Объем памяти.