Уроки по программированию
 
 
Элементы теории графов.

Граф - совокупность точек и линий, в которой каждая линия соединяет две точки. Точки называются вершинами, или узлами, графа, линии - ребрами графа. Если ребро соединят две вершины, то говорят, что оно им инцидентно; вершины, соединенные ребром называются смежными.  Две вершины,  соединенные ребром,  могут совпадать; такое ребро называется петлей.  Число ребер, инцидентных вершине, называется степенью  вершины.  Если  два ребра инцидентны одной и той же паре вершин,  они называются  кратными;  граф,  содержащий кратные ребра, называется мультиграфом. 

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

  Граф однозначно задан,  если заданы множество его вершин,  множество ребер и указаны все  инцидентности  (т.е.  указано,  какие вершины какими ребрами соединены). Наиболее наглядно граф задается рисунком;  однако не все детали  рисунка  одинаково  важны;  в частности, несущественны  геометрические  свойства ребер (длинна, кривизна и т.д.) и взаимное расположение вершин на плоскости.

  Для неориентированного ребра порядок, в котором указанны соединяемые им вершины,  не важен.  Для ориентированного  ребра  важно: первой указывается вершина, из которой выходит ребро.

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

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

  Задача состоит в том,  найти путь из вершины A в вершину B. Будем задавать граф матрицей смежности,  т.е.  квадратной  таблицей NxN,  в которой на пересечении i-й строки и j-го столбца значение TRUE, если i и j соединены ребром, и FALSE в противном случае.

Поиск в ширину.

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

  Для реализации алгоритма понадобятся: 

  матрица m[1..n, 1..n] - матрица смежности графа;

  вспомогательный массив  queue[1..n],  в  котором будет формироваться очередь, т.е. тип данных первый вошел – первый вышел (FIFO). Размер его достаточен,  так как мы не посещаем вершины дважды. С массивом queue связаны две переменные - head и tail. В переменной head будет находиться номер текущей вершины,  из которой идет волна, а при помощи  переменной  tail  новые  вершины  помещаются  в "хвост" очереди queue;

  вспомогательный массив visited[1..n],  который нужен для  того, чтобы отмечать уже пройденные вершины (visited[i]=TRUE <=> вершина i пройдена);

  вспомогательный массив  prev[1..n] для хранения пройденных вершин. В этом массиве и будет сформирован искомый путь;

  переменная f,  которая  примет значение TRUE,  когда путь будет найден.

  Кроме того, мы введем несколько вспомогательных переменных, которые понадобятся при организации циклов.

  Program breadth_first_search;

  Const n=9;

        m:array[1..n, 1..n] of boolean =

        (

           (False, True,  True,  False, False, False, False, False, False),

           (True,  False, True,  False, False, False, True,  True,  False),

           (True,  True,  False, True,  True,  False, False, False, False),

           (False, False, True,  False, True,  False, False, False, False),

           (False, False, True,  True,  False, True,  False, True,  False),

           (False, False, False, False, True,  False, True,  True,  True ),

           (False, True,  False, False, False, True,  False, True,  True ),

           (False, True,  False, False, True,  True,  True,  False, False),

           (False, False, False, False, False, True,  True,  False, False)

        );

  Var A, B: integer;

 

   Procedure A_to_B(A, B: integer);

   Var

        Visited: array[1..n] of boolean;

           Prev: array[1..n] of integer;

           c: array[1..n] of integer;

     head, tail: integer;

              f: boolean;

        i, v, k: integer;

   Begin

     head:=1;

     tail:=1;

     f:=False;

     For i:=1 to n do

     Begin

       Visited[i]:=False;

       Prev[i]:=0

     End;

     C[tail]:=A;

     Visited[A]:=True;

     While (head<=tail) and not f do

     Begin

       v:=C[head];

       head:=head+1;

       For k:=1 to n do

         if m[v, k] and not Visited[k] then

                                       Begin

                                         tail:=tail+1;

                                         C[tail]:=k;

                                         Visited[k]:=True;

                                         Prev[k]:=v;

                                         if k=B then

                                                Begin

                                                  f:=true;

                                                  break

                                                End

                                       End

     End;

     if f then

          Begin

            k:=B;

            Write(B);

            While Prev[k]<>0 do

            Begin

              Write('<-', Prev[k]);

              k:=Prev[k]

            end

          End

          else

               Write('Пути из ', A, ' в ', B, ' нет')

   end;

 

  Begin

    Write('A= '); readln(A);

    Write('B= '); readln(B);

    A_to_B(A, B)

  End. 
 
 
     Ресурсы школьного сайта  здесь             
   Проверь себя тесты 
