Точный набор инструкций описывающих последовательность действий некоторого исполнителя

Главная / Программирование /
Введение в алгоритмы / Тест 1

Упражнение 1:

Номер 1

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

Ответ:

(1) правило 

(2) алгоритм 

(3) структура 

Номер 2

К свойствам алгоритмических процессов следует отнести

Ответ:

(1) дискретность 

(2) детерминированность 

(3) адаптивность 

Номер 3

Алгоритмические процессы являются

Ответ:

(1) потенциально конечными 

(2) аддитивными 

(3) дискретными 

Упражнение 2:

Номер 1

У разных реализаций одного и того же алгоритма должен быть

Ответ:

(1) терминальный граф 

(2) изоморфный граф 

(3) контекстный граф 

Номер 2

Алгоритмы, вызывающие сами себя до тех пор, пока не будет достигнуто некоторое условие возвращения, носят название

Ответ:

(1) циклические 

(2) рекурсивные 

(3) коммутативные 

Номер 3

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

Ответ:

(1) параллельные 

(2) маркированные 

(3) модульные 

Упражнение 3:

Номер 1

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

Ответ:

(1) аддитивный алгоритм 

(2) адаптивный алгоритм 

(3) априорный алгоритм 

Номер 2

Какой тип алгоритмов применяют при сжатии без потерь?

Ответ:

(1) адаптивный 

(2) когнитивный 

(3) деструктивный 

Номер 3

Алгоритм Хаффмана является

Ответ:

(1) вариативным 

(2) адаптивным 

(3) рекуррентным 

Упражнение 4:

Номер 1

Алгоритм для нахождения наибольшего общего делителя двух целых чисел носит название?

Ответ:

(1) алгоритм Диффи-Хеллмана 

(2) алгоритм Коши 

(3) алгоритм Евклида 

Номер 2

Алгоритм для нахождения наибольшей общей меры двух однородных величин носит название

Ответ:

(1) алгоритм Крамера 

(2) алгоритм Евклида 

(3) алгоритм Марка 

Номер 3

Что представляет собой соотношение Безу?

Ответ:

(1) наименьшее общее кратное 

(2) наибольший общий делитель 

(3) наибольшее общее кратное 

Упражнение 5:

Номер 1

К задачам теории алгоритмов относят

Ответ:

(1) формальное доказательство алгоритмической неразрешимости задач 

(2) асимптотический анализ сложности алгоритмов 

(3) классификацию алгоритмов в соответствии с классами сложности 

Номер 2

К ветвям теории алгоритмов следует отнести

Ответ:

(1) классическую теорию алгоритмов 

(2) теорию асимптотического анализа алгоритмов 

(3) теорию практического анализа вычислительных алгоритмов 

Номер 3

Оценка функции трудоёмкости алгоритма называется

Ответ:

(1) степенью 

(2) глубиной 

(3) сложностью 

Упражнение 6:

Номер 1

Машина Тьюринга является

Ответ:

(1) терминальной вычислительной машиной 

(2) абстрактной вычислительной машиной 

(3) комплексной вычислительной машиной 

Номер 2

Машина Тьюринга является расширением

Ответ:

(1) терминального автомата 

(2) аддитивного автомата 

(3) конечного автомата 

Номер 3

Управляющее устройство машины Тьюринга работает согласно:

Ответ:

(1) правилам аддитивности 

(2) правилам перехода 

(3) правилам модульности 

Упражнение 7:

Номер 1

Если каждой комбинации состояния и ленточного символа в таблице соответствует правило, машина Тьюринга называется

Ответ:

(1) априорной 

(2) комплексной 

(3) детерминированной 

Номер 2

На Машине Тьюринга можно имитировать

Ответ:

(1) аддитивный алгоритм Лагранжа 

(2) машину Поста 

(3) нормальные алгоритмы Маркова 

Номер 3

Исполнители, для которых возможна имитация машины Тьюринга, называются

Ответ:

(1) полными по Тьюрингу 

(2) универсальными по Тьюрингу 

(3) статическими по Тьюрингу 

Упражнение 8:

Номер 1

Тезис Чёрча - Тьюринга гласит, что любая интуитивно вычислимая функция является

Ответ:

(1) невычислимой 

(2) частично вычислимой 

(3) абсолютно вычислимой 

Номер 2

Физический тезис Чёрча - Тьюринга гласит, что любая функция, которая может быть вычислена физическим устройством, может быть вычислена

Ответ:

(1) алгоритмом Коши 

(2) машиной Тьюринга 

(3) с помощью ряда Эйлера 

Номер 3

Положение о том, что любая интуитивно вычислимая функция является частично вычислимой, лежит в основе

Ответ:

(1) теоремы Кронекера 

(2) тезиса Чёрча — Тьюринга 

(3) аксиомы Гёделя 

Упражнение 9:

Номер 1

Непустое множество дискретной природы носит название

Ответ:

(1) контейнер 

(2) алфавит 

(3) модуль 

Номер 2

Элементы алфавита называют

Ответ:

(1) символами 

(2) маркерами 

(3) идентификаторами 

Номер 3

Любой конечный упорядоченный набор символов из данного алфавита носит название

Ответ:

(1) строка 

(2) слово 

(3) модуль 

Упражнение 10:

Номер 1

Число символов в слове называют

Ответ:

(1) величиной 

(2) размером 

(3) длиной 

Номер 2

Слово длины 0 называется

Ответ:

(1) пустым 

(2) априорным 

(3) модульным 

Номер 3

Множество всех слов в алфавите с операцией конкатенации образует

Ответ:

(1) полипоид 

(2) моноид 

(3) аксоид 

Источник

http://profbeckman.narod.ru/

Профессор

Игорь Н. Бекман

КОМПЬЮТЕРНЫЕ НАУКИ

Курс лекций

Лекция 7. АЛГОРИТМЫ

Содержание

1

1.1

Определение понятий

1

1.2

История термина

4

1.3

Виды алгоритмов

6

1.3

Исполнитель алгоритмов

7

1.4

Алгоритмический язык

9

2. ТЕОРИЯ АЛГОРИТМОВ

11

2.1

Возникновение теории алгоритмов

11

2.2

Анализ трудоёмкости алгоритмов

12

2.3

Объекты алгоритмов

13

2.4

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

14

2.5

Машина Поста

16

2.6

Алгоритмически неразрешимые задачи и вычислимые функции

16

2.7

Понятие сложности алгоритма

17

2.8

Анализ алгоритмов поиска

18

3. АЛГОРИТМЫ В КОМПЬЮТЕРЕ

20

Теория алгоритмов – одно из основных понятий математики и информатики. Даже происхождение самого термина «алгоритм» связано с математикой. Известно, что основная особенность всех вычислений машины состоит в том, что в основе её работы лежит программный принцип управления. Это означает, что для решения как самой простой, так и самой сложной задачи пользователю необходимо использовать перечень инструкций или команд, следуя которым шаг за шагом компьютер выдаст необходимый результат. Таким образом, для того, чтобы решать задачу на компьютере, её необходимо сначала алгоритмизировать. Именно алгоритмический принцип и лежит в основе работы всех компьютеров.

В данной лекции дадим определение термина алгоритм, рассмотрим историю его развития, виды алгоритмов и алгоритмические языки. Далее мы более подробно остановимся на теории алгоритмов и закончим применением алгоритмов в компьютере.

1. АЛГОРИТМ

1.1Определение понятий

Встарой трактовке алгори́тм— точный набор инструкций, описывающих последовательность действий исполнителя для достижения результата решения задачи за конечное время. По мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что какие-то действия алгоритма должны быть выполнены только друг за другом, но какие-то могут быть и независимыми. Часто в качестве исполнителя выступает некоторый механизм (компьютер, токарный станок, швейная машина), но понятие алгоритма необязательно относится к компьютерным программам, так, например, чётко описанный рецепт приготовления блюда также является алгоритмом, в таком случае исполнителем является человек.

Единого «истинного» определения понятия «алгоритм» нет.

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

Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд.

http://profbeckman.narod.ru/

Алгоритм — последовательность действий, направленных на получение определённого результата за конечное число шагов».

Алгоритм — последовательность действий, либо приводящая к решению задачи, либо поясняющая почему это решение получить нельзя.

Алгоритм — это точная, однозначная, конечная последовательность действий, которую должен выполнить пользователь для достижения конкретной цели либо для решения конкретной задачи или группы задач за конечное число шагов.

Общее в этих определениях то, что алгоритм — это предписание. Предписание должно быть задано (закодировано) в некоторой форме. Это может быть текст — строка символов в некотором алфавите, таблица, диаграмма, упорядоченный набор пиктограмм и т.д.

Любой алгоритм существует не сам по себе, а предназначен для определённого исполнителя. Алгоритм описывается в командах исполнителя, который это алгоритм будет выполнять. Объекты, над которыми исполнитель может совершать действия, образуют среду исполнителя. Исходные данные и результаты любого алгоритма всегда принадлежат среде того исполнителя, для которого предназначен алгоритм.

Значение слова «алгоритм»очень схоже со значением слов «рецепт», «метод», способ. Однако любой алгоритм, в отличие от рецепта или способа, обязательно обладает следующими свойствами: Дискретность — алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, т. е. преобразование исходных данных в результат осуществляется во времени дискретно. Можно считать, что шаги выполняются мгновенно в моменты времени t0, t1, t2…, а между этими моментами ничего не происходит.

Элементарность шагов означает, что объем работы, выполняемой на любом шаге, мажорируется некоторой константой, зависящей от характеристик исполнителя алгоритмов, но не зависящей от входных данных и промежуточных значений, получаемых алгоритмом. Для численных алгоритмов такими элементарными шагами могут быть, например, сложение, вычитание, умножение, деление, сравнение двух 32-разрядных чисел, пересылка одного числа из некоторого места памяти в другое. К элементарным шагам не относится сравнение двух файлов, так как время сравнения зависит от длины файлов, а длина потенциально неограниченна Детерминированность — определённость. В каждый момент времени следующий шаг работы однозначно

определяется состоянием системы: алгоритм выдаёт один и тот же результат для одних и тех же исходных данных. Результаты не зависят ни от каких случайных факторов. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного.

Понятность — алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.

Завершаемость (конечность, определённость) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.

Конечность (финитность) алгоритма означает, что для получения результата нужно выполнить конечное число шагов, т. е. исполнитель в некоторый момент времени останавливается. Требуемое число шагов зависит от входных данных алгоритма и не мажорируется константой.

Массовость — алгоритм должен быть применим к разным наборам исходных данных.

Результативность — завершение алгоритма определенными результатами. Если же входные данные уникальны, то алгоритм в силу свойства определенности (детерминированности) будет давать всегда один и тот же результат и само построение алгоритма теряет смысл.

Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не дает результатов вовсе.

Алгоритм не содержит ошибок, если он дает правильные результаты для любых допустимых исходных данных.

Алгоритм всегда рассчитан на выполнение «неразмышляющим» исполнителем.

Понятие данных (значений) — исходных, промежуточных и результата также требует некоторого ограничительного толкования. Наиболее общее интуитивное понимание состоит в том, что данными в алгоритме могут служить самые разнообразные конструктивные объекты.

http://profbeckman.narod.ru/

Конструктивный объект — это строгое математическое понятие. Можно пока считать, что конструктивный объект — это элемент какого-либо конечного множества (например, один из дней недели), либо объект, вычисленный каким-либо алгоритмом. Конструктивными объектами являются символы, логические значения, целые и вещественные числа, представимые в машине, массивы конструктивных объектов. Алгоритм (его текст) также является конструктивным объектом и, значит, может рассматриваться как данные для другого алгоритма: текст программы (алгоритма) является входными данными для программы-транслятора.

Таким образом, понятия алгоритма и данных двойственны, их определения рекурсивны: в формулировке понятия алгоритма использовались понятия данных, а они, в свою очередь, определяются с использованием понятия алгоритма, и т. д. Это определяет равную важность двух понятий в компьютерных науках, что отражается и в современных языках программирования.

Замечание об определенности и конечности: иногда считают, что алгоритм может заканчиваться без получения результата (безрезультатная остановка) или даже не заканчиваться вовсе при некоторых исходных данных (неприменимость к этим исходным данным). Взгляд на это с точки зрения теории — машины Тьюринга — обсудим позже. С практической точки зрения такая ситуация тоже требует внимания: операционная система (ОС) вычислительной машины, являясь совокупностью алгоритмов, при нормальной работе не предполагает остановки и выдачи каких-либо результатов; она лишь добросовестно получает периодически входные данные-задания и запускает их; задания-алгоритмы сами получают результаты. Таким образом, ОС не выдаёт продукции, если не считать протокола её работы. Другие диалоговые программные системы также требуют для своего описания более широкой интерпретации понятия алгоритма: они не получают входные данные сразу и не всегда можно говорить об априорной ограниченности объёма данных некоторой константой. Однако все сказанное не умаляет важности приведённого понятия алгоритма, а говорит лишь о богатстве проблематики компьютерных наук.

Дадим уточняющее понятие алгоритма, которое не является определением в математическом смысле слова, но более формально описывает понятие алгоритма, раскрывающего его сущность.

