Формы представления алгоритмов.

На практике наиболее распространены следующие формы представления алгоритмов: словесная (записи на естественном языке); графическая (изображения из графических символов); псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.); программная (тексты на языках программирования).

Как фундаментальное научное понятие алгоритм требует обстоятельного изучения. Оно невозможно без уточнения понятия «алгоритм», без его формализации. Известно, несколько подходов к формализации понятия «алгоритм»: • теория конечных и бесконечных автоматов; • теория вычислимых (рекурсивных) функций; • -исчисление Черча. Все эти возникшие исторически независимо друг от друга подходы оказались впоследствии эквивалентными. Главная цель формализации понятия алгоритма такова: подойти к решению проблемы алгоритмической разрешимости различных математических задач, т.е. ответить на вопрос, может ли быть построен алгоритм, приводящий к решению задачи. Мы рассмотрим постановку этой проблемы и некоторые результаты тео­рии алгоритмической разрешимости задач, но вначале обсудим формализацию понятия алгоритма в теории автоматов на примере машин Поста, Тьюринга, а также нормальных алгоритмов Маркова, а затем — основы теории рекурсивных функций. Идеи исчислений Черча реализованы в языке программирования Лисп. Вместе с тем, формально определенный любым из известных способов алго­ритм не может в практическом программировании заменить то, что мы называли алгоритмами в предыдущем подразделе. Основная причина состоит в том, что фор­мальное определение резко сужает круг рассматриваемых задач, делая многие прак­тически важные задачи недоступными для рассмотрения.

Пон-ие алг-ма в И. явл-ся фундам-ным. Алгоритм - заранее заданная послед-сть четко определенных правил или команд для пол-ия реш-ия з-чи за конеч. число шагов.

Алг-м - понятное и точное предписание исполнителю совершить послед-сть действий, напр-ых на достиж-ие опр-ых целей или на реш-ие пост-ой з-чи.

Св-ва: 1.Массовость - кажд. алг-м справедлив для к-л мн-ва исх. данных 2.Дискретность - алг-м д/б разбит на послед-сть отдельных действий; только после вып-ия одного действия переходят к вып-ию след-го 3. Определенность и однозначность - формул-ка алг-ма д/б точна и однозначна 4. Конечность - алг-м д. всегда зак-ся после конеч. числа шагов 5. Детерминированность (предопределение) - все действия и указания однозначны; не д/б неясных ситуаций 6. Результативность - после заверш-ия исполнения алг-ма всегда д/б получен рез-т.

Способы опис-ия алг-мов: словесная запись, алгор. язык, формула, блок-схема, структурограмма.

Словесная запись предст-ет собой перечисл-ие прост-х действий, кот. нужно вып-ть для пол-ия рез-та, в той послед-ти, в какой они д. вып-ся, и явл-ся записью в виде высказываний на обычном разговорном ззыке.

Граф. изобр-ие алг-ма наз-ся структурной схемой алг-ма (блок-схемы и структурограммы).

Б-с явл-ся ориент-м графом, у кот. графич. обозн-ия эл-тов соотв-ют вершинам графа, линии потока - его ребрам. Граф - конечное мн-во вершин, соед. ребрами.

Алг-м из-ся в виде послед-ти блоков, предписывающих вып-ие отд-ых ф-ций, и связей м/у ними. Внутри блоков помещают инф-ию, кот. поясняет вып-ие действия. Б-с показывают орг-ию алг-ма и е отр-ют орг-ию данных или структуру модулей ввода-вывода.

Структурограммы дают полное визуальноепредставление процесса упр-ия в структуриров-ой программе.

АЯ - искусств. формализ-ая система символов, усл-ых обозн-ий, знаков операций и т.п., а также правил точной и единообразной записи алг-мов (алфавит, словарь).

 

6. Граф. Вершины и ребра графа. Виды графов. Пути. Связность, мосты и точки сочленения. Компоненты связности. Двудольный граф. Способы задания графа.

Теория Г. – удобн. язык в описании программ-х моделей. Граф – это сов-сть точек и линий в к-рой каждая линия соедин. 2 точки. Точки – вершина Г. Линии – ребра Г. Г. G=G(V,E) это пара двух множеств V-кон-ое множество вершин, Е- двухэлементные подмнож-ва из множ-ва V. G=({V₁,:,V_n},{(V₁,V₂), (V₂,V₃),:, (V₁,Vn)}).Если ребро е=(V₁,V₂) Г G, тогда V₁-смежна с вершиной V₂ и наоборот. Ребро е инцидентно вершине V₁ и V_2. Любые две вершины инцидентны одному ребру – смежные. Два ребра инцидентны одной вершине – смежные. Если 2 ребра инцидентны 1 и той же паре вершин – кратные рёбра. Если Е=0, то граф пустой. Если каждому ребру приписано направление – граф направленный.

Т.1. Пусть Т дерево с мн-ом вершин V и мн-вом рёбер Е, тогда: 1.Для кажд. пары различных вершин сущест. единст-ый путь в Т связ-щий их; 2. Удаления любого ребра из Т прив-ит к обр-ию Г. с 2мя компон-ми, каждое из кот. яв-ся деревом;

3. Кол-во рёбер |Е|=|V|-1.

Связ-ый Г. удовл-ий люб. из этих условий явл. деревом

Граф –– это множество точек называемых ребрами которые соединяют пары вершин или вершину саму с собой в виде дуги.

Т.1. Пусть Г произ-ый плоский граф с числом вершин |V|,с числом рёбер|E|, кот-ый разбивает пл-ть на |F|граней, тогда |F|=|E|-|V|+2.

Элементы теории графов. Фигура, состоящая из точек (вершин) и соединяющих их линий (ребер), называется графом. Граф называется связанным, если любая пара его вершин связанна.

Ориентированные графы. Для указания направления связи между вершинами графа соответствующее ребро отмечается стрелкой. Ориентированное таким образом ребро называют дугой, а граф с ориентированными ребрами – ориентированным графом:

Взвешенные графы. Дальнейшее обобщение отображения связей между объектами с помощью графов состоит в приписывании ребрам и дугам некоторых количественных значений, качественных признаков или характерных свойств, называемых весами. В простейшем случае это может быть порядковая нумерация ребер и дуг, указывающая на очередность при их рассмотрении (приоритет или иерархия). Вес ребра или дуги может означать длину (пути сообщения), количество набранных очков (турниры), характер отношений между людьми (сын, брат, отец, подчиненный, учитель и т.д).

Вес можно приписывать не только ребрам и дугам, но и вершинам (вес вершины означает любую характеристику соответствующую ей объекта (цвет, изображенного вершиной предмета, возраст человека и т.д.)

Способы задания графа:

Явное задание графа как алгебраической системы

<{a,b,c,d},{u,v,w,x}; {(u,a),(u,b),(v,b),(v,c),(w,c),(w,a),(x,c), (x,d)}>.

Геометрический – рисуются вершины и грани на плоскости.

Степенью вершины назовём удвоенное количество петель, инцидентных этой вершине плюс количество остальных инцидентных ей рёбер.

Подграфом графа называется граф, являющийся подмоделью исходного графа. Иначе говоря, подграф содержит некоторые вершины исходного графа и некоторые рёбра (только те, оба конца которых входят в подграф).

Подграфом, порождённым множеством вершин U называется подграф, множество вершин которого – U, содержащий те и только те рёбра, оба конца которых входят в U.

Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

Пустым называется граф без рёбер. Полным называется граф, в котором каждые две вершины смежны.

Графы часто используют для изображения различных отношений (например, иерархических отношений, т.е., на языке математики – отношений частичного порядка).