Владимир Андреевич Успенский

Начальные понятия дескриптивной теории алгоритмов.

В.А.Успенский планирует прочесть 1 лекцию

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

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

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

В лекции предполагается разъяснить указанные понятия и соотношения.

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

Organization Committee e-mail:
dubna@mccme.ru