Главная > Документ


{добавим в очередь сразу все элементы, связанные с p^.i}

q^ .next := а[р^.i];

q := b[p^.i];

end;

p := p^.next (меняем начало очереди) end;

end;

begin (основная программа)

readln(n); {n - количество вершин}

for i :=l to n do a[i] := nil ;

readin(m); {m - количество ребер}

for i := 1 to m do {считываем ребра} begin

read(j, k) ; {ребро из j в k} {добавляем элемент в список a[j]}

new (p) ;

p^.i := k;

p^.next := a[j);

if a[j] = nil then b[j] := p;

a[j] := p;

{добавляем элемент в список a(k]}

new (p) ;

p^.i := j;

p^.next := a [k] ;

if a[k] = nil then b[k] := p;

a[k] :=p end;

{структура для описания графа создана}

(метим все вершины как непосещенные}

fillchar (vert, sizeof (vert), true);

cnt :== 0;(счетчик компонент связности)

for i : = 1 to n do if vert[i] then

begin

inc(cnt) ;

d_f_s(i) end;

writein(cnt) end.

end.

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

в) Деревья

1. Основные понятия

Деревом называют произвольный связный неориентированный граф без циклов или по другому: связный граф, содержащий N вершин и N-1 ребер. Для произвольного связного неориентированного графа G=(V,E) каждое дерево ,где T _ E называют стягивающим деревом (каркасом, остовом). Ребра такого дерева называются ветвями, а остальные ребра графа – хордами.

Число различных каркасов полного связного неориентированного помеченного графа с N вершинами было впервые найдено Кэли и равно N-1.

Пример

Граф и его каркасы.

Поиск стягивающего дерева (каркаса)

Рассмотрим для алгоритма нахождения каркаса (одного), основных на методах просмотра графа поиском в глубину и в ширину. Граф описывается матрицей смежности А, массив Nnew (array[1..N] of boolean) служит для хранения признаков вершин. Значение Nnew[i], равное true, говорит о том, что вершина с номером i еще не просмотрена. Для хранения ребер, образующих каркас, будем использовать структуру данных Tree (array[1..2,1..N] of integer).

Как при поиске в глубину, так при поиске в ширину просматриваются все вершины связного графа. Использование массива Nnew обеспечивает «подключение» очередного ребра к каркасу без образования циклов. Цикл образуется, если соединить две просмотренные вершины. В нашем случае «подключается» ребро, соединяющее просмотренную вершину с непросмотренной. По логике методов поиска в глубину и в ширину строится связный граф.

Процедура для построения каркаса связного графа методом поиска в глубину:

procedure Tree_depth (v:integer); {рекурсивная процедура}

{А, Nnew, Tree, yk – глобальные}

var i:integer;

begin

Nnew[v]:=false;

for i:=1 to N do

if (A[v,i]<>0) and Nnew[i] then

begin {добавляем ветвь в каркас}

Inc(yk); Tree[1,yk]:=v; Tree[2,yk]:=i;

Tre_Depth (i);

end;

end;

Фрагмент алгоритма, вызывающего:

begin

FillChar(Nnew,SizeOf(Nnew),true); yk:=0;

Tree_Depth(1); {строим от первой вершины}

<вывод каркаса>

end.

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

procedure Tree_Width (v:integer); {А, Tree, yk – глобальные структуры данных}

var Nnew: array[1..N] of boolean;

Turn: array[1..N] of integer;

yr,yw,i:integer;

begin

FillChar(Nnew,SizeOf(Nnew),true);

FillChar(Turn,SizeOf(Turn),0); yr:=0;yw:=0;

Inc(yw); Turn[yw]:=v; Nnew[v]:=false;

while ym<>yr do

begin

Inc(yr); v:=Turn[yr];

for i:=1 to N do

if (A[v,i]<>0) and Nnew then

begin

Inc(yw); Turn[yw]:=i; Nnew[i]:=false;

Inc(yk); Tree[1,yk]:=v; Tree[2,yk]:=i;

end;

end;

end;

Пример

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

(а) (б) (в)

рис.3

Практическая работа..

