x, y, z

Поиск > Публикации: вычислимость

Поля поиска:




Запрос:
Номер раздела:
Сортировать:
Публикации: 6
ПубликацияРазделКомм.
Александр Шень
План лекций: Доказуемость и недоказуемость (почему некоторые утверждения нельзя ни доказать, ни опровергнуть?); Вычислимые функции (почему некоторые функции нельзя вычислить на компьютере?); Сложность алгоритмов; Формальные языки и исчисления.
Математика ≫ Видео 0 Ø
Михаил Раскин
Вероника сидит в комнате. На улице дождь. Вероника ставит ТеХ и смотрит фехтование. Ей многое интересно. Когда закончится дождь? Не повисла ли установка ТеХа? Будет ли следующая атака по корпусу или по маске? Конечно, чтобы узнать ответ наверняка, Веронике придётся подождать. Двое физиков порождают случайный шум. Один ищет радиочастоту, где сигнал не портит помехи, его соседка водит счётчиком Гейгера. Есть много ситуаций, когда знание, происходящего не позволяет нам предсказывать дальнейшее. Я постараюсь объяснить, откуда (и как по-разному) они берутся.
Физика ≫ Видео 0 Ø
Алексей Семёнов
«Качественная» теория алгоритмов (не касающаяся понятия сложности вычислений) может быть построена на интуитивном представлении о том, что такое алгоритм. Такого представления, при некотором его уточнении, оказывается достаточно для того, чтобы доказать первые базовые теоремы теории алгоритмов. В лекции будет приведено указанное уточнение, определено понятие вычислимости и понятие породимости («выводимости в формальной системе»), доказано несколько теорем, другие теоремы — предложены в качестве задач. Будут приведены и примеры т.н. «уточнения понятия алгоритма». Для понимания лекции желательно умение читать по-русски, знание латинского алфавита и представление о натуральном ряде.
Математика ≫ Видео 0 Ø
Алексей Сосинский
Курс занятий посвящен тому, что в математике сделать нельзя. Но речь пойдет не о запрещенных действиях (типа деления на ноль или квадратуры круга), а об отсутствии общих методов для решения некоторых широких классов задач. Начиная от определения вычислимой функции (через машину Тюринга), мы узнаем про существование универсальной вычислимой функции, и как следствие – о существовании не вычислимых функций. Отсюда мы поймем, какие задачи никакой компьютер (даже сколь угодно мощный) решить не может в принципе. Затем мы определим «Колмогоровскую сложность» и изучим ряд ее «нехороших» свойств, именно, не вычислимость некоторых связанных с ней характеристик. Эти свойства сыграют решающую роль в доказательстве теоремы Гёделя о неполноте – одного из самых значительных научных открытий ХХ-го века.
Математика ≫ Видео 0 Ø
Владимир Успенский
В отличие от метрической теории алгоритмов, дескриптивная теория не занимается измерением ресурсов (таких как время, объём памяти), затрачиваемых при применении алгоритма к его возможным исходным данным (в другой терминологии — к его входам). Её интересует лишь, возможен алгоритм для решения данной задачи или нет. Начальные понятия дескриптивной теории алгоритмов суть: конструктивный обьект, алгоритм, число шагов алгоритма, вычислимая функция, перечислимое множество, разрешимое множество, сводимость нумераций, главная вычислимая нумерация, вычислимая операция.
Математика ≫ Видео 0 Ø
Владимир Успенский
Целые числа, рациональные, алгебраические… Что дальше (оставаясь в пределах действительных чисел)? Дальше идут вычислимые действительные числа, т.е. такие действительные числа, которые можно в разумном смысле вычислить. «Можно вычислить» означает, что вычисление можно запрограммировать. Мыслимы различные подходы к тому, что именно надо программировать.
Математика ≫ Видео 0 Ø