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

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

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

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

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

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

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

1. Приглашение

1 урок
Закрытый
1.1 Теоретическая информатика и теория вычислимости ↗
4 197
956
13м 39с
45

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

6 уроков
Закрытый
2.1 Вычислимость, разрешимость, перечислимость ↗
1 242
140
24м 29с
35
Закрытый
2.2 Свойства перечислимых множеств, теорема Поста ↗
626
56
27м 38с
10
Закрытый
2.3 Графики, проекции ↗
436
92
19м 59с
6
Закрытый
2.4 Проблема остановки: перечислимое неразрешимое множество ↗
333
82
37м 14с
4
Закрытый
2.5 Вычислимые действительные числа ↗
279
33
19м 52с
2
Закрытый
2.6 Отступление: вычислимые функции и конструктивные рассуждения ↗
246
83
10м 16с
4

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

9 уроков
Закрытый
3.1 Интерпретаторы, программы, универсальные функции ↗
276
68
7м 28с
8
Закрытый
3.2 Гёделевы универсальные функции ↗
247
17
50м 50с
5
Закрытый
3.3 Св-ва гёделевых универсальных ф-й. Теорема Райса–Успенского ↗
203
10
25м 29с
2
Закрытый
3.4 У любой функции бесконечно много программ ↗
188
4
12м 39с
1
Закрытый
3.5 Отступление: перечислимые неотделимые множества ↗
182
55
17м 12с
1
Закрытый
3.6 Теорема о неподвижной точке и её следствия ↗
192
59
19м 1с
2
Закрытый
3.7 Доказательства теоремы о неподвижной точке ↗
163
11
23м 20с
1
Закрытый
3.8 Самоприменимость, парадокс лжеца, теорема Гёделя ↗
171
61
14м 11с
0
Закрытый
3.9 λ-исчисление ↗
212
58
12м 46с
2

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

5 уроков
Закрытый
4.1 Мотивировка и примеры ↗
284
124
22м 33с
3
Закрытый
4.2 Формальное определение ↗
211
62
11м 44с
3
Закрытый
4.3 Модификации и их последствия ↗
189
98
19м 48с
3
Закрытый
4.4 Оценки времени работы ↗
189
11
228м 47с
3
Закрытый
4.5 Тезис Чёрча–Тьюринга ↗
197
14
5м 3с
2

5. Конвей и FRACTRAN

3 урока
Закрытый
5.1 Как доказывать неразрешимость? ↗
190
11
77м 3с
2
Закрытый
5.2 Минимальный язык ↗
183
55
15м 44с
2
Закрытый
5.3 Сведение программ к пасьянсам ↗
178
43
14м 17с
2

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

2 урока
Закрытый
6.1 Определение и примеры ↗
184
14
33м 50с
1
Закрытый
6.2 Неразрешимость проблемы эквивалентности ↗
169
9
19м 37с
1