Задание 1. Муравей забрался в банку из-под сахара, имеющую форму куба. Сможет ли он последовательно обойти все рёбра куба, не проходя дважды по одному ребру?

Задание 2. Сколько получится листков бумаги, если первоначально было m листов, некоторые листы разрезали на 5 частей, а всего было разрезано k листов?

З
адание 3.
Дана карта участка реки Волошихи. Требуется обойти все 13 мостов, соединяющих острова и берега этой реки, так, чтобы каждый мост оказался пройденным не более одного раза. Возможно ли это?

Задание 4. Разработать программы поиска в глубину и поиска в ширину при различных способах описания графа.

Поурочные планы по теме

«Алгоритмы на графах»

Блок 3

Тема:Эффективные алгоритмы на графах.

Цель: Познакомить учащихся с эффективными алгоритмами на графах.

Тип занятий: Актуализация знаний и формирование новых знаний.

План:

  1. Актуализация знаний.

  2. Объяснение нового материала.

а) Волна на графе.

б) Поиск эйлерова пути в графе.

в) Пути в графах.

  1. Актуализация знаний:

Вопросы: 1. Что такое граф? Какие способы описания графа вы знаете?

  1. Какой граф называется неориентированным?

  2. Какой граф называется ориентированным? Приведите примеры.

  3. Нарисуйте два варианта графа системы «Компьютер» содержащего следующие вершины процессор, оперативная память внешняя память, клавиатура, дисплей, принтер, а) линия связи обозначает отношение «передает информацию» б) линия связи обозначает отношение «управляет».

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

2. Объяснение нового материала:

а). Волна на графе.

Рассмотрим задачу нахождения оптимального маршрута из одного населенного пункта в другой, при предположениях:

чтобы достигнуть конечного пункта быстрее, будем использовать самолет, а следовательно, строить авиационный маршрут. А поскольку самое неприятное в полете — это взлет и посадка, будем минимизировать их число. Таким образом, маршрут — это последовательность населенных пунктов А1 А2, ..., Аn, таких что из Aiв Ai+1можно долететь без промежуточных посадок. Мы имеем набор точек, ряд из которых являются ";соседними"; (в смысле беспосадочного перелета). Число соседей может быть различным у разных точек.

Маршрутом на графе называется последовательность вершин А1, А2, ..., Аn такая, что для всех k = 1, ..., п—1 вершины Аi и аi+1 связаны ребром.

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

При изображении графа его вершины обозначаются точками, а ребра — отрезками или линиями, соединяющими вершины. Например, граф с пятью вершинами а, Ь, с, d, е и ребрами (a, b), (a, с), (b, с), (с, d) и (d, е) можно изображать так:

Рис. 1

Простейшим способом описания графа, содержащего п вершин, является таблицасмежности размера nxп. Она строится так: вершины графа перенумеровываются, и на пересечении i-й строки с j-м столбцом записывается 1, если вершины с номерами i и j связаны между собой ребром, и 0 в противном случае. Так, таблица смежности для графа, изображенного на рис. 1 с нумерацией вершин в алфавитном порядке, имеет вид:

0 1 1 0 0

1 0 1 0 0

1 1 0 1 0

0 0 1 0 1

0 0 0 1 0

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

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

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

  1. Поле 2 3 0

информации

  1. Поле 1 3 0

информации

  1. Поле 1 2 4 0

информации

  1. Поле 3 5 0

информации

  1. Поле 4 0

информации

Массив записей: каждый Списки создаются динамически

элемент массива содержит в процессе работы программы

имя вершины (номер) и ука-

затель на список соседних

с ней вершин. Этот массив

создается статически (перед

началом работы программы)

рис. 2

Ниже приведены описание данных и процедура создания списковой структуры для представления графа:

(...)

const max_graf = 100; { максимальное число вершин графа)

type list = ^elem;

elem = record

num : integer;

next : list;

end;

var Graf : array(1..max_graf] of elem;

(...)

Procedure CreateGraf (n:integer) ;

(n - число вершин графа)

var a: integer;

sosed, sosedl : list;

begin

for i:=l to n do { для каждой вершины }

begin

