Аннотация:
В отличие от метрической теории алгоритмов, дескриптивная теория не занимается измерением ресурсов (таких как время, объём памяти), затрачиваемых при применении алгоритма к его возможным исходным данным (в другой терминологии — к его входам). Её интересует лишь, возможен алгоритм для решения данной задачи или нет. Начальные понятия дескриптивной теории алгоритмов суть:
конструктивный обьект;
алгоритм;
число шагов алгоритма;
вычислимая функция;
перечислимое множество;
разрешимое множество;
сводимость нумераций;
главная вычислимая нумерация;
вычислимая операция.
Между этими понятиями существуют соотношения, хотя в большинстве своём и простые, но всегда достаточно глубокие.
В лекции предполагается разьяснить указанные понятия и соотношения.
Предварительных знаний, помимо знакомства с общим представлением о значении слов «множество», «функция», «упорядоченная пара», не требуется.
Обратная связь: