Please enable JavaScript.
Coggle requires JavaScript to display documents.
Элементы теории алгоритмов - Coggle Diagram
Элементы теории алгоритмов
Алгоритм - набор инструкций для исполнителя
Теория алгоритмов
Сравнительная оценка качества алгоритмов
Доказательство алгоритмической неразрешимости
Анализ сложности алгоритмов
Действия алгоритма
В результате строит другой дискретный объект (или выдаёт сообщение об ошибке)
Обрабатывает объект по шагам
Получает на вход дискретный объект
На каждом шаге получается новый дискретный объект
Эквивалентные алгоритмы (задают одну и ту же функцию)
Модель вычислений
«процессор» (система команд и способ их выполнения)
«память» (способ хранения данных)
язык программирования (способ записи программ);
способ ввода данных
способ вывода результата
Универсальные исполнители
Машина Поста
Команды
0 - стереть метку в рабочей ячейки и записать 0
1 - поставить метку в рабочей ячейке и записать 1
Переместить каретку
? n0,n1 - если в рабочей ячейке нет метки, перейти к строке n0, иначе перейти к строке n1
Стоп - остановить машину
Нормальные алгоритмы Маркова
Машина Тьюринга
Команды
записать символ ai в текущую ячейку
переместить каретку
перейти в состояние qj