new(sosed); { выделили память для нового элемента }

graf[i].next := sosed; { ссылка на новый элемент }

Writeln ('Для элемента ‘,i,’ введите номер очередного соседа или 0’);

repeat

Readln(a) ;

sosed^.num := a; { указатель на очередного соседа }

if а<>0 then begin

new(sosedl) ;

sosed^.next := sosedl ;

sosed := sosedl end;

until a=0 { больше соседе нет}

end

end;

Покажем, как будет выглядеть процедура распространения волны.

Procedure Wave (num_begin, num_end : integer) ;

{номера вершин начала и конца пути }

var

k : integer; { номер ";фронта волны"; }

num : integer; { номер текущей вершины }

flag : boolean; { признак необходимости строить очередной фронт }

beg_qu, end_qu, elem_qu : list; {начало, конец и элемент очереди }

Procedure Add (num : integer; var end_qu : list ) ; { добавление элемента к очереди }

var

е1em_qu : list;

begin

end_qu^.num:=num; { поместили элемент в конец очереди }

new (elem_qu); { выделили память под следующий элемент }

end qu^.next:=elem_qu; {присоединили новый элемент }

end_qu:=elem_qu

end;

Procedure Extract (var num : integer; var begin_qu : list ) ;

{извлечь элемент из списка }

var

elem_qu : list;

begin

num:=beg_qu^.num; { считали первый элемент очереди }

elem_qu:=beg_qu; { запомнили ссылку на первый элемент для последующего уничтожения } beg_qu:=beg_qu^.next; { переносим указатель начала очереди на второй элемент}

Dispose(elem_qu) { освобождаем память, уничтожив первый элемент }

end;

begin

new(elem_qu); { инициализация очереди и размещение в ней первого элемента } beg_qu:=elem qu; { очередь пока пуста ) end qu:=elem_qu;

Graf[num_begin].num := 1; { начальный этап }

Add(num_begin, end_qu); {поместили начало пути в очередь. }

flag := true; {нужно строить фронт}

while flag and (not goal) do {строим очередной фронт } begin

Extract(num, beg_qu);

{берем значение очередного элемента очереди }

k:=Graf[num].num; { число шагов до извлеченного элемента — 1 }

{ просмотреть соседей, пометить очередной фронт и добавить помеченные элементы в очередь }

ref := graf[num].next;

repeat

а:=геf^.num;

if a<>0 then begin

{обработка очередного соседа}

if Graf[a].num=0 {пометить вершину следующим фронтом} then begin

Graf[a].num := k+1;

Add(a,end_qu) end;

ref := ref.next; {переходим к следующему соседу }

end

until a=0;

if Graf [num_end] .num<>0 then_goal:=true { дошли до цели } else

if beg_qu=end_qu then flag:=false {очередь пуста} end

end;

б). Поиск эйлерова пути в графе.

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

Теорема 1. Эйлеров путь в неориентированном графе существует тогда и только тогда, когда граф связан и содержит не более двух вершин нечетной степени.

Степенью вершины v в неориентированном графе называют количество вершин, смежных с v. Таким образом, проверить эйлеровость графа не составит труда. Причем очевидно, что одна вершина с нечетной степенью в графе существовать не может, поэтому допустимым является лишь наличие двух таких вершин, одна из которых должна быть выбрана в качестве начала эйлерова пути, а вторая окажется его концом. Мы можем соединить эти вершины фиктивным ребром, сделав тем самым степени всех вершин четными, и, не снижая общности изложения, решать задачу поиска самого пути в предположении отсутствия вершин нечетной степени.

Алгоритм построения эйлерова пути начинает свою работу с произвольной вершины v, строя путь с началом в v, причем вершины этого пути помещаются в стек, а ребра удаляются из графа. Когда этот путь уже нельзя будет удлинить, включив в него новую вершину, то это означает, что из графа был удален некоторый цикл, а степень всех вершин по-прежнему осталась четной. Текущая вершина записывается в результат и извлекается из стека. Верхний элемент стека становится текущим, и путь ищется уже из него. Процесс продолжается до тех пор, пока стек не станет пустым. Приведем нерекурсивную схему реализации алгоритма, не зависящую от способов представления графа, организации стека и формы записи результата.