Алгоритм – конечная система правил, сформулированная на языке исполнителя, которая определяет последовательность перехода от допустимых исходных данных которая определяет последовательность перехода от допустимых исходных данных к конечному результату и которая обладает свойствами дискретности, детерминированности, результативности, конечности и массовости.

Для каждого исполнителя набор допустимых действий всегда ограничен – не может существовать исполнителя, для которого любое действие является допустимым. Перефразируя И.Канта: «Если бы такой исполнитель существовал, то среди его допустимых действий было бы создание такого камня, который он не может поднят. Но это противоречит допустимости действия «поднять любой камень».

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

Алгоритм является предписанием, а наличие предписания предполагает, что результат будет получен неким исполнителем, действующим по этому предписанию. Исполнитель (компьютер или программист, вручную отлаживающий свою программу) получает предписание и исходные данные. После этого он начинает действовать как автомат, т.е. выполнять в реальном времени описанные в алгоритме шаги. В результате выполнения каждого шага могут образовываться промежуточные результаты, которые исполнитель должен где-то фиксировать так, чтобы они могли быть использованы в качестве исходных данных для следующего шага. Исполнитель совершит конечное число шагов (даже если отдельные описания шагов использовались неоднократно) и после этого остановится, зафиксировав окончательный результат подобно промежуточным результатам.

Если есть текст некоторого предписания, то нужно убедиться в том, что это предписание является алгоритмом. Для этого необходимо проверить, выполняются ли перечисленные выше свойства.

Пример 1. Проверка на примере текста (отыскание максимального и минимального элементов массива):

«Исходные данные — положительное число N, определяющее количество элементов массива A, и целочисленные элементы A[1], A[2], …, A[N] массива A. Значения всех чисел находятся в пределах непосредственно представимых в вычислительной машине. Кроме исходных данных вводятся целочисленные переменные Max, Min, i. Первые две по окончании работы алгоритма определяют его результаты, третья является вспомогательной. Действия алгоритма состоят в выполнении следующих шагов:

1.Установить значения Мах = A[1], Min = A[1], i = 2.

2.Пока i <= N повторять шаги с 3 по 5.

3.Если Мах < A[i], то положить Мах = A[i].

4.Если Мin > A[i], то положить Мin = A[i].

http://profbeckman.narod.ru/

5.Увеличить i на 1.

6.Вывести результаты Мах и Min.

7.Остановиться».

Проверим выполнение основных свойств.

Дискретность очевидна.

Элементарность шагов. Шаг 1 содержит три присваивания значений; шаг 2 содержит одно сравнение чисел; шаги 3- 5 содержат два сравнения чисел, два присваивания значений (выполняется каждый раз только одно из них), одно увеличение значения на единицу; шаг 6 — вывод на экран или на печать данных ограниченного объема.

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

Конечность. Шаги 1 и 6 выполняются по одному разу. Количество выполнений шагов 2-5 зависит от значений переменной i и уровня N. Поскольку i монотонно возрастает, то ее значение достигнет уровня N через конечное число шагов. Если начальное значение переменной i больше уровня N, то шаг 2 выполняется один раз, а шаги 3-5 не выполняется ни разу. Таким образом, в любом случае выполнение алгоритма завершится через конечное число шагов.

Массовость. Алгоритм может воспринимать в качестве исходных данных различные массивы разной длины.

Однако не всегда так легко доказать выполнимость основных свойств алгоритма. Особенно это касается свойства конечности. Рассмотрим, например, алгоритм с одним входным аргументом — натуральным числом k.

1.Если k = 1, то остановиться.

2.Если k четное, то положить k = k/2; если k нечетное, то положить k = 3k+1.

3.Повторить, используя новое значение k.

Как следует из текста алгоритма, имеется некоторый процесс изменения значения k, начинающийся

с определенного начального значения, затем на каждом шаге k либо увеличивается, либо уменьшается и, наконец, возможно, приходит к значению 1, на котором и останавливается. В общем случае процесс немонотонный. Например, для k = 40: k = 40, 20, 10, 5, 16, 8, 4, 2, 1 (8 шагов). Решить вопрос о конечности данного алгоритма — это значит доказать одно из двух утверждений: для любого k процесс заканчивается единицей; для некоторого k процесс не заканчивается.

Если k равно степени двойки (2, 4, 8, 16, 32, …), то процесс будет монотонно убывающим и завершится за число шагов, равное этой степени. В противном случае на некотором промежуточном шаге значение k станет нечётным, но не равным единице, и на следующем шаге значение k увеличится. Оба варианта (алгоритм заканчивается, алгоритм не заканчивается) не кажутся очевидными. С одной стороны, увеличение k происходит в три раза, а уменьшение только в два раза и, если шаги увеличения и уменьшения строго чередуются, то для такого процесса имеется общая тенденция к возрастанию. С другой стороны, за шагом увеличения обязательно следует шаг уменьшения, но обратное неверно, т. е. шагов уменьшения может быть и больше, чем шагов увеличения. Потенциально возможно также зацикливание процесса, когда на очередном шаге получается уже встречавшееся ранее значение. Вот типичный пример с чередованием шагов: k = 127, 382, 191, 574, 287, 862, 431, 1294, 647, 1942, 971, 2914, 1457, 4372, 2186, 1093, 3280, 1640, 820, 410, 205, 616, 308, 154, 77, 232, 116, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

До значения k = 4372 шаги строго чередуются, затем начинается отрезок нерегулярного изменения, на котором имеется 20 четных и 8 нечетных чисел, и заканчивается процесс «хвостом» из степеней двойки. Можно показать, что для всех нечетных k = 2j — 1 или даже для k = n2j — 1, где n — нечётное натуральное число, начальный участок последовательности является строго чередующимся до достижения величины 2(n3j — 1); причем длина участка строгого чередования шагов пропорциональна величине j. Это плохая тенденция, поскольку k удаляется от 1. С другой стороны, для многих сочетаний n и j величина n3j — 1 = m2p — пропорциональна степени двойки. В этом случае вслед за возрастанием k идёт группа операций деления на 2, «сбрасывающая» значение k до величины m. В целом вопрос о конечности этого алгоритма должен решаться методами теории чисел. Несмотря на ряд усилий, предпринимавшихся математиками, решение пока не найдено.

1.2 История термина

Современное формальное определение алгоритма было дано в 30-50-х годы XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча — Тьюринга), Н. Винера, А.А.Маркова.

Само слово «алгоритм» происходит от имени учёного Абу Абдуллах Мухаммеда ибн Муса альХорезми. В 825 он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. Аль-Хорезми сформулировал правила вычислений в новой

http://profbeckman.narod.ru/

системе и, вероятно, впервые использовал цифру 0 для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как «цифра» и «шифр»). Приблизительно в это же время индийские цифры начали применять и другие арабские учёные. В первой половине XII века книга аль-Хорезми в латинском переводе проникла в Европу. Переводчик дал ей название Algoritmi de numero Indorum («Алгоритми о счёте индийском»). По-арабски же книга именовалась Китаб аль-джебр валь-мукабала («Книга о сложении и вычитании»). Из оригинального названия книги происходит слово Алгебра.

Всредние века слово algorism (или algorismus), неизменно присутствовавшее в названиях математических сочинений, обрело значение способа выполнения арифметических действий посредством арабских цифр, то есть на бумаге, без использования абака. Именно в таком значении оно вошло во многие европейские языки.

Алгоритм — это искусство счёта с помощью цифр, но поначалу слово «цифра» относилось только к нулю. Знаменитый французский трувер Готье де Куанси (Gautier de Coincy, 1177-1236) в одном из стихотворений использовал слова algorismus-cipher (которые означали цифру 0) как метафору для характеристики абсолютно никчёмного человека. Очевидно, понимание такого образа требовало соответствующей подготовки слушателей, а это означает, что новая система счисления уже была им достаточно хорошо известна.

Многие века абак был фактически единственным средством для практичных вычислений, им пользовались и купцы, и менялы, и учёные. Достоинства вычислений на счётной доске разъяснял в своих сочинениях такой выдающийся мыслитель, как Герберт Аврилакский (938—1003), ставший в 999 папой римским под именем Сильвестра II. Новое с огромным трудом пробивало себе дорогу, и в историю математики вошло упорное противостояние лагерей абацистов и алгорисмиков, которые пропагандировали использование для вычислений абака вместо арабских цифр. Прошло не одно столетие, прежде чем новый способ счёта окончательно утвердился, столько времени потребовалось, чтобы выработать общепризнанные обозначения, усовершенствовать и приспособить к записи на бумаге методы вычислений.

ВЗападной Европе учителей арифметики вплоть до XVII века продолжали называть «магистрами абака», как, например, математика Никколо Тарталью (1500—1557).

Итак, сочинения по искусству счёта назывались Алгоритмами. Из многих сотен можно выделить и такие необычные, как написанный в стихах трактат «Carmen de Algorismo» (латинское carmen и означает стихи) Александра де Вилла Деи, ум. 1240) или учебник венского астронома и математика Георга Пурбаха (1423-1461) «Opus algorismi jocundissimi» («Веселейшее сочинение по алгоритму»). Постепенно значение слова расширялось. Учёные начинали применять его не только к сугубо вычислительным, но и к другим математическим процедурам. Например, в 1360 французский философ Николай Орем (1323/25-1382) написал математический трактат «Algorismus proportionum» («Вычисление пропорций»), в котором впервые использовал степени с дробными показателями и фактически вплотную подошёл к идее логарифмов. Когда же на смену абаку пришёл так называемый счёт на линиях, многочисленные руководства по нему стали называть «Algorithmus linealis», то есть правила счёта на линиях. Можно обратить внимание на то, что первоначальная форма algorismi спустя какое-то время потеряла последнюю букву, и слово приобрело более удобное для европейского произношения вид algorism. Позднее и оно подверглось искажению связанному со словом arithmetic.

В1684 Готфрид Лейбниц в сочинении «Nova Methodvs pro maximis et minimis, itemque tangentibus…»

впервые использовал слово «алгоритм» (Algorithmo) в ещё более широком смысле: как систематический способ решения проблем дифференциального исчисления. В XVIII веке в одном из германских математических словарей, Vollstandiges mathematisches Lexicon (изданном в Лейпциге в 1747), термин algorithmus всё ещё объясняется как понятие о четырёх арифметических операциях. Но такое значение не было единственным, ведь терминология математической науки в те времена ещё только формировалась. В частности, выражение algorithmus infinitesimalis применялось к способам выполнения действий с бесконечно малыми величинами. Пользовался словом алгоритм и Леонард Эйлер, одна из работ которого так и называется- «Использование нового алгоритма для решения проблемы Пелля. Понимание Эйлером алгоритма как синонима способа решения задачи уже очень близко к современному.

Однако потребовалось ещё почти два столетия, чтобы все старинные значения слова вышли из употребления. Этот процесс можно проследить на примере проникновения слова «алгоритм» в русский язык.

