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

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

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

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

Показатель Текущие показатели Рост
Значение 🏆 Рейтинг 3 дн 7 дн 30 дн
Количество учеников на курсе «Теоретическая информатика: вычислимость»Учеников на курсе 4 089
Сертификаты, выданные на курсе «Теоретическая информатика: вычислимость»Сертификатов выдано 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. Неразрешимость проблемы эквивалентности ↗