v := произвольная вершина графа, обычно первая;

STACK<— v; {вершина заносится в стек}

while {STACK непуст}dobegin

v:= верхний элемент стека STACK;

if {в графе еще есть вершины, связанные с v}then

begin

u := любая вершина, связанная с v;

STACK <= и;

удаляем ребро {v — и} из графа

end

else

begin

v <— STACK; (вершина удаляется из стека)

RES <— v {вершина заносится в результат}

end

end;

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

Перепишем приведенный алгоритм в виде рекурсивной подпрограммы, для простоты использующей матрицу смежности в качестве способа описания графа. Результат будем размещать в массиве res, указывать на первый свободный элемент, в котором будет глобальная переменная р.

procedure search(v: byte);

var j: byte;

begin

for j := 1 to n do

if a[v, j] =1 then begin

a[v, j] := 0; a[j, v] := 0;

search (j) end;

inc (p) ;

res [p] := v end;

в) Пути в графах.

Неориентированный граф называется связным, если существует хотя бы один путь между каждой парой вершин u и v (u<>v).

Путем от А1 до Аn в графе называется такая последовательность ребер, ведущая от А1 до Аn , в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза.

Циклом называется путь, в котором совпадают его начальная и конечная вершины.

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

Пусть дан связанный неориентированный граф, для каждого ребра которого задан неотрицательный вес. Задача состоит в нахождении такого подмножества ребер этого графа, которое по-прежнему связывает все вершины, а суммарный вес ребер из этого подмножества минимален. Такое подмножество обязательно окажется деревом (т.е. графом без циклов), ведь в любом цикле одно ребро можно удалить, не нарушая связности графа. Поэтому искомый подграф называют ";минимальным покрывающим деревом";, или ";остовом минимального веса";.

Алгоритмы, решающие эту задачу, относятся к классу так называемых жадных. Наиболее простым в реализации является алгоритм Прима. Он позволит произвести поиск кратчайшего пути во взвешенном графе. Формирование остова начинается с произвольной вершины графа. Первым в остовное дерево включается ребро наименьшего веса, выходящее из выбранной вершины. На каждом шаге к дереву добавляется ребро наименьшего веса среди ребер, соединяющих вершины этого дерева с вершинами, пока в дерево не вошедшими. При реализации важно уметь быстро выбирать требуемое ребро минимального веса. Для того чтобы на каждом шаге не пересчитывать расстояние от текущего остовного дерева до всех не вошедших в него вершин, эти расстояния удобно хранить в линейном массиве, пересчитывая его значения после добавления в остов нового элемента. Как и ранее, для пометки вершин, уже вошедших в остовное дерево, будем использовать булевский массив vert. Следующие две процедуры показывают, как для произвольного графа, вес ребер которого задается с помощью функции а (u, v) , а отсутствие ребра между двумя вершинами обозначается весом, равным (конкретное числовое значение для этого параметра подбирается исходя из условия задачи), построить остовное дерево.

procedure calc(i: integer);

{пересчитывает расстояние до остова, i -- вершина, включенная в остов последней}

var j: integer;

begin

for j : = 1to n do if not vert[j] then

if d[j ] >a(i, j) then

begin

d [ j ] := a ( i, j ) ;

res [j ] := i

end

end;

procedure build;

{строит минимальный остов}

var i, j, imin: integer;

mm: extended;

begin

fillchar(vert, sizeof(vert), false);

for i := 1 to n do d[i] :=9999;

vert[1] := true;

calc(1) ;

for j : = 1 to n - 1 do {остов состоит из n - 1 ребра}

begin

min :=9999 ;

for i := 1 to n –1 do if not vert[i] then

if min > d[i] then

begin

min := d[i] ;

imin := i

end;

vert[imin] := true;

calc(imin) ; {в остов вошло ребро imin - res[imin]}

writein(imin,' ', res[imin])

end end;

Рассмотрим алгоритм нахождения кратчайшего элементарного пути с использованием структуры данных «приоритетная очередь».

