Сколько стоит курс «Введение в теоретическую информатику»?

Курс «Введение в теоретическую информатику» доступен бесплатно.

Сколько времени занимает прохождение курса «Введение в теоретическую информатику»?

Прохождение курса «Введение в теоретическую информатику» занимает примерно 27 часов.

Какой рейтинг у курса «Введение в теоретическую информатику»?

Курс имеет рейтинг 4.0 из 5 на основе 9 отзывов. На курсе обучается 21 589 учеников.

Выдаётся ли сертификат по окончании курса?

Да, при успешном завершении курса выдаётся сертификат от платформы Stepik. На данный момент 325 учеников получили сертификат (1.5% завершаемость).

Где можно пройти курс «Введение в теоретическую информатику»?

Курс доступен на образовательной платформе Stepik по адресу stepik.org/course/104.

Курс на Stepik

Обложка курса «Введение в теоретическую информатику» на Stepik

Бесплатно

Введение в теоретическую информатику ★ 4.000

Name: Введение в теоретическую информатику
Availability: InStock
Rating: 4.0 (9 reviews)

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

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

Показатель	Текущие показатели		Рост
Показатель	Значение	🏆 Рейтинг	3 дн	7 дн	30 дн
Учеников на курсе	21 589
Сертификатов выдано	325
Отзывов получено	9
Рейтинг курса	4.000
Количество уроков	86
Количество квизов	111
Количество задач с кодом	118
Время прохождения курса	27 ч.	—
Обновления курса	—	—
Дата публикации курса	11 лет назад	—	—	—	—
Последнее обновление	4 года назад	—	—	—	—

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

Разделы в курсе «Введение в теоретическую информатику»

18 разделов Уроки в курсе «Введение в теоретическую информатику»

86 уроков Тесты в курсе «Введение в теоретическую информатику»

111 тестов Задачи в курсе «Введение в теоретическую информатику»

118 задач Время прохождения курса «Введение в теоретическую информатику»

27 ч.

обн. 4 года назад

Разрешающие деревья

6 уроков

1. Отгадывание числа: верхние и нижние оценки ↗

2. Отгадывание с ошибками ↗

3. Поиск максимума ↗

4. Сортировка: примеры ↗

5. Сортировка: верхние и нижние оценки для n ↗

6. Ещё несколько задач ↗

Схемы из функциональных элементов

3 урока

1. Связки, функциональные элементы, ДНФ и КНФ, полнота ↗

2. Оценки сложности. Сумма, сравнение ↗

3. Оценки сложности произвольных функций ↗

Пропозициональная логика

5 уроков

1. Формулы. Следование. Тавтологии. Выполнимость ↗

2. Следование и выводимость ↗

3. Исчисление резолюций и его полнота ↗

4. Поиск вывода или контрпримера ↗

5. Нижние оценки на поиск вывода ↗

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

5 уроков

1. Вычислимость, разрешимость, перечислимость ↗

2. Свойства перечислимых множеств, теорема Поста ↗

3. Графики, проекции ↗

4. Проблема остановки: перечислимое неразрешимое множество ↗

5. Вычислимые действительные числа ↗

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

9 уроков

1. Интерпретаторы, программы, универсальные функции ↗

2. Гёделевы универсальные функции ↗

3. Св-ва гёделевых универсальных ф-й. Теорема Райса–Успенского ↗

4. У любой функции бесконечно много программ ↗

5. Отступление: перечислимые неотделимые множества ↗

6. Теорема о неподвижной точке и её следствия ↗

7. Доказательства теоремы о неподвижной точке ↗

8. Самоприменимость, парадокс лжеца, теорема Гёделя ↗

9. λ-исчисление ↗

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

5 уроков

1. Мотивировка и примеры ↗

2. Формальное определение ↗

3. Модификации и их последствия ↗

4. Оценки времени работы ↗

5. Тезис Чёрча–Тьюринга ↗

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

2 урока

1. Определение и примеры ↗

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

Переборные задачи и их сложность

11 уроков

1. Переборные задачи ↗

2. Полиномиальные задачи ↗

3. Неразрешимые задачи ↗

4. Примеры переборных задач ↗

5. Сравнение сложности: сведение ↗

6. Переборные задачи вокруг нас ↗

7. NP-полные задачи ↗

8. Задача 3-CNF NP-полна ↗

9. Задача о независимом множестве NP-полна ↗

10. Задача о 3-раскраске NP-полна ↗

11. Задачи поиска сводятся к задачам проверки ↗

Ускорение перебора

3 урока

1. Чего мы хотим ↗

2. Задача о раскраске графа ↗

3. Задачи 2-SAT и 3-SAT ↗

Конечные автоматы

5 уроков

1. Примеры ↗

2. Формальное определение. Автоматные множества ↗

3. Недетерминизм и его устранение ↗

4. Теорема Клини ↗

5. Минимальный автомат ↗

Контекстно-свободные языки

4 урока

1. Правильные скобочные структуры ↗

2. Два типа скобок: алгоритм и грамматика ↗

3. Однозначный разбор выражений ↗

4. Контекстно-свободные грамматики и их использование ↗

Игры

2 урока

1. Игры, стратегии, кванторы ↗

2. Выигрышные и проигрышные позиции. Доказательство теоремы Цермело ↗

Коды

3 урока

1. Код с исправлением ошибок ↗

2. Верхние и нижние оценки для числа кодовых слов ↗

3. Код Хемминга ↗

Коммуникационная сложность

6 уроков

1. Постановка задачи. Пример: проверка равенства. ↗

2. Пространство вариантов и комбинаторные прямоугольники ↗

3. Вероятностная проверка равенства ↗

4. Уменьшение вероятности ошибки ↗

5. Ещё о проверке равенства: многочлены и коды ↗

6. Математическое отступление: (1 - 1/n)^n < 1/2 (три способа) ↗

Ликбез по арифметике: числа, остатки, алгоритм Евклида

8 уроков

1. Арифметика остатков ↗

2. Свойства операций, обратимые элементы ↗

3. Алгоритм Евклида ↗

4. Алгоритм Евклида: время работы ↗

5. Разложение на простые: существование и единственность ↗

6. Малая теорема Ферма. Теорема Эйлера ↗

7. Китайская теорема об остатках ↗

8. Проверка простоты по Миллеру и Рабину ↗

Криптография

3 урока

1. Секретный ключ: можно ли без него обойтись? ↗

2. Схема Диффи–Хеллмана ↗

3. Система RSA ↗

Интерактивные доказательства

3 урока

1. Требования к доказательствам: неинтерактивные соответствуют NP ↗

2. Интерактивные док-ва: интерактивное док-во для неизоморфизма ↗

3. Доказательства с нулевым разглашением ↗

Правила Хоара

3 урока

1. Инвариант цикла: примеры ↗

2. Быстрое возведение в степень ↗

3. Математики и программисты ↗