Интернет-ресурсы для самообразования
 
    Полный учебник по Турбо Паскаль можно найти по адресу:    http://www.lyc.zelenogorsk.ru/project/ebook/pascal/
 
 
Всем, кто хочет научиться работать в Power Point рекомендуем учебник на сайте
 
 Графический редактор CorelDRAW! является объектно-ориентированным векторным редактором. Это означает что CorelDRAW работает с изображением, состоящим из отдельных объектов, каждый из которых описывается математически.Для самообучения обратиться в http://www.lyc.zelenogorsk.ru/project/ebook/cdr/index.shtml
 
Практическое руководство по HTML.
 
 Все для web-дизайна и раскрутки сайта
 
 Обучение Flash и Html, Ява скрипты (Java scripts), полезные программы, гостевая книга, форум, голосование, ЧАТ.
http://www.search.ru/CATRL?id=27692&id2=45&url=http://ascity.narod.ru
 
Ресурс, посвящён технологиям и способам разработки веб-сайтов. Статьи по написанию скриптов на различных языках веб-программирования, хитрости при создании дизайна, статьи по раскрутке сайтов... Всё очень подробно.

Ресурсы подраздела предназначены для администрации, методистов и учителей образовательных учреждений.

 

Министерство образования и науки Российской Федерации

http://www.mon.gov.ru

Федеральная служба по надзору в сфере образования и науки (Рособрнадзор)

http://www.obrnadzor.gov.ru

Федеральное агентство по образованию (Рособразование)

http://www.ed.gov.ru

Федеральное агентство по науке и инновациям (Роснаука)

http://www.fasi.gov.ru

 

Приоритетные национальные проекты: сайт Совета при Президенте Россиийской Федерации по реализации приоритетных национальных проектов и демографической политике

http://www.rost.ru

Федеральная целевая программа развития образования (2006–2010) — ФЦПРО

http://www.fcpro.ru

Национальный фонд подготовки кадров. Приоритетный национальный проект «Образование» и проект «Информатизация системы образования»

http://portal.ntf.ru

Статистика российского образования

http://stat.edu.ru

 

Академия повышения квалификации и профессиональной переподготовки работников образования РФ

http://www.apkppro.ru

Государственый научно-исследовательский институт информационных технологий и телекоммуникаций (ГНИИ ИТТ «Информика»)

http://www.informika.ru

Национальное аккредитационное агентство в сфере образования

http://www.nica.ru

Федеральный институт педагогических измерений

http://www.fipi.ru

Федеральный совет по учебникам Министерства образования и науки РФ

http://fsu.mto.ru

Федеральный центр образовательного законодательства

http://www.lexed.ru

Федеральный центр тестирования

http://www.rustest.ru

 

 

Федеральный портал «Российское образование»

http://www.edu.ru

Российский общеобразовательный портал

http://www.school.edu.ru

Портал информационной поддержки Единого государственного экзамена

http://ege.edu.ru

Естественнонаучный образовательный портал

http://www.en.edu.ru

Федеральный образовательный портал «Экономика. Социология. Менеджмент»

http://www.ecsocman.edu.ru

Федеральный портал «Инженерное образование»

http://www.techno.edu.ru

Федеральный портал «Социально-гуманитарное и политологическое образование»

http://www.humanities.edu.ru/

Федеральный правовой портал «Юридическая Россия»

http://www.law.edu.ru

Федеральный портал «Информационно-коммуникационные технологии в образовании»

http://www.ict.edu.ru

Российский портал открытого образования

http://www.openet.edu.ru

Образовательный портал по поддержке процессов обучения в странах СНГ

http://www.sng.edu.ru

Федеральный портал «Дополнительное образование детей»

http://www.vidod.edu.ru

Федеральный портал «Непрерывная подготовка преподавателей»

http://www.neo.edu.ru

Федеральный специализированный информационный портал «Сравнительная образовательная политика»

http://comparative.edu.ru