Блок-схемы алгоритмов.
Связи между шагами алгоритма можно изобразить в виде графа (блок-схемы) такого, как, например, следующий:
где вершинам соответствуют шаги (блоки), а дугам – переходы между шагами. Его вершины могут быть двух видов – операторы(из этих вершин выходит одно ребро) ипредикаты(или логические условия; из этих вершин выходят два ребра). Кроме того, выделяют операторы начала и конца алгоритма.
В подобных схемах шаги могут быть элементарными или могут представлять собой самостоятельные алгоритмы (блоки).
На блок-схеме хорошо видна разница между описанием алгоритма и процессом его реализации.
Описание – это граф; процесс реализации – это путь в графе. Различные пути в одном и том же графе возникают при различных данных, которые создают разные логические условия в точках разветвления.
Отсутствие сходимости алгоритма означает, что в процессе вычисления не появляются условий, ведущих к концу, и процесс идет по бесконечному пути (зацикливается).
Отметим, что блок-схема отражает связи по управлению (что делать в следующий момент, то есть какому блоку передать управление), а не по информации (где этому блоку брать исходные данные).
Очевидно, что блок-схемы являются средством описания детерминизма алгоритма.
Замечания:
На практике блок-схемы часть имеют предикаты (точки разветвления) не только двоичные, но и многозначные, важно лишь, чтобы верным был ровно один из возможных ответов.
Блок схема вида:
где блок А1 вычисляют функцию f1(x), а исходными данными для А2 являются результаты А1, называется композицией алгоритмов А1 и А2 (то есть эта блок-схема задает алгоритм, вычисляющий f2(f1(x)), то есть композицию f1 и f2)
Yandex.RTB R-A-252273-3
- Математическая логика
- Парадигмы формальной логики.
- Предмет, цель, задачи и содержание читаемого курса лекций.
- Место читаемого курса о законах и формах правильного мышления.
- Концептуальный базис математической логики.
- Построение математической логики.
- Классическая логика высказываний.
- Язык классической логики предикатов (я.Л.П.).
- Примеры:
- Алгебра логики предикатов.
- Пояснения:
- Квантификация предикатов.
- Эквивалентные преобразования кванторных формул.
- Классические логические исчисления.
- Цель классических и.В. И и.П.
- Метасимволика и.В. И и.П.
- Построение логических исчислений.
- Интуитивное (наивное) понятие алгоритма как основное первичное понятие математики.
- Основные требования к алгоритмам.
- Основная терминология теории алгоритмов.
- Основные теоремы теории алгоритмов.
- Параметры алгоритма.
- Основная гипотеза теории алгоритмов.
- Алгоритмические (формальные математические) модели.
- Блок-схемы алгоритмов.
- Машина Тьюринга. Машина Тьюринга т – название, закрепившееся за вычислительными абстрактными машинами некоторого точно охарактеризованного типа.
- 1) Пусть последовательность k0k2kzимеет видq0a2a1a4q1a1qza4a2(очевидно, что последовательность команд следующая:q0a2q1a4 dп,q1a1qza2dЛ).
- Формальное определение машины Тьюринга.
- Основной тезис Тьюринга.
- Нормальные алгорифмы (алгоритмы).
- Рекурсивные функции.
- Примитивно-рекурсивные функции.
- Оператор минимизации (- орератор).
- Основной тезис Черча.
- Алгоритмически неразрешимые проблемы.