Spisok_opredeleny_k_ekzamenu_2014

Оглавление

Алгоритм ..................................................................................................................

3

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

3

Управляющая головка.............................................................................................

3

Внутренняя память машины ..................................................................................

3

Конфигурация машины Тьюринга ........................................................................

3

Программа машины Тьюринга ..............................................................................

3

Тезис Тьюринга .......................................................................................................

3

Машина В эквивалентна машине А ......................................................................

3

Самоанализирующие машины ...............................................................................

3

Универсальная машина...........................................................................................

3

Взаимозаменяемые машины Тьюринга ................................................................

3

Свойство машин Тьюринга называется инвариантным......................................

3

Свойство машин Тьюринга называется нетривиальным ....................................

3

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

3

Тезис Маркова .........................................................................................................

3

Эффективно перечислимое множество.................................................................

3

Подмножество В множества А эффективно распознается в А ..........................

3

Множество (по Тьюрингу) .....................................................................................

4

Множество (по Кантору)......................................................................................

4

Мощность множества (по Кантору)...................................................................

4

Мощность множества...........................................................................................

4

Конечное множество .............................................................................................

4

Бесконечное множество ........................................................................................

4

Счетно-бесконечные множества .........................................................................

4

Несчетные множества ..........................................................................................

4

Счетное множество...............................................................................................

4

Трансфинитное число .............................................................................................

4

Множество целых чисел.........................................................................................

4

Два элемента a и b называют упорядоченной парой ..........................................

4

Упорядоченная n-ка натуральных чисел...............................................................

4

Конечные комплексы натуральных чисел.............................................................

4

Рациональное число.................................................................................................

4

Алгебраическое действительное число.................................................................

4

Континуум-гипотеза ..............................................................................................

4

Комплексное число ..................................................................................................

4

Иррациональное число ............................................................................................

5

Трансцендентное число ..........................................................................................

5

Импредикабельное свойство..................................................................................

5

Действительное число вычислимо ........................................................................

5

Арифметическая функция ......................................................................................

5

Частичная арифметическая функция (ЧАФ) ......................................................

5

Характеристическая функция χA какого-нибудь подмножества А расширенного

множества натуральных чисел N*.......................................................................

5

Вычислимая арифметическая функция (ВАФ) ....................................................

5

Вычислимая частичная арифметическая функция (ВЧАФ) ..............................

5

Эффективное распознавание функций ...............................................................

5

Эффективное сравнение арифметических функций...........................................

5

Частичная арифметическая функция f называется примитивно-рекурсивной5

Частичная арифметическая функция f называется частично-рекурсивной...

5

Тезис Черча ..............................................................................................................

6

Частичная арифметическая функция f называется общерекурсивной............

6

Кусочно-заданная функция.....................................................................................

6

Нерекурсивная функция ..........................................................................................

6

Непримитивно рекурсивная функция ....................................................................

6

Временная сложность алгоритма T(x) ................................................................

6

Пространственная сложность S(x) .....................................................................

6

Арифметическая функция f(x) называется функцией одного верхнего порядка с

функцией g(x) и записывается …...........................................................................

6

Арифметическая функция f(x) называется функцией одного нижнего порядка с

функцией g(x) и записывается …...........................................................................

6

Арифметическая функция f(x) называется функцией одного порядка с функцией g(x) и

записывается … ......................................................................................................

6

Полиномиальные функции ......................................................................................

7

Экспоненциальные функции ...................................................................................

7

Арифметические функции f(x) и g(x) называются полиномиально-связанными или

полиномиально-эквивалентнтными ......................................................................

7

Полиномиальный алгоритм....................................................................................

7

Экспоненциальный алгоритм .................................................................................

7

Легкоразрешимая задача........................................................................................

7

Трудноразрешимая задача......................................................................................

7

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

Алгоритм

системы операций, определяющих процесс перехода от исходных

данных к искомому результату для решения задачи данного типа.

абстрактная

(воображаемая)

"вычислительная

машина"

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

некоторого точно охарактеризованного типа, дающая пригодное

для целей математического рассмотрения уточнение общего

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

это некоторое устройство, которое может перемещаться вдоль

Управляющая головка

ленты так, что в каждый рассматриваемый момент времени оно

находится напротив определенной ячейки ленты

это выделенная ячейка памяти, которая в каждый

Внутренняя память

рассматриваемый момент находится в некотором «состоянии».

машины

это совокупность, образованная содержимым текущей

Конфигурация машины

обозреваемой ячейки aj и состоянием внутренней памяти Si.

Тьюринга

это совокупность команд установленного формата.

Программа машины

Тьюринга

любой алгоритм можно преобразовать в машину Тьюринга

Тезис Тьюринга

если в соответствующие такты их работы лента машины В

Машина В эквивалентна

содержит всю информацию о ленте машины А.

машине А

это машины, в которых все служебные символы как-либо

Самоанализирующие

изображаются ленточными символами.

машины

машина Тьюринга, обладающая способностью путём подходящего

Универсальная машина

кодирования выполнить любое вычисление

Две машины Тьюринга, имеющие один и тот же внешний алфавит,

Взаимозаменяемые

будем называть взаимозаменяемыми, если, каково бы ни было слово

машины Тьюринга

в их общем алфавите, не содержащее пустого символа, они либо пе-

рерабатывают его в одно и то же слово, либо обе к нему неприме-

нимы.

если любые две взаимозаменяемые машины либо обе обладают этим