Историки датируют 1691 годом один из списков древнерусского учебника арифметики, известного как «Счётная мудрость». Это сочинение известно во многих вариантах (самые ранние из них почти на сто

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
Источник

Материал из MachineLearning.

Перейти к: навигация, поиск

Содержание

  • 1 Общие определения
    • 1.1 Формальные признаки алгоритмов
  • 2 Алгоритмы анализа данных
  • 3 Литература
  • 4 Ссылки

Алгори́тм — это точный набор инструкций, описывающих порядок действий некоторого исполнителя для достижения результата, решения некоторой задачи за конечное время.

Общие определения

Единого «истинного» определения понятия «алгоритм» нет.
Наиболее известные варианты определения опираются на интуитивное понятие «задачи»:

  • Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность (Д. Э. Кнут).
  • Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи (А. Н. Колмогоров).
  • Алгоритм — это последовательность действий, либо приводящяя к решению задачи, либо поясняющая, почему это решение получить нельзя.

Формальные признаки алгоритмов

  • Детерминированность: в каждый момент времени следующий шаг работы однозначно определяется состоянием исполнителя. Алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных.
  • Понятность: алгоритм должен включать только команды из заранее оговоренной системы команд исполнителя.
  • Завершаемость (конечность): при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов.
  • Массовость: алгоритм должен быть применим к разным наборам исходных данных.

Алгоритмы анализа данных

В анализе данных под алгоритмом понимается функция,
преобразующая входные данные в выходные данные,
эффективно вычислимая на компьютере за конечное время,
точнее, за приемлемо малое для данной задачи время.

В машинном обучении понятие алгоритм может употреблять в трёх смыслах.

Литература

  1. Рудаков, К. В. Алгебраическая теория универсальных и локальных ограничений для алгоритмов распознавания: Дис. док. физ.-мат. наук: 05-13-17. — Вычислительный центр АН СССР, 1992. — 274 с.  (подробнее)

Ссылки

  • Алгоритм — Википедия (русский).
  • Algorithm — Wikipedia (english).
Источник

Материал из Википедии — свободной энциклопедии

Перейти к: навигация, поиск

В старой трактовке алгори́тм — это точный набор инструкций, описывающих последовательность действий некоторого исполнителя для достижения результата, решения некоторой задачи за конечное время. По мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что какие-то действия алгоритма должны быть выполнены только друг за другом, но какие-то могут быть и независимыми.

Ранее часто писали «алгориФм», сейчас такое написание используется редко. (см. например Нормальный алгорифм Маркова)

Понятие алгоритма необязательно относится к компьютерным программам, так, например, чётко описанный рецепт приготовления блюда также является алгоритмом, в таком случае исполнителем является человек. Однако чаще всего в качестве исполнителя выступает компьютер.

Содержание

  • 1 Определения алгоритма
  • 2 Формальные признаки алгоритмов
  • 3 Наличие исходных данных и некоторого результата
  • 4 История термина
  • 5 Литература
  • 6 См. также
  • 7 Ссылки

[править] Определения алгоритма

Единого «истинного» определения понятия «алгоритм» нет.

«Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность». (Д. Э. Кнут)

«Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи». (А. Колмогоров)

«Алгоритм — это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату». (А. Марков)

«Алгоритм — точное предписание о выполнении в определенном порядке некоторой системы операций, ведущих к решению всех задач данного типа». (Философский словарь / Под ред. — М.М. Розенталя)

«Алгоритм — строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд». (Николай Дмитриевич Угринович)

«Алгоритм — это последовательность действий, направленных на получение определённого результата за конечное число шагов». (ROXANstudio)

«Алгоритм — это строго определённая последовательность действий, направленная на достижение определённых целей за конечное число шагов». (Привалов Егор Николаевич)

«Алгоритм есть формализованная последовательность действий (событий). Алгоритм может быть записан словами и изображён схематически. Практически любое неслучайное повторяемое действие поддаётся описанию через алгоритм». ([grey_olli])

«Алгоритм — однозначно, доступно и кратко (условные понятия — названия этапа) описанная последовательность процедур для воспроизводства процесса с обусловленным задачей алгоритма результатом при заданных начальных условиях. Универсальность (или специализация) алгоритма определяется применимостью и надёжностью данного алгоритма для решения нестандартных задач».

«Алгоритм — это понятные и точные предписания исполнителю совершить конечное число шагов, направленных на решение поставленной задачи».

«Алгоритм — это система операторов, взятых из множества операторов некоторого исполнителя, которая полностью определяет некоторый класс алгоритмических процессов, то есть процессов, которые:

  1. дискретны;
  2. детерминированы;
  3. потенциально конечны;
  4. преобразовывают некоторые конструктивные объекты.

Между операторами алгоритма и операциями (элементарными действиями) алгоритмического процесса в общем случае существует гомоморфное соответствие. Поэтому алгоритм следует также считать моделью алгоритмического процесса». (А. Копаев)

«Алгоритм — это некоторый конечный набор рассчитаных на определённого исполнителя операций в результате выполнения которых через определённое число шагов может быть достигнута поставленная цель или решена задача определённого типа».

«Алгоритм — это последовательность действий, либо приводящая к решению задачи, либо поясняющая почему это решение получить нельзя».

[править] Формальные признаки алгоритмов

Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:

  • Детерминированность — определённость. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного.
  • Понятность — алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.
  • Завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.
  • Массовость — алгоритм должен быть применим к разным наборам исходных данных.

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

[править] Наличие исходных данных и некоторого результата

Алгоритм — это точно определённая инструкция, последовательно применяя которую к исходным данным, можно получить решение задачи. Для каждого алгоритма есть некоторое множество объектов, допустимых в качестве исходных данных. Например, в алгоритме деления вещественных чисел делимое может быть любым, а делитель не может быть равен нулю.

Алгоритм служит, как правило, для решения не одной конкретной задачи, а некоторого класса задач. Так, алгоритм сложения применим к любой паре натуральных чисел. В этом выражается его свойство массовости, то есть возможности применять многократно один и тот же алгоритм для любой задачи одного класса.

[править] История термина

Современное формальное определение алгоритма было дано в 30—50-х годы XX века в работах Тьюринга, Поста, Чёрча (тезис Чёрча — Тьюринга), Н. Винера, А. А. Маркова.

Само слово «алгоритм» происходит от имени учёного Абу Абдуллах Мухаммеда ибн Муса аль-Хорезми. Около 825 года он написал сочинение, в котором впервые дал описание придуманной в Индии позиционной десятичной системы счисления. К сожалению, арабский оригинал книги не сохранился. Аль-Хорезми сформулировал правила вычислений в новой системе и, вероятно, впервые использовал цифру 0 для обозначения пропущенной позиции в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как «цифра» и «шифр»). Приблизительно в это же время индийские цифры начали применять и другие арабские учёные. В первой половине XII века книга аль-Хорезми в латинском переводе проникла в Европу. Переводчик, имя которого до нас не дошло, дал ей название Algoritmi de numero Indorum («Алгоритми о счёте индийском»). По-арабски же книга именовалась Китаб аль-джебр валь-мукабала («Книга о сложении и вычитании»). Из оригинального названия книги происходит слово Алгебра.

Таким образом, мы видим, что латинизированное имя среднеазиатского ученого было вынесено в заглавие книги, и сегодня ни у кого нет сомнений, что слово «алгоритм» попало в европейские языки именно благодаря этому сочинению. Однако вопрос о его смысле длительное время вызывал ожесточённые споры. На протяжении многих веков происхождению слова давались самые разные объяснения.

Одни выводили algorism из греческих algiros (больной) и arithmos (число). Из такого объяснения не очень ясно, почему числа именно «больные». Или же лингвистам больными казались люди, имеющие несчастье заниматься вычислениями? Своё объяснение предлагал и энциклопедический словарь Брокгауза и Ефрона. В нём алгорифм (кстати, до революции использовалось написание алгориѳм, через фиту) производится «от арабского слова Аль-Горетм, то есть корень». Разумеется, эти объяснения вряд ли можно счесть убедительными.

Упомянутый выше перевод сочинения аль-Хорезми стал первой ласточкой, и в течение нескольких следующих столетий появилось множество других трудов, посвящённых всё тому же вопросу — обучению искусству счёта с помощью цифр. И все они в названии имели слово algoritmi или algorismi.

Про аль-Хорезми позднейшие авторы ничего не знали, но поскольку первый перевод книги начинается словами: «Dixit algorizmi: …» («Аль-Хорезми говорил: …»), всё ещё связывали это слово с именем конкретного человека. Очень распространённой была версия о греческом происхождении книги. В англо-норманской рукописи XIII века, написанной в стихах, читаем:

«Алгоризм был придуман в Греции. Это часть арифметики. Придуман он был мастером по имени Алгоризм, который дал ему своё имя. И поскольку его звали Алгоризм, Он назвал свою книгу «Алгоризм».

Около 1250 года английский астроном и математик Иоанн Сакробоско написал труд по арифметике «Algorismus vulgaris», на столетия ставший основным учебником по вычислениям в десятичной позиционной системе счисления во многих европейских университетах. Во введении Сакробоско назвал автором науки о счёте мудреца по имени Алгус (Algus). А в популярной средневековой поэме «Роман о розе» (1275—1280) Жана де Мена «греческий философ Алгус» ставится в один ряд с Платоном, Аристотелем, Евклидом и Птолемеем! Встречался также вариант написания имени Аргус (Argus). И хотя, согласно древнегреческой мифологии, корабль «Арго» был построен Ясоном, именно этому Арго приписывалось строительство корабля.

«Мастер Алгус» (или Аргус) стал в средневековой литературе олицетворением счетного искусства. И в уже упоминавшейся «Поэме о розе», и в известной итальянской поэме «Цветок», написанной Дуранте, имеются фрагменты, в которых говорится, что даже «mestre Argus» не сумеет подсчитать, сколько раз ссорятся и мирятся влюблённые. Великий английский поэт Джефри Чосер в поэме «Книга герцогини» (1369 г.) пишет, что даже «славный счётчик Аргус» (noble countour Argus) не сможет счесть чудовищ, явившихся в кошмарных видениях герою.

Впрочем, греческая версия была не единственной. Мифический Алгор (Algor) именовался то королём Кастилии (Rex quodam Castelliae), то индийским королём, то арабским мудрецом (philosophus Algus nomine Arabicus).

Однако со временем такие объяснения всё менее занимали математиков, и слово algorism (или algorismus), неизменно присутствовавшее в названиях математических сочинений, обрело значение способа выполнения арифметических действий посредством арабских цифр, то есть на бумаге, без использования абака. Именно в таком значении оно вошло во многие европейские языки. Например, с пометкой «устар.» оно присутствует в представительном словаре английского языка Webster’s New World Dictionary, изданном в 1957 г.

Алгоритм — это искусство счёта с помощью цифр, но поначалу слово «цифра» относилось только к нулю. Знаменитый французский трувер Готье де Куэнси (Gautier de Coincy, 1177—1236) в одном из стихотворений использовал слова algorismus-cipher (которые означали цифру 0) как метафору для характеристики абсолютно никчёмного человека. Очевидно, понимание такого образа требовало соответствующей подготовки слушателей, а это означает, что новая система счисления уже была им достаточно хорошо известна.

Многие века абак был фактически единственным средством для практичных вычислений, им пользовались и купцы, и менялы, и учёные. Достоинства вычислений на счётной доске разъяснял в своих сочинениях такой выдающийся мыслитель, как Герберт Аврилакский (938—1003), ставший в 999 г. папой римским под именем Сильвестра II. Новое с огромным трудом пробивало себе дорогу, и в историю математики вошло упорное противостояние лагерей абацистов и алгорисмиков (первых иногда ещё называли гербекистами), которые пропагандировали использование для вычислений абака вместо арабских цифр. Интересно, что известный французский математик Никола Шюке (Nicolas Chuquet, 1445—1488) в реестр налогоплательщиков города Лиона был вписан как алгорисмик (algoriste). Но прошло не одно столетие, прежде чем новый способ счёта окончательно утвердился, столько времени потребовалось, чтобы выработать общепризнанные обозначения, усовершенствовать и приспособить к записи на бумаге методы вычислений. В Западной Европе учителей арифметики вплоть до XVII века продолжали называть «магистрами абака», как, например, математика Никколо Тарталью (1500—1557).

Итак, сочинения по искусству счёта назывались Алгоритмами. Из многих сотен можно выделить и такие необычные, как написанный в стихах трактат «Carmen de Algorismo» (латинское carmen и означает стихи) Александра де Вилла Деи (Alexander de Villa Dei, ум. 1240) или учебник венского астронома и математика Георга Пурбаха (Georg Peurbach, 1423—1461) «Opus algorismi jocundissimi» («Веселейшее сочинение по алгоритму»).

Постепенно значение слова расширялось. Учёные начинали применять его не только к сугубо вычислительным, но и к другим математическим процедурам. Например, около 1360 г. французский философ Николай Орем (Nicolaus Oresme, 1323/25-1382) написал математический трактат «Algorismus proportionum» («Вычисление пропорций»), в котором впервые использовал степени с дробными показателями и фактически вплотную подошёл к идее логарифмов. Когда же на смену абаку пришёл так называемый счёт на линиях, многочисленные руководства по нему стали называть «Algorithmus linealis», то есть правила счёта на линиях.

Можно обратить внимание на то, что первоначальная форма algorismi спустя какое-то время потеряла последнюю букву, и слово приобрело более удобное для европейского произношения вид algorism. Позднее и оно, в свою очередь, подверглось искажению, скорее всего, связанному со словом arithmetic.

В 1684 году Готфрид Лейбниц в сочинении «Nova Methodvs pro maximis et minimis, itemque tangentibus…» впервые использовал слово «алгоритм» (Algorithmo) в ещё более широком смысле: как систематический способ решения проблем дифференциального исчисления.

В XVIII веке в одном из германских математических словарей, Vollstandiges mathematisches Lexicon (изданном в Лейпциге в 1747 г.), термин algorithmus всё ещё объясняется как понятие о четырёх арифметических операциях. Но такое значение не было единственным, ведь терминология математической науки в те времена ещё только формировалась. В частности, выражение algorithmus infinitesimalis применялось к способам выполнения действий с бесконечно малыми величинами. Пользовался словом алгоритм и Леонард Эйлер, одна из работ которого так и называется — «Использование нового алгоритма для решения проблемы Пелля» («De usu novi algorithmi in problemate Pelliano solvendo»). Мы видим, что понимание Эйлером алгоритма как синонима способа решения задачи уже очень близко к современному.

Однако потребовалось ещё почти два столетия, чтобы все старинные значения слова вышли из употребления. Этот процесс можно проследить на примере проникновения слова «алгоритм» в русский язык.

Историки датируют 1691 годом один из списков древнерусского учебника арифметики, известного как «Счётная мудрость». Это сочинение известно во многих вариантах (самые ранние из них почти на сто лет старше) и восходит к ещё более древним рукописям XVI в. По ним можно проследить, как знание арабских цифр и правил действий с ними постепенно распространялось на Руси. Полное название этого учебника — «Сия книга, глаголемая по еллински и по гречески арифметика, а по немецки алгоризма, а по русски цифирная счётная мудрость».

