Курс на Stepik
Обложка курса «Теоретическая информатика: вычислимость» на Stepik
Бесплатно

Теоретическая информатика: вычислимость 0.000

Открыть на
STEPIK.ORG

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

Показатель Текущие показатели Рост
Значение 🏆 Рейтинг 3 дн 7 дн 30 дн
Количество учеников на курсе «Теоретическая информатика: вычислимость»Учеников на курсе 4 070
Сертификаты, выданные на курсе «Теоретическая информатика: вычислимость»Сертификатов выдано 32
Отзывы о курсе «Теоретическая информатика: вычислимость»Отзывов получено 0
Рейтинг курса «Теоретическая информатика: вычислимость»Рейтинг курса 0.000
Уроки в курсе «Теоретическая информатика: вычислимость»Количество уроков 26
Тесты в курсе «Теоретическая информатика: вычислимость»Количество квизов 23
Задачи с кодом в курсе «Теоретическая информатика: вычислимость»Количество задач с кодом 41
Время прохождения курса «Теоретическая информатика: вычислимость»Время прохождения курса
Обновления курса «Теоретическая информатика: вычислимость»Обновления курса
Дата публикации курса «Теоретическая информатика: вычислимость»Дата публикации курса
Последнее обновление курса «Теоретическая информатика: вычислимость»Последнее обновление

Содержание курса

Разделы в курсе «Теоретическая информатика: вычислимость» 6 разделов Уроки в курсе «Теоретическая информатика: вычислимость» 26 уроков Тесты в курсе «Теоретическая информатика: вычислимость» 23 теста Задачи в курсе «Теоретическая информатика: вычислимость» 41 задача Время прохождения курса «Теоретическая информатика: вычислимость» 12 ч. Последнее обновление курса «Теоретическая информатика: вычислимость» обн. 1 год назад

Приглашение

1 урок
1. Теоретическая информатика и теория вычислимости

Вычислимость

6 уроков
1. Вычислимость, разрешимость, перечислимость
2. Свойства перечислимых множеств, теорема Поста
3. Графики, проекции
4. Проблема остановки: перечислимое неразрешимое множество
5. Вычислимые действительные числа
6. Отступление: вычислимые функции и конструктивные рассуждения

Программы и универсальные функции

9 уроков
1. Интерпретаторы, программы, универсальные функции
2. Гёделевы универсальные функции
3. Св-ва гёделевых универсальных ф-й. Теорема Райса–Успенского
4. У любой функции бесконечно много программ
5. Отступление: перечислимые неотделимые множества
6. Теорема о неподвижной точке и её следствия
7. Доказательства теоремы о неподвижной точке
8. Самоприменимость, парадокс лжеца, теорема Гёделя
9. λ-исчисление

Машины Тьюринга

5 уроков
1. Мотивировка и примеры
2. Формальное определение
3. Модификации и их последствия
4. Оценки времени работы
5. Тезис Чёрча–Тьюринга

Конвей и FRACTRAN

3 урока
1. Как доказывать неразрешимость?
2. Минимальный язык
3. Сведение программ к пасьянсам

Ассоциативные исчисления

2 урока
1. Определение и примеры
2. Неразрешимость проблемы эквивалентности