1. Добавляем в кучу стартовую вершину s с приоритетом p(s)•= 0.

2. Пока не просмотрена конечная вершина ( или куча не станет пустой, выполняем следующую последовательность шагов:

• из кучи удаляется вершина и (с минимальным приоритетом р(u));

• если эта вершина ранее удалялась из кучи, то она игнорируется;

• вершина v считается просмотренной;

• для вершины v находятся ее непросмотренные соседи w (они уже могут быть в куче) и добавляются в кучу с приоритетом p(w) = p{v) + с(u, w).

Заметим, что

1) элементами кучи может быть следующая тройка чисел:

• приоритет (это поле является ключевым);

• номер вершины;

• предшествующий элемент, т. е. тот элемент, из которого для данной вершины было вычислено значение ее приоритета;

type

zap = record

prior: integer;

n_ver: integer;

pred: integer;

end;

var

heap: array[0..n] of zap;

Num: integer;

2) одна вершина может несколько раз поместиться в кучу; приоритет, с которым вершина находится в куче, есть длина некоторого произвольного элементарного пути из стартовой вершины s в данную вершину;

3) вершина становится просмотренной при ее первом удалении из кучи; каждой вершине u ставим в соответствие потенциал, равный тому приоритету, который был у v при ее первом удалении из кучи; потенциал вершины v — длина кратчайшего элементарного пути из стартовой вершины s в данную вершину;

4) ситуация, в результате которой некоторая вершина v достается из кучи повторно, обрабатывается следующим образом: удаляем вершину u из кучи и ничего для нее не делаем; в данном случае для вершины u уже известен кратчайший элементарный путь до нее, а тот факт, что данная вершина находилась в куче с приоритетом р(u), говорит о том, что в эту вершину из стартовой вершины существует еще один элементарный путь, но его длина p(v) больше, чем длина кратчайшего элементарного пути в вершину u;

5) количество элементов в куче ограничено числом ребер. Восстановить кратчайший путь из вершины s в вершину и можно одним из следующих двух способов:

• двигаться из вершины и в вершину s по обратным дугам, для которых стоимость дуги (х, у) равна разности потенциалов вершины х и вершины у;

• двигаться из вершины v в вершину s, используя метку «предшествующий элемент».

Трудоемкость алгоритма поиска кратчайшего пути в графе равна 0(п+ т log т).

Пример: Для изображенного на рис. 2 графа найти кратчайший элементарный путь из стартовой вершины s = 1 во все вершины, достижимые из нее.

рис. 2

Далее приводится содержимое структуры данных «куча» на каждом шаге алгоритма.

1) начальное состояние кучи:

(приоритет = 0, вершина = 1, предшествующая вершина = 0);

2) вершина 1 просмотрена;

(приоритет = 1, вершина = 2, предшествующая вершина =1);

(приоритет = 5, вершина = 3, предшествующая вершина = 1);

3) вершина 2 просмотрена;

(приоритет = 5, вершина = 3, предшествующая вершина = 1);

(приоритет = 9, вершина = 4, предшествующая вершина = 2);

4) вершина 3 просмотрена;

(приоритет = 9, вершина = 4, предшествующая вершина = 2);

(приоритет = 7, вершина = 4, предшествующая вершина = 3);

5) вершина 4 просмотрена;

(приоритет = 7, вершина = 4, предшествующая вершина = 3).

После завершения работы алгоритма все вершины, достижимые из стартовой вершины s=l, имеют потенциал (на рис. 2 он записан у каждой из вершин в квадратных скобках): это длина кратчайшего элементарного пути из стартовой вершины s в данную вершину. Для восстановления самого пути можно, например, одновременно с потенциалом хранить номер той вершины, из которой данная вершина получила свой потенциал.

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

type

uk = ^el;

el = record val: integer;

c: integer;

next: uk ;

end;

var

gr: array [l..n] of uk;

z, d: zap;

begin

d.prior:=0;

d. n_ver: =s;

d.pred:=0 ;

insert_heap(d, H, Hum, code);

for i:=l to n do

begin

visible[i]:=false;

ptn[i]:=0;

ptn_ver[i]:=0 end;

