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

Основы информатики

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Что такое вычислимость?

Вычислимая задача

Существование алгоритма: Существует чёткая процедура решения.
Конечное время: Результат достигается за конечное число шагов.

Невычислимая задача

Отсутствие алгоритма: Невозможно решить для всех возможных входных данных.
Бесконечные вычисления: Может никогда не прийти к результату.

¹ Невычислимые задачи могут стать вычислимыми, как только для них будет найден алгоритм и/или известный алгоритм удастся завершить за конечное число шагов.

Автоматы

Определение автомата

Воображаемые машины
Помогают понять, как работают вычисления
Имеют состояния
Имеют правила переходов между состояниями

Изображение светофора как аналогия, представляющая автомат

Конечный автомат (КА)

Конечный автомат (КА)

Простые машины
Фиксированное число состояний
Нет памяти за пределами текущего состояния

Изображение светофора и состояний как аналогия для конечного автомата

Автомат с магазинной памятью (МП-автомат)

Автомат с магазинной памятью (МП-автомат)

Более мощный
Имеет состояния
Использует стековую память для более сложных решений

Изображение светофора и состояний как аналогия для автомата с магазинной памятью

Итоги

Конечный автомат (КА)

Подходит для простых задач

Автомат с магазинной памятью (МП-автомат)

Более мощный инструмент для сложных задач

Значимость

Если задача может быть смоделирована автоматом, для её решения МОЖНО реализовать алгоритм

Давайте потренируемся!

Основы информатики