Таким образом, слово «алгоритм» понималось первыми русскими математиками так же, как и в Западной Европе. Однако его не было ни в знаменитом словаре В. И. Даля, ни спустя сто лет в «Толковом словаре русского языка» под редакцией Д. Н. Ушакова (1935 г.). Зато слово «алгорифм» можно найти и в популярном дореволюционном Энциклопедическом словаре братьев Гранат, и в первом издании Большой Советской Энциклопедии (БСЭ), изданном в 1926 г. И там, и там оно трактуется одинаково: как правило, по которому выполняется то или иное из четырёх арифметических действий в десятичной системе счисления. Однако к началу XX в. для математиков слово «алгоритм» уже означало любой арифметический или алгебраический процесс, выполняемый по строго определённым правилам, и это объяснение также даётся в БСЭ.

Совершенно неожиданное объяснение слова мы обнаруживаем в энциклопедии Брокгауза-Ефрона. В ней сказано, что «Русское слово „обозначение“ вполне соответствует точному значению слова А.» Очень трудно понять, откуда автор энциклопедической статьи взял это объяснение, как нам кажется, вряд ли верное. А это означает, что даже к сведениям, приводимым в самом авторитетном энциклопедическом издании, следует относиться внимательно, по возможности перепроверяя их!

Алгоритмы становились предметом все более пристального внимания учёных, и постепенно это понятие заняло одно из центральных мест в современной математике. Что же касается людей, от математики далёких, то к началу сороковых годов это слово они могли услышать разве что во время учебы в школе, в сочетании «алгоритм Евклида». Несмотря на это, алгоритм все ещё воспринимался как термин сугубо специальный, что подтверждается отсутствием соответствующих статей в менее объёмных изданиях. В частности, его нет даже в десятитомной Малой Советской Энциклопедии (1957 г.), не говоря уже об однотомных энциклопедических словарях. Но зато спустя десять лет, в третьем издании Большой советской энциклопедии (1969 г.) алгоритм уже характеризуется как одна из основных категорий математики, «не обладающих формальным определением в терминах более простых понятий, и абстрагируемых непосредственно из опыта». Как мы видим, отличие даже от трактовки первым изданием БСЭ разительное! За сорок лет алгоритм превратился в одно из ключевых понятий математики, и признанием этого стало включение слова уже не в энциклопедии, а в словари. Например, оно присутствует в академическом «Словаре русского языка» (1981 г.) именно как термин из области математики.

Одновременно с развитием понятия алгоритма постепенно происходила и его экспансия из чистой математики в другие сферы. И начало ей положило появление компьютеров, благодаря которому слово «алгоритм» обрело новую жизнь. Вообще можно сказать, что его сегодняшняя известность напрямую связана со степенью распространения компьютеров. Например, в третьем томе «Детской энциклопедии» (1959 г.) о вычислительных машинах говорится немало, но они ещё не стали чем-то привычным и воспринимаются скорее как некий атрибут светлого, но достаточно далёкого будущего. Соответственно и алгоритмы ни разу не упоминаются на её страницах. Но уже в начале 70-х гг. прошлого столетия, когда компьютеры перестали быть экзотической диковинкой, слово «алгоритм» стремительно входит в обиход. Это чутко фиксируют энциклопедические издания. В «Энциклопедии кибернетики» (1974 г.) в статье «Алгоритм» он уже связывается с реализацией на вычислительных машинах, а в «Советской военной энциклопедии (1976 г.) даже появляется отдельная статья «Алгоритм решения задачи на ЭВМ». За последние полтора-два десятилетия компьютер стал неотъемлемым атрибутом нашей жизни, компьютерная лексика становится все более привычной. Слово «алгоритм» в наши дни известно, вероятно, каждому. Оно уверенно шагнуло даже в разговорную речь, и сегодня мы нередко встречаем в газетах и слышим в выступлениях политиков выражения вроде «алгоритм поведения», «алгоритм успеха» или даже «алгоритм предательства». Академик Н. Н. Моисеев назвал свою книгу «Алгоритмы развития», а известный врач Н. М. Амосов — «Алгоритм здоровья» и «Алгоритмы разума». А это означает, что слово живёт, обогащаясь все новыми значениями и смысловыми оттенками.

[править] Литература

  • Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн Алгоритмы: построение и анализ = INTRODUCTION TO ALGORITHMS. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296. — ISBN 0-07-013151-1
  • Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4
  • Порублев Илья Николаевич, Ставровский Андрей Борисович Алгоритмы и программы. Решение олимпиадных задач. — М.: «Вильямс», 2007. — С. 480. — ISBN 978-5-8459-1244-2

[править] См. также

  • ДРАКОН (язык программирования) — Дракон-схемы
  • Список алгоритмов
  • Алгоритм (издательство).
  • Императивное программирование
  • Теория алгоритмов
  • Рекурсия
  • Численные методы
  • Блок-схема
  • Метаалгоритм
  • Адаптивный алгоритм

[править] Ссылки

  • Паронджанов В.Д. Как улучшить работу ума. Алгоритмы без программистов — это очень просто! М.: Дело, 2001. — 360с.
  • «Слово „алгоритм“: происхождение и развитие», В. В. Шилов, Журнал «Потенциал» — источник исторических сведений.
  • Алгоритмы, методы, исходники — сайт по алгоритмам и методам программирования
  • Дискретная математика: Алгоритмы — список алгоритмов
  • Юрий Лифшиц. Курс лекций Алгоритмы для Интернета
  • Геометрические алгоритмы
  • о Алгоритме в энциклопедии «Кругосвет»
  • Статьи по алгоритмам из научных библиотек
Источник

Введение в алгоритмы — ответы на тесты Интуит

Правильные ответы выделены зелёным цветом.
Все ответы: В курсе дается введение в теорию алгоритмов. Рассматриваются формальные модели алгоритмов: машина Тьюринга, алгоритмы Маркова, Паскаль, а также основные структуры данных и алгоритмы.

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

(1) правило

(2) алгоритм

(3) структура

Что представляет собой дерево?

(1) связанный граф

(2) динамический граф

(3) контекстный граф

Совокупность всех листьев дерева носит название

(1) листва

(2) крона

(3) ветвь

Какова вычислительная сложность алгоритма цифровой сортировки?

(1) линейная

(2) квадратичная

(3) кубическая

Именованный набор однотипных переменных, расположенных в памяти непосредственно друг за другом, доступ к которым осуществляется по индексу, носит название

(1) модульный массив

(2) индексный массив

(3) контекстный массив

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

(1) типизация

(2) функция

(3) конструкция

Нормальный алгоритм Маркова является

(1) модальным

(2) вербальным

(3) вариативным

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

(1) формальная система

(2) маркировка

(3) алфавит

Основной чертой высокоуровневых языков является

(1) детерминация

(2) абстракция

(3) модификация

Преобразование входного массива данных произвольной длины в выходную битовую строку фиксированной длины носит название

(1) интерпретация

(2) хеширование

(3) модуляция

Паскаль — это

(1) визуальная среда программирования

(2) высокоуровневый язык программирования

(3) структурированный алгоритмический язык

Обращение к статической переменной осуществляется

(1) по имени

(2) по идентификатору

(3) по ключу

Дерево, в котором степени вершин не превосходят 3, носит название

(1) комплексное

(2) двоичное

(3) аддитивное

У разных реализаций одного и того же алгоритма должен быть

(1) терминальный граф

(2) изоморфный граф

(3) контекстный граф

Удаление ветви дерева носит название

(1) агрегация

(2) обрезка

(3) инъекция

Вершины дерева, не имеющие потомков, называются

(1) модальными вершинами

(2) статическими вершинами

(3) терминальными вершинами

Сколько сравнений и обращений к памяти требуется в связных списках при обращении к элементу по его номеру?

В Паскале массив объявляется ключевым словом

(1) cont

(2) array

(3) module

Из приведенных ниже записей выделите свойства функции:

(1) функция возвращает значение

(2) вызов функции может использоваться в программе как выражение

(3) функция является процедурой

Любой нормальный алгоритм эквивалентен

(1) машине Тьюринга

(2) алгоритму Порка

(3) идентификатору Купера

Система правил определения поведения отдельных языковых конструкций носит название

(1) грамматика

(2) семантика

(3) морфология

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

(1) C++

(2) Visual Basic

(3) Java

К простейшим примерам хеш-функций следует отнести

(1) контрольную сумму

(2) массив идентификаторов

(3) ориентированный граф

Объектное расширение языка Паскаль носит название

(1) Module Pascal

(2) Object Pascal

(3) API Pascal

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

(1) Mark

(2) Release

(3) MaxAvail

Если у некоторого узла оба поддерева пустые, то он называется

(1) конечным узлом

(2) листовым узлом

(3) маркированным узлом

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

(1) аддитивный алгоритм

(2) адаптивный алгоритм

(3) априорный алгоритм

Обход дерева, при котором каждый узел-предок просматривается прежде его потомков, называется

(1) ассоциативным обходом

(2) предупорядоченным обходом

(3) маркированным обходом

Дерево без ветвей с одной вершиной — это

(1) контекстное дерево

(2) пустое дерево

(3) рекурсивное дерево

Сложность сортировки двусвязного списка составляет

(1) O(logn)

(2) O(n)

(3) O(n2)

Одномерный массив, каждый элемент которого, является ссылкой на другой одномерный массив, называется

(1) структурным массивом

(2) массивом массивов

(3) контекстным массивом

Подпрограммы, не возвращающие значения, носят название

(1) функции

(2) процедуры

(3) контейнеры

Процесс превращения функций многих переменных в функцию одной переменной называется

(1) стаффинг

(2) карринг

(3) ресторинг

Определение процесса вычисления в виде последовательности правил перезаписи носит название

(1) семантика вычислений

(2) терминальная семантика

(3) семантика правил

Транслятор, выполняющий преобразование программы, составленной на исходном языке, в объектный модуль, носит название

(1) компилятор

(2) имитатор

(3) детерминатор

Нахождение коллизии для хеш-функции с длиной значений n бит требует в среднем перебора около

(1) 2n операций

(2) 2n/2 операций

(3) 2n-1 операций

Программы на Паскале начинаются с ключевого слова

(1) rewrite

(2) program

(3) module

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

(1) Tree

(2) Mark

(3) Add

Сортирующее дерево является

(1) двоичным

(2) тернарным

(3) модальным

Алгоритм для нахождения наибольшего общего делителя двух целых чисел носит название?

(1) алгоритм Диффи-Хеллмана

(2) алгоритм Коши

(3) алгоритм Евклида

Обход дерева, при котором узлы посещаются уровень за уровнем, носит название

(1) обход по контексту

(2) обход в ширину

(3) обход с заменой

Дерево, у которого число вершин в левом и правом поддеревьях отличается не более чем на единицу, является

(1) идеально сбалансированным

(2) априорно сбалансированным

(3) контекстно сбалансированным

Эффективность метода сортировки при обработке уже упорядоченных, или частично упорядоченных данных, называется

(1) ассоциативностью

(2) естественностью

(3) терминальностью

Сложность параллельной сортировки

(1) меньше линейной

(2) больше линейной

(3) линейная

Функции, в результате вызова которых возвращается вычисленное значение, являются функциями

(1) с последовательным вызовом

(2) без побочного эффекта

(3) с типизацией данных

Какие рекурсивные функции используются в теории вычислимости?

(1) примитивно рекурсивные функции

(2) общерекурсивные функции

(3) частично рекурсивные функции

В какой семантике функции рассматриваются как текстуальные правильно построенные определения, обеспечивающие апплицирование?

(1) в модификативной

(2) в априорной

(3) в операциональной

К видам компиляции следует отнести

(1) пакетную

(2) построчную

(3) условную

(4) безусловную

В каких структурах данных используются хеш-функции?

(1) хеш-таблицы

(2) декартовы деревья

(3) массивы коллизий

Признаком конца программы или модуля в Паскале служит

(1) знак /

(2) знак $

(3) точка

Значение типа Word, содержащее смещение адреса указанного объекта, содержит функция

Двоичное дерево поиска является одной из возможных реализаций

(1) комплексного массива

(2) ассоциативного массива

(3) модального массива

К задачам теории алгоритмов относят

(1) формальное доказательство алгоритмической неразрешимости задач

(2) асимптотический анализ сложности алгоритмов

(3) классификацию алгоритмов в соответствии с классами сложности

Количество поддеревьев узла носит название

(1) степень узла

(2) высота узла

(3) модуль узла

Выделенная вершина графа носит название

(1) маркер

(2) полюс

(3) точка входа

К алгоритмам неустойчивой сортировки следует отнести

(1) сортировку выбором

(2) цифровую сортировку

(3) сортировку Шелла

Алгоритмы, использующие парные сравнения не могут иметь вычислительную сложность, меньшую чем

(1) O(n)

(2) O(nlogn)

(3) O(n2)

Что представляет собой парадокс Рассела?

(1) функционально-логический парадокс

(2) теоретико-множественную антиномию

(3) контекстно-независимое множество

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

(1) комплексно рекурсивные функции

(2) общерекурсивные функции

(3) модульно рекурсивные функции

Основной акцент концепции семантической паутины делается на работе

(1) с алгоритмами

