На главную страницу ЛШСМ-2009 К списку курсов ЛШСМ-2009

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

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

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

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

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

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

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


Rambler's Top100