Теория вычислений
-
Теория вычислений
- Раздел информатики и математики, изучающий задачи, решаемые с помощью моделей вычислений.
- Включает теорию автоматов, формальных языков, вычислимости и сложности вычислений.
-
Теория автоматов
- Изучение абстрактных машин и вычислительных задач.
- Автоматы используются для доказательства вычислимости.
-
Теория формальных языков
- Описание языков как набора операций над алфавитом.
- Формальные языки используются для описания задач, которые должны быть вычислены.
-
Теория вычислимости
- Вопрос о том, в какой степени задача разрешима на компьютере.
- Важные результаты: проблема остановки и теорема Райса.
-
Теория вычислительной сложности
- Анализ эффективности решения задач.
- Временная и пространственная сложность алгоритмов.
- Обозначение Big O для сравнения функций.
-
Модели вычислений
- Машина Тьюринга и другие эквивалентные модели.
- Регулярные выражения, конечные автоматы, контекстно-свободные грамматики и другие формализмы.
-
Рекомендации
- Учебники по теории вычислений, формальным языкам и автоматам.
- Ссылки на веб-источники и конференции.