(2) с метаданными

(3) с идентификаторами

Теоретической моделью процедурного программирования служит алгоритмическая система под названием

(1) машина Поста

(2) машина Тьюринга

(3) машина Максвелла

Ситуация в хеш-таблице, когда для различных ключей получается одно и то же хэш-значение, называется

(1) рекурсией

(2) коллизией

(3) сегрегацией

К порядковым типам языка Паскаль относятся

(1) все типы данных

(2) комплексные типы данных

(3) все типы, кроме real

Структура данных с дисциплиной доступа к элементам «первый пришёл — первый вышел» носит название

(1) стек

(2) контейнер

(3) очередь

К операциям обхода узлов двоичного дерева поиска следует отнести

(1) INVOKE_TRAVERSE

(2) INFIX_TRAVERSE

(3) ERASE_TRAVERSE

Машина Тьюринга является

(1) терминальной вычислительной машиной

(2) абстрактной вычислительной машиной

(3) комплексной вычислительной машиной

Дерево, в котором степени вершин не превосходят 3, носит название

(1) бинарное

(2) тернарное

(3) квадратное

Орграф, для которого существует покрытие дуг путями, исходящими из входа орграфа, носит название

(1) модульный граф

(2) абсолютный граф

(3) правильный граф

К алгоритмам сортировки, не основанным на сравнениях, следует отнести

(1) блочную сортировку

(2) поразрядную сортировку

(3) сортировку подсчётом

Время исполнения алгоритма блочной сортировки является

(1) линейным

(2) квадратичным

(3) экспоненциальным

Теоремы о неполноте разработаны

(1) Коши

(2) Абелем

(3) Гёделем

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

(1) алгоритм Эйлера

(2) машина Тьюринга

(3) цепь Маркова

Формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории, носит название

(1) форма Бэкуса-Наура

(2) комплекс Эйлера

(3) формат Кронекера

По своей семантике язык Паскаль является

(1) терминальным

(2) процедурным

(3) комплексным

Мерой криптостойкости хеш-функции является

(1) вычислительная сложность нахождения коллизии

(2) степень свободы хеш-функции

(3) типизация данных хеш-функции

Последовательность однотипных элементов в Паскале носит название

(1) файл

(2) модуль

(3) контейнер

Выборку элемента из очереди принято обозначать словом

(1) dequeue

(2) erase

(3) eject

Операция INFIX_TRAVERSE реализуется

(1) терминальным образом

(2) рекурсивным образом

(3) комплексным образом

Если каждой комбинации состояния и ленточного символа в таблице соответствует правило, машина Тьюринга называется

(1) априорной

(2) комплексной

(3) детерминированной

Какова степень концевых вершин дерева?

Подмножество графа, в котором любые две вершины смежные, носит название

(1) контейнер

(2) метадерево

(3) клика

Перед использованием поразрядной обменной сортировки необходимо знать

(1) максимальное количество разрядов в сортируемых величинах

(2) количество возможных значений одного разряда

(3) идентификаторы типизированных данных

Если входные элементы подчиняются равномерному закону распределения, то математическое ожидание времени работы алгоритма карманной сортировки является

(1) экспоненциальным

(2) линейным

(3) квадратичным

Входом универсальной машины Тьюринга является

(1) программа

(2) идентификатор

(3) маркер

С помощью вектора начальных вероятностей и матрицы переходов можно вычислить

(1) априорный вектор

(2) стохастический вектор

(3) терминальный вектор

Форма Бэкуса-Наура используется для описания синтаксиса

(1) языков программирования

(2) метаданных

(3) контейнеров

К примитивным типам данных Паскаля следует отнести

(1) mode

(2) real

(3) integer

Для устранения коллизий хеш-функций используют

(1) метод цепочек

(2) метод взаимосвязей

(3) метод корреляции

Переменная, диапазон значений которой состоит из адресов ячеек памяти, носит название

(1) идентификатор

(2) модификатор

(3) указатель

Чем коллекции отличаются от контейнеров?

(1) структурой

(2) типом связей

(3) терминацией

Сортировка несбалансированного дерева с помощью бинарного дерева поиска занимает времени

(1) O(N)

(2) O(N2)

(3) O(logN)

Тезис Чёрча — Тьюринга гласит, что любая интуитивно вычислимая функция является

(1) невычислимой

(2) частично вычислимой

(3) абсолютно вычислимой

Число различных деревьев, которые можно построить на n нумерованных вершинах, равно

Дерево с выделенной вершиной носит название

(1) остовное дерево

(2) корневое дерево

(3) аддитивное дерево

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

(1) модульной

(2) внешней

(3) контейнерной

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

(1) непрерывное равномерное распределение

(2) модульное динамическое распределение

(3) структурное частичное распределение

Программу любой детерминированной машины Тьюринга можно записать, используя

(1) машину Коши

(2) конечный алфавит

(3) массив идентификаторов

Группы состояний марковской цепи, которым соответствуют тупиковые вершины диаграммы порядка графа переходов, называются

(1) коммутативными классами

(2) эргодическими классами

(3) модификативными классами

Регулярные грамматики являются подмножеством

(1) терминальных

(2) контекстно-свободных

(3) модификативных

Примитивный тип данных в информатике, которые могут принимать два возможных значения, иногда называемых правдой и ложью, носит название

(1) истинный тип

(2) логический тип

(3) структурный тип

Что представляет собой предикат?

(1) идентификатор

(2) функцию

(3) массив

Нулевой указатель в Паскале имеет вид

(1) null

(2) void

(3) nil

Коллекция, реализующая принцип хранения «LIFO», носит название

(1) стек

(2) очередь

(3) маркер

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

(1) динамический сдвиг

(2) обратный вызов

(3) обратная рекурсия

Непустое множество дискретной природы носит название

(1) контейнер

(2) алфавит

(3) модуль

DFS — это

(1) поиск в глубину

(2) поиск в ширину

(3) поиск в высоту

Корневой баланс вершины, рассматриваемой как корень соответствующего поддерева, носит название

(1) баланс смежности

(2) баланс вершины

(3) баланс четности

Время работы алгоритма сортировки слиянием составляет

(1) O(logn)

(2) O(nlogn)

(3) O(n)

Сортировка перемешиванием является разновидностью

(1) блочной сортировки

(2) пузырьковой сортировки

(3) модальной сортировки

К элементам алфавита описания программ машины Тьюринга следует отнести

(1) идентификаторы

(2) маркеры

(3) символы состояния

Если любое состояние может быть достигнуто из любого другого состояния за конечное число переходов, то марковская цепь называется

(1) бинарной

(2) вероятностной

(3) неприводимой

Формальная система определения синтаксиса, в которой одни синтаксические категории последовательно определяются через другие, носит название

(1) модульная форма Бэкуса-Наура

(2) расширенная форма Бэкуса-Наура

(3) когнитивная форма Бэкуса-Наура

Тип данных, предназначенный для хранения одного символа в определённой кодировке, носит название

(1) символьный тип

(2) строковый тип

(3) контекстный тип

Количество связываемых объектов в отношении носит название

(1) четность

(2) арность

(3) модульность

Какой блок программы Паскаль является самым верхним в цепочке вложения процедур и функций?

(1) Program

(2) Main

(3) Class

Структура данных, состоящая из узлов, каждый из которых содержит как собственные данные, так и одну или две ссылки на следующее и/или предыдущее поле, носит название

(1) маркированный список

(2) ссылочный список

(3) связный список

Двоичное дерево, в узлах которого хранятся ссылки и ключи, носит название

(1) эйлерово дерево

(2) декартово дерево

(3) дерево Коши

Число символов в слове называют

(1) величиной

(2) размером

(3) длиной

К ребрам, которые образовываются после обходу в глубину, следует отнести

(1) древесные ребра

(2) ребра касания

(3) модальные ребра

Бинарное дерево, у которого все висячие вершины находятся на одном уровне и каждая вершина с одним потомком имеет брата с двумя сыновьями, носит название

(1) 2-3-дерево

(2) 1-2-братское дерево

(3) 1-2-3-симплекс

Сортировка вставками с предварительными «грубыми» проходами лежит в основе

(1) сортировки Эйлера

(2) сортировки Шелла

(3) сортировки Марка

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

(1) O(n)

(2) O(logn)

(3) O(2n)

Что утверждает теорема об универсальной машине Тьюринга?

(1) существование универсальной машины Тьюринга

(2) невозможность существования универсальной машины Тьюринга

(3) описание универсальной машины Тьюринга массивом модификаторов

Машина, которая в качестве кода читает свой собственный код, носит название

(1) аддитивная

(2) самоанализирующая

(3) комплексная

Имена, считающиеся заданными для данного описания грамматики, носят названия

(1) комплексные идентификаторы

(2) предопределённые идентификаторы

(3) маркированные идентификаторы

Из приведенных ниже записей выделите разновидности целого типа данных:

(1) знаковый

(2) модульный

(3) стоковый

Одноместные отношения соответствуют

(1) модификаторам

(2) свойствам

(3) типам

Файл модуля языка Паскаль начинается с ключевого слова

(1) MAIN

(2) MODULE

(3) UNIT

Дерево представляет собой

(1) связный граф

(2) модульный граф

(3) маркированный граф

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

(1) метаграф

(2) биграф

(3) циклограф

Из приведенных ниже записей выделите классы пройденных дуг орграфа при обходе в глубину:

(1) древесные

(2) прямые

(3) симметричные

Балансированное по высоте двоичное дерево поиска носит название

(1) АВЛ-дерево

(2) дерево Эйлера

(3) субдерево

Каким является В-дерево?

(1) сбалансированным

(2) модальным

(3) комплексным

Количество применяемой служебной памяти при пирамидальной сортировке составляет

(1) O(n)

(2) O(logn)

(3) O(1)

Универсальная машина Тьюринга моделирует другие машины

(1) с кубическим замедлением

(2) с не более чем квадратичным замедлением

(3) с экспоненциальным замедлением

Объединение нескольких элементов в единое целое носит название

(1) агрегирование

(2) маркировка

(3) конкатенация

Пустое множество в конечном алфавите является

(1) регулярным

(2) статическим

(3) комплексным

Форма представления дробных чисел, в которой число хранится в форме мантиссы и показателя степени, носит название

(1) перечислимый тип

(2) комплексный тип

(3) плавающая точка

Какими из приведенных ниже свойств обладают бинарные отношения?

(1) рефлексивность

(2) симметричность

(3) транзитивность

Стек программы Turbo Pascal обычно занимает

(1) 16 К

(2) 32 К

(3) 64 К

Глубина вложенности узла равна длине пути

(1) до последнего узла

(2) до корневого узла

(3) до соседнего узла

Последовательное деление дерева на две части, не связанные между собой, носит название

(1) биекция

(2) агрегация

(3) дихотомия

Сложность алгоритма пузырьковой сортировки составляет

(1) O(n2)

(2) O(logn)

(3) O(nlogn)

К типам вращения в АВЛ-дереве следует отнести

(1) малое правое вращение

(2) оптимальное правое вращение

(3) большое левое вращение

Рост высоты красно-черного дерева зависит

(1) от типа данных

(2) от числа узлов

(3) от метода идентификации данных

Значение в любой вершине сортирующего дерева

(1) больше, чем значения ее потомков

(2) меньше, чем значения ее потомков

(3) равно значениям ее потомков

Если исходная машина произвела t шагов, то универсальная произведёт не более

(1) clogt

(2) ct2

(3) cet

Методика создания нового класса из уже существующих классов носит название

(1) композиция

(2) терминация

(3) аддитивность

К параметрам конечного автомата следует отнести

(1) конечное множество состояний автомата

(2) множество заключительных состояний автомата

(3) допустимый входной алфавит автомата

Переменная, диапазон значений которой состоит из адресов ячеек памяти, носит название

(1) указатель

(2) идентификатор

(3) контейнер

Какие условия должны быть выполнены для отношения эквивалентности?

(1) рефлексивность

(2) симметричность

(3) транзитивность

Переменные, которые размещаются в памяти непосредственно в процессе работы программы, называются

(1) комплексными

(2) динамическими

(3) аддитивными

Из приведенных ниже записей выделите типы деревьев:

(1) рекурсивное

(2) с именованными ребрами

(3) ациклическое

Поддерживает ли язык Object Pascal полиморфизм?

(1) да, поддерживает

(2) нет, не поддерживает

(3) только в более ранней реализации

К свойствам алгоритмических процессов следует отнести

(1) дискретность

(2) детерминированность

(3) адаптивность

Узел, имеющий потомка, называется

(1) узлом-итератором

(2) узлом-родителем

(3) узлом-проходчиком

Самый верхний узел дерева называется

(1) листом

(2) корнем

(3) кроной

Эффективность алгоритма цифровой сортировки зависит

(1) от типизации данных

(2) от плотности элементов в массиве ячеек

(3) от метода формирования идентификаторов

Целое число, либо значение типа, приводимого к целому, указывающее на конкретный элемент массива, носит название

(1) идентификатор массива

(2) индекс массива

(3) модуль массива

Что представляет собой функция в программировании?

(1) контейнер

(2) подпрограмму

(3) модуль

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

