АСД_Теория алгоритмов

Набор инструкций, четко описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий:

• программа

• блок

• оператор

• алгоритм

• исключение

К какому времени относят возникновение термина «алгоритм»?

• III век до н.э.

• 825 г. до н.э.

• начало ХХ века

• 1931 г.

• 1936 г.

Одним из старейших численных алгоритмов является:

• Алгоритм Прима

• Алгоритм Краскала

• Алгоритм Евклида

• Алгоритм Дейкстры

• Алгоритм Шора

Кто предложил алгоритм нахождения наибольшего общего делителя двух чисел?

• Дейкстра

• Прим

• Шор

• Евклид

• Краскал

С работы какого ученого началась современная теория алгоритмов?

• Гёдель

• Тьюринг

• Пост

• Чёрч

• Кнут

В каком году появились первые фундаментальные работы по теории алгоритмов?

• 1960

• 1950

• 1936

• 1931

• 1825

Выберите верное определение понятия «алгоритм»:

• конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность

• всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи

• точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату

• точное предписание о выполнении в определённом порядке некоторой системы операций, ведущих к решению всех задач данного типа

• все определения эквиваленты

К 1960-1970 годам в теории алгоритмов было сформировано следующее направление:

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

• теория асимптотического анализа алгоритмов

• теория практического анализа вычислительных алгоритмов

• теория нормальных алгоритмов

• все из перечисленных

К какому направлению теории алгоритмов относится формулировка задач в терминах формальных языков, понятие задачи разрешимости, введение сложностных классов, формулировка проблемы P=NP(?), открытие класса NP-полных задач и его исследование:

• теория асимптотического анализа алгоритмов

• теория практического анализа вычислительных алгоритмов

• теория нормальных алгоритмов

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

• все из перечисленных

К какому направлению теории алгоритмов относится понятие сложности и трудоёмкости алгоритма, критерии оценки алгоритмов, методы получения асимптотических оценок, в частности для рекурсивных алгоритмов, асимптотический анализ трудоемкости или времени выполнения:

• > все из перечисленных

• теория асимптотического анализа алгоритмов

• теория практического анализа вычислительных алгоритмов

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

• теория нормальных алгоритмов