Свойство машин Тьюрин-

свойством, либо обе не обладают.

га называется

инвариантным

если существуют как машины, обладающие этим свойством, так и

Свойство машин Тьюрин-

не обладающие им

га называется

нетривиальным

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

Нормальный алгоритм

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

Маркова

схемой подстановок, выполняемых по заранее определенной схеме.

любой вычислительный процесс можно преобразовать в

Тезис Маркова

нормальный алгоритм.

множество, элементы которого можно перечислить по алгоритму

Эффективно

(пронумеровать натуральным рядом без пропусков и повторений).

перечислимое

множество

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

Подмножество В

элемента множества А определить, принадлежит ли

данный

это действительное число, не являющееся рациональным.

Иррациональное число

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

Трансцендентное число

это свойство, которое не применимо само к себе.

Импредикабельное

свойство

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

Действительное число

точности

вычислимо

это функция, определенная на расширенном множестве

Арифметическая

натуральных чисел N* и принимающая значения из расширенного

функция

множества натуральных чисел N*..

это функция, определенная на некотором подмножестве М

Частичная

расширенного множества натуральных чисел N* и принимающая

арифметическая

значения из множества N*.

функция (ЧАФ)

это функция от одной переменной, равная 1 в точках множества A

Характеристическая

и равная 0 в точках, не принадлежащих A

функция χA какого-нибудь

подмножества А

расширенного

множества

натуральных чисел N*

это функция, для которой существует алгоритм вычисления ее

Вычислимая

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

арифметическая

чисел N*

функция (ВАФ)

это функция, для которой существует алгоритм вычисления ее

Вычислимая частичная

значения в любой точке области определенности

арифметическая

функция (ВЧАФ)

это процедура, позволяющая при помощи некоторого алгоритма

Эффективное

определить, относится ли данная функция к рассматриваемому

распознавание функций

классу

это процедура, позволяющая при помощи некоторого алгоритма

Эффективное сравнение

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

арифметических

функций

если она может быть получена из простейших функций Cqn, S, Umn

Частичная

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

арифметическая

(т.е. задана в базисе Клини).

функция f называется

примитивно-

рекурсивной

если она может быть получена из простейших функций Cqn, S, Umn

Частичная

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

арифметическая

минимизации (т.е. задана в расширенном базисе Клини).

функция f называется

частично-рекурсивной

Класс алгоритмически (или машинно) вычислимых частичных

Тезис Черча

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

рекурсивных функций.

если она может быть получена из из простейших функций Cqn, S,

Частичная

Umn конечным числом операций подстановки, примитивной рекурсии

арифметическая

и слабой минимизации

функция f называется

общерекурсивной

Пусть заданы некоторые функции fi(x1,.....,xn), i=1,…,s+1 и указаны

Кусочно-заданная

какие то условия Pj(x1,.....,xn), j=1,…,s, которые для любого набора

функция

чисел x1,.....,xn могут быть истинными или ложными. Допустим, что

ни для одного набора чисел x1,.....,xn никакие два из упомянутых

условий не могут быть одновременно истинными. Функция

f(x1,.....,xn), заданная схемой:

f1(x1,…,xn)

если P1(x1,…,xn) истинно;

f2(x1,…,xn)

если P2(x1,…,xn) истинно;

f (x1,.....,xn) = ………

fs(x1,…,xn)

если Ps(x1,…,xn) истинно;

fs+1(x1,…,xn) для остальных x1,…,xn

называется кусочно-заданной

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

Нерекурсивная функция

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

функция, являющаяся общерекурсивной, но не принадлежащая к

Непримитивно

множеству примитивно-рекурсивных функций.

рекурсивная функция

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

Временная сложность

размера x в худшем случае.

алгоритма T(x)

это число единиц памяти, необходимых для решения задачи размера

Пространственная

x в худшем случае.

сложность S(x)

f(x) = O(g(x)), если существует такое натуральное число c > 0, что,

Арифметическая

в конце концов (т. е. начиная с некоторого x) получим f(x) c∙g(x).

функция f(x) называется

функцией одного

верхнего порядка с

функцией g(x) и

записывается …

f(x)=о(g(x)), если существует такое c > 0, что в конце концов

Арифметическая

(начиная с некоторого x) получим f(x) c∙g(x)

функция f(x) называется

функцией одного

нижнего порядка с

функцией g(x) и

записывается …

f(x) = o(g(x)) & f(x) = О(g(x)), если она одного верхнего и одного

Арифметическая

нижнего порядка с функцией g(x)

функция f(x) называется

функцией одного порядка

с функцией g(x) и

записывается …

это функции одного верхнего порядка с полиномами

Полиномиальные

функции

это функции одного нижнего порядка с экспонентой

Экспоненциальные

функции

если существуют такие многочлены P1(x) и P2(x), что, в конце

Арифметические

концов (начиная с некоторого числа) f(x) P1∙g(x) и g(x) P2∙f(x)

функции f(x) и g(x)

называются

полиномиально-

связанными или

полиномиально-

эквивалентнтными

это алгоритм, обе функции сложности которого полиномиальные

Полиномиальный

алгоритм

это алгоритм, у которого хотя бы одна из двух функций сложности

Экспоненциальный

экспоненциальная

алгоритм

это задача, решаемая полиномиальным алгоритмом

Легкоразрешимая задача

это задача, которую нельзя решить полиномиальным алгоритмом

Трудноразрешимая

задача