(1) определение алфавита алгоритма

(2) определение схемы алгоритма

(3) определение идентификаторов алгоритма

Из приведенных ниже записей выделите синонимы понятия грамматики в математической логике:

(1) исчисление

(2) модуляция

(3) терминация

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

(1) модуляция

(2) конкретизация

(3) абстракция

Результат работы функции свёртки носит название

(1) модуль

(2) контейнер

(3) хеш

Программа на процедурном языке программирования состоит из последовательности

(1) модулей

(2) контейнеров

(3) инструкций

Доступ к динамической переменной может осуществляться

(1) по имени

(2) по ссылке

(3) по указателю

Узлами двоичного дерева являются

(1) контейнеры

(2) записи

(3) маркеры

Алгоритмы, вызывающие сами себя до тех пор, пока не будет достигнуто некоторое условие возвращения, носят название

(1) циклические

(2) рекурсивные

(3) коммутативные

Добавление ветви дерева называется

(1) аддитивностью

(2) прививкой

(3) терминацией

Нетерминальные вершины дерева называются

(1) внешними

(2) внутренними

(3) серединными

Cложность алгоритма сортировки односвязного списка составляет

(1) O(n)

(2) O(logn)

(3) O(nlogn)

Массив, размер которого может меняться во время исполнения программы, называется

(1) динамическим

(2) рекурсивным

(3) структурным

Входящими значениями функции являются

(1) идентификаторы

(2) маркеры

(3) аргументы

Вариант тезиса Чёрча — Тьюринга, сформулированный применительно к нормальным алгоритмам, принято называть

(1) принципом детерминации

(2) принципом нормализации

(3) принципом конкатенации

Смысловое значение предложений алгоритмического языка определяет

(1) семантика

(2) маркировка

(3) морфология

Из приведенных ниже записей выделите высокоуровневые языки программирования:

(1) Python

(2) Algol

(3) Ruby

Множество массивов данных, дающих одинаковые хеш-коды, носят название

(1) сегменты

(2) коллизии

(3) итераторы

К составляющим элементам языка Паскаль следует отнести

(1) определение типов

(2) записи

(3) указатели

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

(1) New

(2) Get

(3) Create

Каждый узел в дереве задаёт

(1) метадерево

(2) поддерево

(3) аддитивное дерево

Какой тип алгоритмов применяют при сжатии без потерь?

(1) адаптивный

(2) когнитивный

(3) деструктивный

Обход дерева, при котором каждый потомки просматриваются прежде их узла-предка, называется

(1) поступорядоченным обходом

(2) терминальным обходом

(3) статистическим обходом

Максимальная степень всех вершин является

(1) глубиной дерева

(2) степенью дерева

(3) маркером дерева

Идеальной вычислительной сложностью для алгоритма сортировки является

(1) O(n)

(2) O(logn)

(3) O(nlogn)

К типам отсчета значений в массиве следует отнести

(1) отсчет от нуля

(2) отсчет от специфического значения

(3) отсчет от последнего модификатора

Процедура — это

(1) тип массивных данных

(2) подпрограмма, не возвращающая значения

(3) алгоритм вычисления идентификаторов

Чем машина Поста отличается от машины Тьюринга?

(1) методом идентификации

(2) простотой

(3) типизацией данных

Операциональная семантика используется

(1) для синтаксических понятий языка

(2) для морфологической типизации языка

(3) для структуризации функций языка

Трансляция программы на язык, близкий к машинному, носит название

(1) интеграция

(2) компиляция

(3) сегрегация

n-битная хеш-функция считается криптостойкой, если вычислительная сложность нахождения коллизий для нее близка к

Блок операторов языка Паскаль ограничивается ключевыми словами

(1) repeat и until

(2) begin и end

(3) do и while

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

(1) MaxInt

(2) MaxMem

(3) MaxAvail

Высота кучи соответствует

(1) высоте ее корневого узла

(2) глубине ее листов

(3) глубине ее рекурсии

Алгоритм для нахождения наибольшей общей меры двух однородных величин носит название

(1) алгоритм Крамера

(2) алгоритм Евклида

(3) алгоритм Марка

Каждый уровень дерева при обходе в ширину обходится

(1) справа налево

(2) слева направо

(3) в произвольном порядке

N элементов можно организовать в бинарное дерево с высотой не более

(1) 2N

(2) log2(N)

(3) N2

К основным типам сортировки следует отнести

(1) внутреннюю

(2) рекурсивную

(3) вариантную

Алгоритмы сортировки классифицируются

(1) по назначению

(2) по вычислительной сложности

(3) по емкостной сложности

В каком программировании программа представляет собой набор вложенных вызовов функций, не вызывающих побочных эффектов?

(1) функциональное программирование

(2) аддитивное программирование

(3) модульное программирование

Какие из приведенных ниже функций совпадают с множеством вычислимых по Тьюрингу функций?

(1) частично рекурсивные функции

(2) модульно рекурсивные функции

(3) терминально рекурсивные функции

Какой тип семантики выражениям в программе ставит в соответствие настоящие математические объекты?

(1) денотационная семантика

(2) вариантная семантика

(3) рекурсивная семантика

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

(1) терминация

(2) интерпретация

(3) модификация

Хеширование применяется

(1) для сверки данных

(2) для проверки на наличие ошибок

(3) для проверки парольной фразы

Является ли Паскаль регистрозависимым?

(1) да, является

(2) нет, не является

(3) только в более поздних реализациях

Значение типа Pointer по заданному сегменту и смещению возвращает функция

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

(1) FIND

(2) LEFT

(3) SCOP

К ветвям теории алгоритмов следует отнести

(1) классическую теорию алгоритмов

(2) теорию асимптотического анализа алгоритмов

(3) теорию практического анализа вычислительных алгоритмов

Подграф данного графа, содержащий все его вершины и являющийся деревом, носит название

(1) остов

(2) контейнер

(3) биграф

Число вершин в графе носит название

(1) порядок графа

(2) глубина графа

(3) модуль графа

Сложность пирамидальной сортировки составляет

(1) O(nlogn)

(2) O(logn)

(3) O(n)

Алгоритм сортировки, в котором сортируемые элементы делятся на конечное число отдельных блоков так, что все элементы в одном блоке всегда больше, чем в другой, носит название

(1) блочная сортировка

(2) модульная сортировка

(3) комплексная сортировка

Парадокс Рассела демонстрирует противоречивость

(1) функциональной теории графов

(2) наивной теории множеств

(3) модульной теории массивов

Любая примитивно рекурсивная функция является

(1) абсолютно рекурсивной

(2) терминально рекурсивной

(3) частично рекурсивной

В семантической паутине предполагается повсеместное использование

(1) универсальных идентификаторов ресурсов

(2) онтологий описания метаданных

(3) языков описания метаданных

Программа на процедурном языке программирования состоит из последовательности

(1) идентификаторов

(2) инструкций

(3) модулей и приложений

Число хранимых элементов хеш-таблицы делённое на число возможных значений хэш-функции называется

(1) коэффициентом аддитивности хеш-таблицы

(2) коэффициентом заполнения хеш-таблицы

(3) коэффициентом маркировки хеш-таблицы

Каким ключевым словом обозначается в Паскале множество?

(1) set

(2) enum

(3) mode

Добавление элемента в очередь принято обозначать словом

(1) add

(2) enqueue

(3) set

Из приведенных ниже записей выделите операции обхода узлов двоичного дерева поиска:

(1) PREFIX_RESTORE

(2) PREFIX_ADJUST

(3) PREFIX_TRAVERSE

Машина Тьюринга является расширением

(1) терминального автомата

(2) аддитивного автомата

(3) конечного автомата

Имеет ли дерево кратные ребра?

(1) да, имеет

(2) нет, не имеет

(3) только терминальное дерево

Произвольное подмножество попарно несмежных ребер графа носит название

(1) терминальность

(2) паросочетание

(3) симплекс

Сложность обменной поразрядной сортировки является

(1) кубической

(2) квадратичной

(3) линейной

При удачных входных данных алгоритм блочной сортировки может достигать времени исполнения

(1) O(N)

(2) O(logN2)

(3) O(logN)

Машина Тьюринга, которая может заменить собой любую машину Тьюринга, носит название

(1) универсальная машина Тьюринга

(2) терминальная машина Тьюринга

(3) модульная машина Тьюринга

Конечная дискретная цепь определяется

(1) множеством состояний

(2) вектором начальных вероятностей

(3) матрицей переходных вероятностей

Для описания контекстно-свободных формальных грамматик используется

(1) теорема Диффи-Хеллмана

(2) форма Бэкуса-Наура

(3) система Цермело

К особенностям языка Паскаль следует отнести

(1) строгую типизацию

(2) наличие средств структурного программирования

(3) использование массивов идентификации

Какая хеш-функция по определению не имеет коллизии?

(1) когнитивная

(2) инъективная

(3) модификативная

Для чтения из файла используется процедура

(1) get

(2) line

(3) depend

Какие операции поддерживает очередь с приоритетом?

(1) InsertWithPriority

(2) GetNext

(3) PeekAtNext

Можно ли использовать бинарное дерево поиска для сортировки?

(1) только для динамических массивов

(2) нет, нельзя

(3) да, можно

На Машине Тьюринга можно имитировать

(1) аддитивный алгоритм Лагранжа

(2) машину Поста

(3) нормальные алгоритмы Маркова

Любое дерево является

(1) симплексным графом

(2) двудольным графом

(3) априорным графом

Дерево с конечным числом вершин носит название

(1) ассоциативное

(2) полное

(3) конечное

Сколько времени занимает процедура, предназначенная для создания кучи из неупорядоченного массива входных данных?

(1) O(nlogn)

(2) O(n)

(3) O(n2)

При карманной сортировке предполагается, что входные данные равномерно распределены на отрезке

(1) [0, 1)

(2) (0, 1]

(3) [0, 1]

Отметьте возможный вход универсальной машины Тьюринга:

(1) массив

(2) программа

(3) модуль

Марковская цепь изображается в виде

(1) графа соответствий

(2) графа корреляции

(3) графа переходов

Из приведенных ниже записей выделите элементы описания формы Бэкуса-Наура:

(1) протоколы

(2) идентификаторы

(3) модификаторы

Из приведенных ниже записей выделите примитивные типы данных языка Паскаль:

(1) char

(2) stat

(3) boolean

Какие из приведенных ниже методов используются для устранения коллизий хеш-функций?

(1) маркированная адресация

(2) открытая адресация

(3) модульная адресация

К основным операциям над указателями следует отнести

(1) присваивание

(2) терминацию

(3) разыменование

Если коллекция хранит объекты разных типов, то она является

(1) комплексной

(2) гетерогенной

(3) маркированной

Чтобы сбалансировать дерево, следует использовать

(1) метод ветвей и узлов

(2) алгоритм пирамиды

(3) теорему Эйлера

Физический тезис Чёрча — Тьюринга гласит, что любая функция, которая может быть вычислена физическим устройством, может быть вычислена

(1) алгоритмом Коши

(2) машиной Тьюринга

(3) с помощью ряда Эйлера

Сколько различных деревьев можно построить на 4 нумерованных вершинах?

Величина в бинарном дереве, характеризующая соотношение между весами левого и правого поддеревьев корня, носит название

(1) массивная разность

(2) корневой баланс

(3) априорный маркер

Упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин, носит название

(1) ассоциативная сортировка

(2) топологическая сортировка

(3) модульная сортировка

К свойствам асимптотической оценки следует отнести

(1) транзитивность

(2) рефлексивность

(3) инцидентность

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

(1) с помощью массива идентификаторов

(2) используя конечный алфавит

(3) применив алгоритм Шекли

Состояния, которые находятся в эргодических классах, называются

(1) объективными

(2) априорными

(3) существенными

БНФ-конструкция определяет конечное число

(1) маркеров

(2) идентификаторов

(3) нетерминалов

Минимальная адресуемая ячейка памяти носит название

(1) маркер

(2) байт

(3) контейнер

Если хотя бы на одном наборе аргументов предикат принимает значение 1, он называется

(1) априорным

(2) выполнимым

(3) модульным

Оператор безусловного перехода в Паскале имеет вид

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

(1) контейнер

(2) множество

(3) массив

Процедура, которая ссылается на свободные переменные в своём лексическом контексте, носит название

(1) обобщение

(2) замыкание

(3) отождествление

Элементы алфавита называют

(1) символами

(2) маркерами

(3) идентификаторами

Поиск в глубину всегда завершается через конечное число шагов

(1) в контекстной вершине

(2) в начале просмотра

(3) в серединной вершине

Вершина с двумя потомками в бинарном дереве называется

(1) бинарной

(2) полной

(3) модульной

Сортировка слиянием может быть

(1) естественной

(2) модульной

(3) конструктивной

Лучшим случаем для сортировки перемешиванием является

(1) отсортированный массив

(2) терминальный массив

(3) контекстный массив

Из приведенных ниже записей выделите элементы алфавита описания программ машины Тьюринга:

(1) скобки

(2) маркеры

(3) коннекторы

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

(1) терминальная марковская модель

(2) скрытая марковская модель

(3) динамическая марковская модель

