Начальные понятия дескриптивной теории алгоритмов
В отличие от метрической теории алгоритмов, дескриптивная теория не занимается измерением ресурсов (таких как время, объём памяти), затрачиваемых при применении алгоритма к его возможным исходным данным (в другой терминологии — к его входам). Её интересует лишь, возможен алгоритм для решения данной задачи или нет. Начальные понятия дескриптивной теории алгоритмов суть:
- конструктивный обьект;
- алгоритм;
- число шагов алгоритма;
- вычислимая функция;
- перечислимое множество;
- разрешимое множество;
- сводимость нумераций;
- главная вычислимая нумерация;
- вычислимая операция.
Между этими понятиями существуют соотношения, хотя в большинстве своём и простые, но всегда достаточно глубокие.
В лекции предполагается разьяснить указанные понятия и соотношения. Предварительных знаний, помимо знакомства с общим представлением о значении слов «множество», «функция», «упорядоченная пара», не требуется.
Успенский Владимир Андреевич, доктор физико-математических наук, профессор.
Летняя школа «Современная математика», г. Дубна
20 и 22 июля 2009 г.
Похожее
-
Владимир Успенский
Целые числа, рациональные, алгебраические… Что дальше (оставаясь в пределах действительных чисел)? Дальше идут вычислимые действительные числа, т.е. такие действительные числа, которые можно в разумном смысле вычислить. «Можно вычислить» означает, что вычисление можно запрограммировать. Мыслимы различные подходы к тому, что именно надо программировать.
-
Алексей Семёнов
«Качественная» теория алгоритмов (не касающаяся понятия сложности вычислений) может быть построена на интуитивном представлении о том, что такое алгоритм. Такого представления, при некотором его уточнении, оказывается достаточно для того, чтобы доказать первые базовые теоремы теории алгоритмов. В лекции будет приведено указанное уточнение, определено понятие вычислимости и понятие породимости («выводимости в формальной системе»), доказано несколько теорем, другие теоремы — предложены в качестве задач. Будут приведены и примеры т.н. «уточнения понятия алгоритма». Для понимания лекции желательно умение читать по-русски, знание латинского алфавита и представление о натуральном ряде.
-
Владимир Успенский
Составленная из нулей и единиц цепочка 100010111011110100000111 выглядит более случайной, чем цепочка 010101010101010101010101. Возможно ли разделить все цепочки нулей и единиц на случайный и не случайные? Для конечных цепочек эта задача вряд ли осуществима. Однако можно пытаться решать её для бесконечных цепочек, т.е. для последовательностей. Иными словами, можно пытаться найти строгое математическое определение для понятия «случайная последовательностей нулей и единиц».
-
Питер Эткинз
Эта книга предназначена для широкого круга читателей, желающих узнать больше об окружающем нас мире и о самих себе. Автор, известный ученый и популяризатор науки, с необычайной ясностью и глубиной объясняет устройство Вселенной, тайны квантового мира и генетики, эволюцию жизни и показывает важность математики для познания всей природы и человеческого разума в частности.
-
Владимир Успенский
Знаменитая Теорема Гёделя о неполноте имеет две версии — синтаксическую (объявленную и доказанную самим Гёделем) и семантическую (чаще всего фигурирующую в популярных рассуждениях о великой Теореме). Семантическая версия утверждает, что какую бы систему формальных доказательств ни придумать, в языке найдутся истинные утверждения, не доказуемые в рамках предложенной системы. Таким образом, семантическая версия исходит из того, что некоторые выражения языка выражают осмысленные утверждения, являющиеся истинными или ложными. Синтаксическая версия не опирается на то, что какие бы то ни было выражения языка имеют какой-то смысл, она смотрит на выражения как на синтаксические конструкции, то есть как на цепочки символов, организованные по определённым правилам.
-
Алексей Сосинский
Курс занятий посвящен тому, что в математике сделать нельзя. Но речь пойдет не о запрещенных действиях (типа деления на ноль или квадратуры круга), а об отсутствии общих методов для решения некоторых широких классов задач. Начиная от определения вычислимой функции (через машину Тюринга), мы узнаем про существование универсальной вычислимой функции, и как следствие – о существовании не вычислимых функций. Отсюда мы поймем, какие задачи никакой компьютер (даже сколь угодно мощный) решить не может в принципе. Затем мы определим «Колмогоровскую сложность» и изучим ряд ее «нехороших» свойств, именно, не вычислимость некоторых связанных с ней характеристик. Эти свойства сыграют решающую роль в доказательстве теоремы Гёделя о неполноте – одного из самых значительных научных открытий ХХ-го века.
-
Владимир Успенский
Действительно ли в математике всё определяется и доказывается? Можно ли определить понятие натурального числа? Можно ли определить Натуральный Ряд (с прописной буквы)? Можно ли аксиоматически определить понятие натурального ряда (со строчной буквы)? Можно ли доказать, что Великую теорему Ферма нельзя ни доказать, ни опровергнуть? Что такое доказательство? Можно ли математику сделать понятной?
-
Владимир Успенский
Если в качестве значений переменных разрешается брать только элементы носителя, язык называют элементарным языком, или языком первого порядка. Если же в качестве значений переменных разрешается брать также функции и отношения, язык называют языком второго порядка. Выразительные возможности языков первого порядка довольно ограничены. Например, на языке первого порядка можно сообщить, что носитель содержит ровно 17 элементов, но невозможно выразить его конечность. На языке второго порядка выразить конечность носителя возможно. Возникает совершенно естественное недоумение: а зачем тогда пользоваться языками первого порядка с их бедными выразительными средствами, не лучше ли пользоваться языками второго порядка?
-
Александр Шень
Сколько нужно вопросов (с ответом “да” и “нет”), чтобы заведомо отгадать задуманное число от 1 до 1000? Можно ли обойтись меньшим числом вопросов? Если нет, то как это доказать? Сколько нужно взвешиваний на чашечных весах без гирь, чтобы наверняка выделить более лёгкую монету среди 1000 одинаковых на вид? С такого рода вопросов начинается наука о сложности алгоритмов, и очень скоро доходит до важных, но до сих пор не решённых задач.
-
Александр Шень
Природа статистических законов вызывала споры с самого рождения теории вероятностей и продолжает их вызывать. Эти философские споры привели к рождению интересной математической теории: алгоритмической теории вероятностей и информации, которая — в отличие от классической — пытается дать определение индивидуального случайного объекта. Мы обсудим основные понятия этой теории и их связь с основаниями и парадоксами теории вероятностей. Об этом в публичной лекции математика Александра Шеня, кандидата физико-математических наук, старшего научный сотрудник Лаборатории теории передачи информации и управления ИППИ РАН.
Далее >>>
|
|
