С. А. Турбекова русский язык. Самостоятельная работа
Понятие вспомогательного алгоритма
жүктеу/скачать 1,62 Mb. Pdf көрінісі
|
Адскова
- Бұл бет үшін навигация:
- Понятие графа. Способы представления графа
| Понятие вспомогательного алгоритма
Алгоритм решения задачи проектируется путем декомпози- ции всей задачи в отдельные подзадачи. Обычно подзадачи реа- лизуются в виде подпрограмм. Подпрограмма – это некоторый вспомогательный алгоритм, многократно использующийся в основном алгоритме с различны- ми значениями некоторых входящих величин, называемых пара- метрами. Подпрограмма в языках программирования – это последова- тельность операторов, которые определены и записаны только в одном месте программы, однако их можно вызвать для выполне- ния из одной или нескольких точек программы. Каждая подпро- грамма определяется уникальным именем. В языке Pascal существуют два типа подпрограмм – процеду- ры и функции. Процедура и функция – это именованная последо- вательность описаний и операторов. При использовании проце- дур или функций программа должна содержать текст процедуры или функции и обращение к процедуре или функции. Параметры, указанные в описании, называются формальными, указанные в обращении подпрограммы – фактическими. Все формальные па- раметры можно разбить на следующие категории: 1) параметры-переменные; 2) параметры-константы; 3) параметры-значения; 4) параметры-процедуры и параметры-функции, т. е. параме- тры процедурного типа; 5) нетипизированные параметры-переменные. Тексты процедур и функций помещаются в раздел описаний процедур и функций. ( Источник : Цветкова А.В. Информатика и информационные технологии. Конспект лекций. – М.: Эксмо, 2007. – 192 с.) 28 Задание 5. Прочитать текст. Отметить особенности лексики научного стиля. Привести примеры, распределив слова по трём группам. Понятие графа. Способы представления графа Граф – пара G = (V, E), где V – множество объектов произ- вольной природы, называемых вершинами, а Е – семейство пар ei = (vil, vi2), vijOV, называемых ребрами. В общем случае множе- ство V и (или) семейство Е могут содержать бесконечное число элементов, но мы будем рассматривать только конечные графы, т. е. графы, у которых как V, так и Е конечны. Если порядок эле- ментов, входящих в ei, имеет значение, то граф называется ориен- тированным, сокращенно – орграф, иначе – неориентированным. Ребра орграфа называются дугами. В дальнейшем будем считать, что термин «граф», применяемый без уточнений (ориентирован- ный или неориентированный), обозначает неориентированный граф. Если е = При этом говорят, что ребро е является смежным (инцидентным) каждой из вершин v и и. Вершины v и и также называются смеж- ными (инцидентными). В общем случае допускаются ребра вида е = петлями. Степень вершины графа – это число ребер, инцидентных данной вершине, причем петли учитываются дважды. Поскольку каждое ребро инцидентно двум вершинам, сумма степеней всех вершин графа равна удвоенному количеству ребер: Sum(deg(vi), i=1…|V|) = 2 * |E|. Вес вершины – число (действительное, целое или рациональ- ное), поставленное в соответствие данной вершине (интерпрети- руется как стоимость, пропускная способность и т. д.). Вес, длина ребра – число или несколько чисел, которые интерпретируются как длина, пропускная способность и т. д. Путем в графе (или маршрутом в орграфе) называется чере- дующаяся последовательность вершин и ребер (или дуг – в ор- графе) вида v0, (v0,v1), v1…, (vn – 1,vn), vn. Число n называется длиной пути. Путь без повторяющихся ребер называется цепью, без повторяющихся вершин – простой цепью. Путь может быть 29 замкнутым (v0 = vn). Замкнутый путь без повторяющихся ребер называется циклом (или контуром в орграфе); без повторяющихся вершин (кроме первой и последней) – простым циклом. Граф называется связным, если существует путь между лю- быми двумя его вершинами, и несвязным – в противном случае. Несвязный граф состоит из нескольких связных компонент (связ- ных подграфов). ( жүктеу/скачать 1,62 Mb. Достарыңызбен бөлісу:
|