Расширенная форма Бэкуса-Наура используется для описания

(1) аддитивных маркированных грамматик

(2) контекстно-свободных формальных грамматик

(3) структурно-независимых грамматик

Символьный тип для Юникода является

(1) однобайтовым

(2) двубайтовым

(3) многобайтовым

К свойствам отношений следует отнести

(1) симметричность

(2) комплексность

(3) транзитивность

К составляющим частям вспомогательных модулей следует отнести

(1) типы

(2) константы

(3) переменные

Структура данных, состоящая из элементов одного типа, связанных между собой, называется

(1) линейный список

(2) комплексный список

(3) массивный список

Линейный алгоритм построения декартового дерева основан

(1) на инверсии

(2) на рекурсии

(3) на инцидентности

Слово длины 0 называется

(1) пустым

(2) априорным

(3) модульным

Ребра, замыкающие циклы при обходе дерева в глубину, называются

(1) ребра тождества

(2) ребра цикла

(3) ребра касания

Дерево с двумя концевыми вершинами называется

(1) линейным

(2) маркерным

(3) квадратным

К преимуществам сортировки вставками следует отнести

(1) эффективность на небольших наборах данных

(2) эффективность на наборах данных, которые уже частично отсортированы

(3) устойчивость

Каково время работы алгоритма сортировки перемешиванием для массива, отсортированного в обратном порядке?

(1) O(n2)

(2) O(logn2)

(3) O(n3)

О чем говорит теорема об универсальной машине Тьюринга?

(1) об описании терминальным алфавитом программы машины Тьюринга

(2) о существовании универсальной машины Тьюринга

(3) об описании программы машины Тьюринга контекстными символами

Единственной существенной аксиомой лямбда-исчисления является

(1) гамма-строка

(2) бета-редукция

(3) альфа-модификация

Элементы грамматики, имеющие собственные имена и структуру, носят название

(1) нетерминальные символы

(2) комплексные символы

(3) синтаксические символы

Целый тип, размер которого совпадает с размером машинного слова, носит название

(1) унифицированный

(2) стандартный

(3) модифицированный

Двуместные отношения называют

(1) комплексными

(2) бинарными

(3) двойными

Какие секции содержит модуль Паскаль программы?

(1) интерфейсную секцию

(2) секцию реализации

(3) секцию отождествления

Узел, имеющий потомка, называется

(1) узлом-итератором

(2) узлом-родителем

(3) узлом-модулем

Путь в графе, начинающийся и кончающийся в одной и той же вершине, носит название

(1) цепь

(2) контейнер

(3) цикл

Какие из приведенных ниже записей следует отнести к классам пройденных дуг орграфа при обходе в глубину?

(1) обратные

(2) контекстные

(3) поперечные

Для каждой вершины АВЛ-дерева высота его двух поддеревьев различается

(1) на 2

(2) на 1

(3) не более чем на 1

Свойство каждого узла дерева ссылаться на большое число узлов-потомков носит название

(1) ассоциативность

(2) ветвистость

(3) контекстность

Зависит ли количество применяемой служебной памяти при пирамидальной сортировке от размера массива?

(1) да, зависит

(2) нет, не зависит

(3) только в комплексных массивах

С каким максимальным замедлением универсальная машина Тьюринга может моделировать другие машины?

(1) с квадратичным

(2) с линейным

(3) с логарифмическим

Агрегирование — это

(1) типизация массивных данных

(2) объединение нескольких элементов в единое целое

(3) отождествление переходов в графе соответствия

Множество, состоящее из одной лишь пустой строки в конечном алфавите, является

(1) контекстным

(2) регулярным

(3) терминальным

К составляющим частям числа с плавающей точкой следует отнести

(1) маркер

(2) порядок

(3) мантиссу

Рефлексивное симметричное транзитивное отношение называется

(1) отношением априорности

(2) отношением эквивалентности

(3) отношением модульности

Динамическую память обычно используют

(1) при обработке больших массивов данных

(2) при разработке САПР

(3) при временном запоминании данных при работе с графическими средствами

Самый верхний узел дерева называется

(1) основным

(2) терминальным

(3) корневым

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

(1) таблица виртуальных методов

(2) таблица ассоциативности

(3) таблица инцидентности

BFS — это

(1) комплексный поиск

(2) поиск в ширину

(3) поиск в глубину

Сколько операций требует добавление элемента в АВЛ-дерево?

(1) O(lgN)

(2) O(NlgN)

(3) O(2N)

2-3 дерево является

(1) терминальным деревом

(2) В-деревом

(3) рекурсивным деревом

К достоинствам пирамидальной сортировки следует отнести

(1) доказанную оценку худшего случая O(logn)

(2) O(1) дополнительной памяти

(3) типизацию данных

Доказательство теоремы об универсальной машине Тьюринга является

(1) конструктивным

(2) деструктивным

(3) модификативным

На базе агрегирования реализуется методика

(1) поглощения

(2) делегирования

(3) вариативности

Графическое представление множества состояний и функции переходов носит название

(1) граф переходов

(2) диаграмма Эйлера

(3) контейнер соответствий

Тип данных, чьё множество значений представляет собой ограниченный список идентификаторов, носит название

(1) модульный тип

(2) перечислимый тип

(3) константный тип

Передача параметра возможна

(1) по модулю

(2) по значению

(3) по ссылке

Участок памяти, имеющий максимальную длину, носит название

(1) маркер

(2) контейнер

(3) сегмент

Граф с вершиной, выделенной в качестве корневой, носит название

(1) корневое дерево

(2) маркированное дерево

(3) контекстное дерево

Перекрытие виртуального метода осуществляется с помощью ключевого слова

(1) override

(2) eject

(3) disgrace

Алгоритмические процессы являются

(1) потенциально конечными

(2) аддитивными

(3) дискретными

Максимальная длина нисходящего пути от данного узла к самому нижнему узлу носит название

(1) высота узла

(2) длина узла

(3) модуль узла

Верхний узел для нижнего узла называется

(1) итератором

(2) предком

(3) исходом

Алгоритм сортировки, в котором сортируемые элементы делятся на конечное число отдельных блоков так, что все элементы в одном блоке всегда больше (или меньше), чем в другом, носит название

(1) структурная сортировка

(2) блочная сортировка

(3) массивная сортировка

Массивы с одним индексом называют

(1) простыми

(2) аддитивными

(3) одномерными

К подпрограммам в программировании следует отнести

(1) процедуры

(2) функции

(3) идентификаторы

Формула подстановки схемы нормального алгоритма может быть

(1) статической

(2) заключительной

(3) динамической

Какие из приведенных ниже записей следует считать синонимами грамматики в математической логике?

(1) формальная система

(2) исчисление

(3) детерминация

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

(1) интеграция

(2) портирование

(3) корректировка

К характеристикам алгоритмов хеширования следует отнести

(1) разрядность

(2) вычислительная сложность

(3) криптостойкость

К особенностям Паскаля следует отнести

(1) строгую типизацию

(2) наличие средств структурного программирования

(3) использование препроцессора при компиляции

С помощью процедур и функций реализуется работа с динамической областью памяти в Паскале?

(1) New

(2) Dispose

(3) MemAvail

Какие из приведенных ниже данных содержит узел двоичного дерева?

(1) данные, привязанные к узлу

(2) ссылки на узлы, являющиеся детьми данного узла

(3) идентификаторы доступа узла

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

(1) параллельные

(2) маркированные

(3) модульные

Пошаговый перебор элементов дерева по связям между предками-узлами и потомками-узлами называется

(1) динамизацией дерева

(2) унификацией дерева

(3) обходом дерева

Две вершины дерева соединяются

(1) ветвью

(2) циклом

(3) рекурсией

Требования к памяти при сортировке односвязного списка составляет

(1) O(logn)

(2) O(2n)

(3) O(n)

Массив, в разные элементы которого могут быть непосредственно записаны значения, относящиеся к различным типам данных, называется

(1) инцидентным

(2) ассоциативным

(3) гетерогенным

Результат выполнения функции может быть

(1) идентификатором

(2) скалярной величиной

(3) векторным значением

Набор правил нормального алгоритма преобразует двоичные числа

(1) в единичные

(2) в десятичные

(3) в шестнадцатеричные

Что представляет собой семантика в программировании?

(1) систему правил определения поведения отдельных языковых конструкций

(2) метод типизации данных

(3) формирование структуры процедур и функций

Какие из приведенных ниже записей следует отнести к высокоуровневым языкам программирования?

(1) Delphi

(2) Perl

(3) Cobol

Обычная разрядность контрольных сумм составляет

(1) 32 бита

(2) 64 бита

(3) 128 бит

Из приведенных ниже записей выделите элементы языка Паскаль:

(1) перечисления

(2) множества

(3) модификаторы

Какая процедура языка Паскаль освобождает участок памяти, выделенный для размещения динамической переменной?

(1) Dispose

(2) Delete

(3) Free

Какие структуры данных основаны на двоичном дереве?

(1) АВЛ-дерево

(2) красно-чёрное дерево

(3) дерево Фибоначчи

Алгоритм Хаффмана является

(1) вариативным

(2) адаптивным

(3) рекуррентным

Обход дерева, при котором посещается сначала левое поддерево, затем узел, затем — правое поддерево, носит название

(1) динамический обход

(2) статический обход

(3) симметричный обход

Обход двоичного дерева сверху вниз является

(1) префиксным

(2) суффиксным

(3) модульным

Сортировка, которая не меняет взаимного расположения равных элементов, носит название

(1) устойчивая

(2) модальная

(3) ассоциативная

К достоинствам массивов следует отнести

(1) легкость вычисления адреса элемента по его индексу

(2) одинаковое время доступа ко всем элементам

(3) малый размер элементов

Любое изменение функцией состояния программной среды, кроме возврата результата, называется

(1) коммутативностью

(2) побочным эффектом

(3) модификативностью

Какие варианты возможны после запуска машины Тьюринга?

(1) работа может закончиться невыполнимой командой

(2) работа может закончиться командой Stop

(3) работа никогда не закончится

Для синтаксических понятий языка используется

(1) терминальная семантика

(2) операциональная семантика

(3) комплексная семантика

Из приведенных ниже записей выделите типы компиляторов:

(1) векторизующий

(2) диалоговый

(3) отладочный

Простейшим способом усложнения поиска коллизий является

(1) изменение типизации данных

(2) увеличение разрядности хеша

(3) изменение адресации памяти

Операторы Паскаля разделяются

(1) точками с запятой

(2) символами #

(3) скобками

Какая функция языка Паскаль возвращает объем в байтах, занимаемый переменной?

(1) Length

(2) SizeOf

(3) MaxMem

Высота кучи в сортирующем дереве равна

(1) O(n)

(2) O(logn)

(3) O(1)

Что представляет собой соотношение Безу?

(1) наименьшее общее кратное

(2) наибольший общий делитель

(3) наибольшее общее кратное

К общим операциям с деревьями следует отнести

(1) поиск элемента

(2) перебор ветви дерева

(3) нахождение корневого элемента для любого узла

Если дерево идеально сбалансировано, то для поиска среди N элементов потребуется

(1) log2(N) сравнений

(2) N сравнений

(3) 2N сравнений

К алгоритмам устойчивой сортировки следует отнести

(1) сортировку пузырьком

(2) сортировку перемешиванием

(3) блочную сортировку

Алгоритм внутренней сортировки QuickSort имеет вычислительную сложность в среднем

(1) O(nlogn)

(2) O(n)

(3) O(logn)

Наиболее известным языком программирования, реализующим парадигму функционального программирования, является

(1) Алгол

(2) Лисп

(3) Фортран

Общерекурсивные функции включают в себя

(1) каскадно рекурсивные функции

(2) примитивно рекурсивные функции

(3) матрично рекурсивные функции

Механизмы отложенных вычислений использованы в языках

(1) Algol

(2) Miranda

(3) Haskell

Перевод программы с низкоуровневого языка на высокоуровневый носит название

(1) детерминация

(2) детализация

(3) декомпиляция

К вариантам адресации в хеш-таблицах следует отнести

(1) прямую

(2) открытую

(3) терминальную

К примитивным типам данных Паскаля следует отнести

(1) real

(2) integer

(3) char

Какая функция языка Паскаль освобождает участок кучи?

(1) Depend

(2) Erase

(3) Release

Из приведенных ниже записей выделите операции базового интерфейса двоичного дерева поиска:

(1) INSERT

(2) REMOVE

(3) ERASE

Оценка функции трудоёмкости алгоритма называется

(1) степенью

(2) глубиной

(3) сложностью

Множество, не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев, носит название

(1) массив

(2) кластер

(3) лес

Раскраска, при которой всякие смежные вершины (смежные ребра) раскрашены в разные цвета, носит название

(1) правильная раскраска

(2) четная раскраска

(3) нечетная раскраска

Какова сложность сортировки выбором?

(1) O(n)

(2) O(n2)

(3) O(logn)

Может ли блочная сортировка обладать линейным алгоритмом?

(1) да, может

(2) нет, не может

(3) только при комплексных типах данных

К аксиоматизациям парадокса Рассела следует отнести

