Формализация понятия «алгоритм»

1. Лекция №2 Формализация понятия «алгоритм»

2.

3. Подходы к формализации понятия «алгоритм»:

• теория конечных и бесконечных автоматов;
• теория вычислимых (рекурсивных) функций;
• λ-исчисление Черча.

4.

• Цель формализации понятия алгоритма - подойти
к
решению
проблемы
алгоритмической
разрешимости различных математических задач.

5. Понятие исполнителя алгоритма

6.

7. Характеристики исполнителя алгоритма:

• - сpеда ("место обитания" исполнителя);
• - элементаpные действия;
• - cистема команд:
Для каждой команды должны быть заданы:
условия пpименимости,
pезультаты выполнения команды.
• - отказы (сбои работы исполнителя).