x, y, z

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

Алексей Семёнов

Комментарии: 0

«Качественная» теория алгоритмов (не касающаяся понятия сложности вычислений) может быть построена на интуитивном представлении о том, что такое алгоритм. Такого представления, при некотором его уточнении, оказывается достаточно для того, чтобы доказать первые базовые теоремы теории алгоритмов. В лекции будет приведено указанное уточнение, определено понятие вычислимости и понятие породимости («выводимости в формальной системе»), доказано несколько теорем, другие теоремы — предложены в качестве задач. Будут приведены и примеры т.н. «уточнения понятия алгоритма». Для понимания лекции желательно умение читать по-русски, знание латинского алфавита и представление о натуральном ряде.

Семёнов Алексей Львович, доктор физико-математических наук, профессор, академик РАН.

Летняя школа «Современная математика», г. Дубна
21 июля 2012 г.
Комментарии: 0