(1) теорию Цермело — Френкеля

(2) теорию Неймана — Бернайса — Гёделя

(3) теорию Майка — Вайнера

Частично рекурсивные функции совпадают с множеством

(1) тернарных функций

(2) вычислимых функций

(3) аддитивных функций

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

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

(1) Бейсик

(2) Фортран

(3) Паскаль

Среднее время выполнения операций в хеш-таблице зависит

(1) от типа данных

(2) от коэффициента заполнения таблицы

(3) от маркировки идентификаторов

Типизация данных в Паскале осуществляется с помощью ключевого слова

(1) type

(2) struct

(3) set

Добавление элемента в очередь возможно

(1) только в начало

(2) только в конец

(3) в любое место очереди

Какие из приведенных записей следует отнести к операциям обхода узлов двоичного дерева поиска?

(1) POSTFIX_TRAVERSE

(2) POSTFIX_EJECT

(3) POSTFIX_QUERY

Управляющее устройство машины Тьюринга работает согласно:

(1) правилам аддитивности

(2) правилам перехода

(3) правилам модульности

Имеет ли дерево кратные петли?

(1) да, имеет

(2) нет, не имеет

(3) только контекстное дерево

Орграф, у которого каждая пара вершин соединена дугой, носит название

(1) полный граф

(2) частичный граф

(3) тернарный граф

Каждый ключ при обменной поразрядной сортировке представляется

(1) в десятичном виде

(2) в двоичном виде

(3) в виде модификаторов

К недостаткам блочной сортировки следует отнести

(1) сильную деградацию

(2) строгую типизацию

(3) ограничение по размеру массива

Что представляет собой универсальная машина Тьюринга?

(1) машина Тьюринга, не включающая в себя идентификаторов

(2) машина Тьюринга, которая может заменить собой любую машину Тьюринга

(3) машина Тьюринга, которая вызывает другие машины Тьюринга

Максимальным элементом матрицы переходных вероятностей является

Форма Бэкуса-Наура используется для описания

(1) аддитивных маркированных грамматик

(2) контекстно-свободных формальных грамматик

(3) комплексно-независимых грамматик

Программы на Паскале начинаются с ключевого слова

(1) main

(2) program

(3) class

Вычислительная невозможность нахождения исходного блока данных по известному значению хеш-функции от этого блока носит название

(1) априорность

(2) необратимость

(3) вариативность

Для записи в файл используется процедура

(1) try

(2) restore

(3) put

Может ли очередь с приоритетом хранить несколько пар с одинаковыми ключами?

(1) нет, не может

(2) да, может

(3) только в контейнерах переменных

Если элементы массива различны и расположены в случайном порядке, а длина массива N, то сортировка с помощью бинарного дерева поиска требует в среднем

(1) O(NlogN) операций

(2) O(N) операций

(3) O(N2) операций

Исполнители, для которых возможна имитация машины Тьюринга, называются

(1) полными по Тьюрингу

(2) универсальными по Тьюрингу

(3) статическими по Тьюрингу

Любое дерево, содержащее счётное количество вершин, является

(1) коммутативным графом

(2) планарным графом

(3) макрографом

Замкнутый путь в орграфе носит название

(1) маркер

(2) префикс

(3) контур

Фибоначчиева куча представляет собой

(1) массив идентификаторов

(2) контейнер ключей и данных

(3) набор деревьев

Время работы сортировки вставками равно

(1) O(n2)

(2) O(n)

(3) O(logn)

Какие из приведенных ниже записей следует отнести к возможным входам универсальной машины Тьюринга?

(1) программа

(2) рекурсия

(3) модификатор

Вершины графа переходов, изображающего марковскую цепь, соответствуют

(1) состояниям цепи

(2) вероятностям связности цепи

(3) идентификаторам цепи

Какие элементы описываются формой Бэкуса-Наура?

(1) модули

(2) данные

(3) терминалы

Заранее скомпилированные библиотеки подпрограмм, которые программист может использовать для создания новых программ, носят название

(1) модули

(2) контейнеры

(3) отладчики

Из приведенных ниже записей выделите методы устранения коллизий хеш-функций:

(1) метод цепочек

(2) строгая типизация

(3) открытая адресация

Указатель, хранящий специальное значение, используемое для того, чтобы показать, что данная переменная-указатель не ссылается ни на какой объект, носит название

(1) пустой указатель

(2) структурный указатель

(3) нулевой указатель

По логике организации коллекция может быть

(1) вектором

(2) массивом

(3) матрицей

Каким образом можно сбалансировать дерево?

(1) используя алгоритм пирамиды

(2) используя красно-чeрное дерево

(3) используя модульное дерево

Положение о том, что любая интуитивно вычислимая функция является частично вычислимой, лежит в основе

(1) теоремы Кронекера

(2) тезиса Чёрча — Тьюринга

(3) аксиомы Гёделя

Сколько различных деревьев можно построить на 5 нумерованных вершинах?

Число ребер в мультиграфе, соединяющих две данные вершины, носит название

(1) кратность

(2) четность

(3) инцидентность

Какими свойствами обладает частичный порядок?

(1) рефлексивность

(2) антисимметричность

(3) транзитивность

Из приведенных ниже записей выделите свойства асимптотической оценки:

(1) ассоциативность

(2) симметричность

(3) модульность

Можно ли записать программу любой детерминированной машины Тьюринга используя конечный алфавит?

(1) да, можно

(2) нет, нельзя

(3) только универсальную машину Тьюринга

Какие состояния цепи присутствуют в алгоритме Дейкстры?

(1) vertex

(2) analysis

(3) decrease

БНФ-конструкция определяет правила замены символа на последовательность

(1) терминалов

(2) маркеров

(3) идентификаторов

Какие логические операции допустимы в Паскале?

Математическая структура, которая формально определяет свойства различных объектов и их взаимосвязи, носит название

(1) отношение

(2) соответствие

(3) модальность

К подпрограммам Паскаля следует отнести

(1) модули

(2) процедуры

(3) функции

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

(1) матрица

(2) модуль

(3) контейнер

Что представляет собой замыкание?

(1) процедуру

(2) контейнер

(3) массив

Любой конечный упорядоченный набор символов из данного алфавита носит название

(1) строка

(2) слово

(3) модуль

Ребра, по которым при поиске в глубину, осуществлялись переходы из посещенных вершин в непосещенные, называются

(1) коммутативными

(2) древесными

(3) комплексными

Дерево, центр которого состоит из двух смежных вершин, называется

(1) бароцентральным

(2) бицентральным

(3) метацентральным

Из приведенных ниже записей выделите типы сортировки слиянием:

(1) сортировка простым слиянием

(2) сортировка естественным слиянием

(3) сортировка комплексным слиянием

Худшим случаем для алгоритма сортировки перемешиванием является

(1) аддитивный массив

(2) массив, отсортированный в обратном порядке

(3) массив с произвольным расположением элементов

Какие из приведенных ниже записей следует отнести к элементам алфавита описания программ машины Тьюринга?

(1) символы состояния

(2) скобки

(3) стрелки

Конечный набор, состоящий из пар слов, где левое слово переходит в правое, носит название

(1) нормальная схема подстановок

(2) модульная схема подстановок

(3) контекстная схема подстановок

Минимальные элементы грамматики, не имеющие собственной грамматической структуры, носят название

(1) маркированные символы

(2) аддитивные символы

(3) терминальные символы

Основным применением символьного типа данных является обращение

(1) к идентификаторам

(2) к отдельным знакам строки

(3) к меткам контейнера

К примерам отношений в математике следует отнести

(1) равенство

(2) коллинеарность

(3) делимость

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

(1) implementation

(2) initialization

(3) finalization

Именованный набор однотипных переменных, расположенных в памяти непосредственно друг за другом, доступ к которым осуществляется по индексу, носит название

(1) терминальный массив

(2) индексный массив

(3) коммутативный массив

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

(1) линейное

(2) квадратичное

(3) кубическое

Множество всех слов в алфавите с операцией конкатенации образует

(1) полипоид

(2) моноид

(3) аксоид

Частичный граф, порожденный древесными ребрами, является

(1) модулем графа

(2) контейнером графа

(3) каркасом графа

Максимальный связный подграф, не содержащий мостов, носит название

(1) ветвь

(2) суграф

(3) лист

Какие из приведенных ниже записей следует отнести к преимуществам сортировки вставками?

(1) сортировка списка по мере его получения

(2) простота реализации

(3) отсутствие изменения порядка элементов, которые уже отсортированы

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

(1) O(logn)

(2) O(nlogn)

(3) O(n)

Существует ли универсальная машина Тьюринга?

(1) да, существует

(2) нет, не существует

(3) только в комплексном пространстве

Лямбда-исчисление обладает свойством полноты по Тьюрингу в комплексе

(1) с бета-редукцией

(2) с альфа-терминацией

(3) с гамма-маркировкой

Последовательность символов в кавычках или апострофах носит название

(1) строка

(2) цепочка

(3) маркер

Целые типы, меньше стандартного размера, называются

(1) модульными

(2) общими

(3) короткими

Трёхместные отношения называют

(1) триадами

(2) триполярными

(3) тернарными

Какие из приведенных ниже объектов могут быть объявлены в интерфейсной секции модуля?

(1) константы

(2) переменные

(3) процедуры

Максимальная длина нисходящего пути от заданного узла к самому нижнему узлу называется

(1) высота узла

(2) глубина узла

(3) модуль узла

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

(1) ациклическим

(2) модальным

(3) когнитивным

Частичный орграф, порожденный древесными дугами, является

(1) модульным семантическим деревом

(2) корневым растущим ордеревом

(3) ассоциативным структурным деревом

Операция, которая в случае разницы высот левого и правого поддеревьев АВЛ-дерева равной 2, изменяет связи предок-потомок в поддереве данной вершины так, что разница становится не больше 1, носит название

(1) балансировка

(2) модификация

(3) терминация

Обобщением B-дерева на многомерный случай является

(1) R-дерево

(2) L-дерево

(3) T-дерево

Сортировка пирамидой использует

(1) корректирующее дерево

(2) сортирующее дерево

(3) модальное дерево

Верно ли то, что универсальная машина Тьюринга может моделировать другие машины с кубическим замедлением?

(1) да, может

(2) нет, не может

(3) только терминальная машина Тьюринга

Результат агрегирования называют

(1) агрегацией

(2) агрегатом

(3) модулем

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

(1) конечный автомат

(2) маркированный автомат

(3) терминальный автомат

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

(1) в флопсах

(2) в байтах

(3) в герцах

Антирефлексивное антисимметричное транзитивное отношение называется отношением

(1) частичного порядка

(2) строгого порядка

(3) модального порядка

Модули компилируются

(1) в текстовые файлы

(2) в бинарные файлы

(3) в базы данных

Любой узел дерева, имеющий потомков, носит название

(1) внутренний узел

(2) комплексный узел

(3) массивный узел

Метод класса, который может быть переопределён в классах-наследниках так, что конкретная реализация метода для вызова будет определяться во время исполнения, носит название

(1) агрегатная функция

(2) терминальная функция

(3) виртуальная функция

Поиск в ширину реализуется с помощью структуры

(1) массив

(2) очередь

(3) стек

При добавлении вершины в АВЛ-дерево, балансировка всех предков добавленной вершины производится

(1) в порядке от корня к родителю

(2) в порядке от родителя к корню

(3) в произвольном порядке

Все данные 2-3-дерева хранятся

(1) в контекстных вершинах

(2) в аддитивных вершинах

(3) в листовых вершинах

Из приведенных ниже записей выделите недостатки пирамидальной сортировки:

(1) сложность реализации

(2) неустойчивость

(3) наличие структурных анализаторов

Является ли доказательство теоремы об универсальной машине Тьюринга конструктивным?

(1) да, является

(2) нет, не является

(3) только в комплексном пространстве

Процесс, когда поставленная перед внешним объектом задача перепоручается внутреннему объекту, специализирующемуся на решении задач такого рода, носит название

(1) переопределение

(2) делегирование

(3) модуляция

Граф переходов является

(1) нагруженным

(2) однонаправленным

(3) контекстным

К операциям над указателями следует отнести

(1) присваивание

(2) структуризацию

(3) разыменование

Множество, созданное для логической группировки уникальных идентификаторов, носит название

(1) контейнер

(2) библиотека

(3) пространство имен

Какой указатель определяет запись PP: Pointer;?

(1) априорный

(2) нетипизированный

(3) массивный

Набор корневых деревьев называется

(1) контейнером

(2) линейным множеством

(3) лесом

Что позволяет объектам Паскаль использовать другую реализацию, просто используя другой набор указателей метода?

(1) таблица виртуальных методов

(2) разделение массива идентификаторов

(3) перекрытие

Источник

Понравилась статья? Поделить с друзьями:
  • Точный набор инструкций описывающих последовательность действий некоторого исполнителя
  • Точный набор инструкций описывающих порядок действий исполнителя для достижения результата
  • Точное описание некоторого процесса инструкция по его выполнению
  • Точное описание некоторого процесса инструкция по его выполнению
  • Точная инструкция определяющая процесс достижения поставленной цели за конечное число шагов