while Num <> 0 do

begin

d:= delete_min_heap(H, Num, code);

if not (visible[d.n ver]) then

begin

ptn[d.n_ver]:=d.prior;

ptn_ver[d.n_ver]:=d.pred;

dop:=gr[d.n_ver];

while dop <> nil do

begin

if not(visible[dop^.val]) then

begin

z.prior:=d.prior+dop^.с;

z.n_ver:=dop^.val;

z.pred:=d.n_ver ;

insert_heap(z, H, Num, code)

end;

dop:=dop^.next

end;

visible[d.n_ver]:=true

end

end

end.

Практическая работа.

Задание 1
Дана матрица 4х4. Напишите программу определяющую, включает ли она в себя игровую фигуру, т.е. фигуру из игры ";Тетрис"; (рис. 1-7) и если включает, то указать ее номер. Считается, что фигура является игровой только в том случае, если матрица содержит ее одну.

Задание 2 Разработать прграмму нахождения кратчайшего пути между двумя заданными вершинами графа. (Путем, соединяющим вершины u и v, называют такую последовательность вершин v0 , v1 , ….,vn(n>=0), что v0=u, vn=v и для любого i

(0<=i<=n-1) vi и vi+1 смежные. Длина пути равна количеству ребер.).

Задание 3 Имеется механизм, состоящий из N расположенных в одной плоскости и свободно надетых на зафиксированные оси пронумерованных шестеренок, зубья которых сопрягаются друг с другом. Информация о механизме ограничивается тем, что для каждой шестеренки перечислены все те, с которыми она находится в непосредственном зацеплении. Напишите программу, определяющую, есть ли такая шестеренка, поворачивая которую мы приведем в движение весь механизм.

Задание 4. На участке 3 дома и 3 колодца. От каждого дома к каждому колодцу ведет тропинка. Когда владельцы домов поссорились, они задумали проложить дорогу от каждого дома к каждому колодцу так, чтобы не встречаться на пути к колодцам. Может ли осуществиться их намерение?

Задание 5. Дана карта автомобильных дорог. Найти кратчайший путь, учитывая длины дорог, из Ярославля до Новосибирска. Использовать только те города, которые отмечены флажком. Совпадет ли кратчайший маршрут, если не брать во внимание длины дорог?

Литература:

  1. Андреева Е.В. Олимпиады по информатике. Информатика №9,10-2002

  2. Ахо А.А., Хопкрофт Д.Э., Ульман Д.Д. Структуры данных и алгоритмы. М.:Вильямс,2000

  3. Вирт Н. Алгоритмы и структуры данных. СП6: Невский диалект, 2001г.

  4. Котов В.М. Соболевский Е.П. ИНФОРМАТИКА И ОБРАЗОВАНИЕ №9,10.11-2003



Скачать документ

Похожие документы:

  1. Представление информации в форме графа

    Документ
    ... графах» Блок 1 Тема: Представлениеинформации в формеграфа Цель: Познакомить учащихся с понятием графа, историей возникновения и развития теории графов, представлениеминформации в формеграфа и представлениемграфа ...
  2. Примерные программы по информатике и икт для 8-9 классов и 10-11 классов (базовый уровень) федеральный компонент государственного стандарта общего образования 8-9 класс (105 часов) информация и информационные процессы (4 часа)

    Документ
    ... текстовой информации. Представление данных ;в табличной форме. Представлениеинформации в формеграфа. Представление зависимостей в виде формул. Представление последовательности действий в форме блок-схемы ...
  3. Новосибирск 2012 Информация и информационные процессы

    Программа
    ... текстовой информации. Представление данных в табличной форме. Представлениеинформации в формеграфа. Представление зависимостей в виде формул. Представление последовательности действий в форме блок-схемы ...
  4. «01 » сентября 2010 года «01»сентября 2010 года Образовательная программа

    Программа
    ... текстовой информации. Представление данных в табличной форме. Представлениеинформации в формеграфа. Представление зависимостей в виде формул. Представление последовательности действий в форме блок-схемы ...
  5. «методы визуализации информации при помощи графов»

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

Другие похожие документы..