Please enable JavaScript.
Coggle requires JavaScript to display documents.
Алгоритм :check: - Coggle Diagram
Алгоритм
:check:
:!:
Обязательное условие алгоритма
:fire:Обрабатывает объект по шагам (дискретно)
Процесс заканчивается
Результат работы алгоритма известен, определён объект, который считается результатом алгоритма
Процесс не заканчивается (зацикливание)
Результат работы алгоритма не определён
:fire:Получает на вход дискретный объект
:!:
Программа для универсального исполнителя
:pen:Алгоритм записан на
понятном
исполнителю языке
:check:
Универсальный исполнитель
- это исполнитель, который может моделировать работу любого другого исполнителя (существует эквивалентный алгоритм для универсального исполнителя)
:star: Язык программирования
:star: Память
:star: Процессор
:star: Способ ввода
:star: Способ вывода
:recycle:
Виды универсальных эквивалентных исполнителей
:red_flag: Машина Тьюринга
Бесконечная лента, разбитая на ячейки (память)
Каретка (ввод данных)
Программируемый автомат (процессор)
Алфавит {0, 1, ' '}
Определение состояний: вправо, влево, точка, новое состояние
:red_flag:Машина Поста
Бесконечная лента, разбитая на ячейки
Каретка
Программируемый автомат
Алфавит и состояния: 6 команд
:check:Автомат - устройство, работающее без участия человека
:fountain_pen:
Нормальные алгорифмы Маркова (НАМ)
Строгая математическая запись алгоритма
Используют для доказательства разрешимости и неразрешимости различных задач
Выполняемые задачи
:check:
Алгоритмические задачи
Неразрешимые - соответствует невычислимой функции
:warning:
Невычислимые функции
Примеры
Проблема распознавания видимости
проблема эквивалентности
проблема останова (нельзя поручить компьютеру тестировать программы)
Разрешимые
:checkered_flag:
Функции
:tada:
Вычислимые
- для их вычисления существует алгоритм
Могут быть вычислены с помощью универсального алгоритма