- Понятие алгоритма исторически возникло как фундаментальная основа любой вычислительной деятельности, однако с развитием математической логики и теории вычислимости появилась насущная необходимость в строгом определении, которое бы четко отделяло алгоритмически разрешимые задачи от неразрешимых.
- Формализация теории алгоритмов — это процесс строгого математического определения интуитивного понятия «алгоритм» с помощью формальных систем.
- Цель формализации — дать однозначное определение вычислимой функции и алгоритмически разрешимой задачи, исключив неопределённость содержательных описаний.
- Основные формализации теории алгоритмов:
- машина Тьюринга — абстрактная вычислительная машина с конечным автоматом и бесконечной лентой;
- рекурсивные функции — формализация на основе примитивных операций и рекурсии;
- алгоритмы Маркова — системы подстановок для строк;
- лямбда-исчисление — функциональный подход к вычислениям.
- Любой алгоритм может быть сведён к задаче обработки битовых строк. Принцип работы алгоритма как преобразователя битов:
- вход: битовая строка, представляющая входные данные;
- выход: битовая строка, представляющая результат;
- процесс: детерминированная пошаговая обработка, где каждый шаг зависит только от текущего состояния и обрабатываемых битов.
Информатика • 11 класс
1108
Формализация понятия алгоритма
Было полезно?
Рекомендуем
Вы учитель или ученик?
Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ
Учителю
Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников
Ученику
Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках