Алгоритмы на графах 10 класс план урока

Обновлено: 04.07.2024

Тема рассчитана среднего ученика, поэтому тема была усвоена почти всеми учащимися.
Цели урока выбраны не случайно, они соответствуют учебной программе и учебному материалу по учебнику Семакина И.Г.
Главный этап урока - научиться решать задачи по данной теме, которые входят в базовый уровень ЕГЭ, почти всеми ученика класса усвоено.

План
1. Организационный момент – 2 мин
2. Актуализация – фронтальный опрос - 5мин
3. Теоретический материал – (повторение, пантомима)- 5-7 мин
4. Физкультминутка (гимнастика для глаз) – 2 мин
5. Решение задач -10 мин
6. Связь с ЕГЭ (заполнение КИМ) -3 мин
7. Практическое задание - 15 мин
8. Рефлексия-2 мин
Полный текст материала Урок информатики "Структура данных. Графы"; 10 класс смотрите в скачиваемом файле.
На странице приведен фрагмент.

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

Есть мнение?
Оставьте комментарий

Упражнения на технику чтения и понимания прочитанного

Тонкости и секреты работы в Яндекс.Почте

Как работать с детьми с СДВГ в обычном классе?

Отправляя материал на сайт, автор безвозмездно, без требования авторского вознаграждения, передает редакции права на использование материалов в коммерческих или некоммерческих целях, в частности, право на воспроизведение, публичный показ, перевод и переработку произведения, доведение до всеобщего сведения — в соотв. с ГК РФ. (ст. 1270 и др.). См. также Правила публикации конкретного типа материала. Мнение редакции может не совпадать с точкой зрения авторов.

Для подтверждения подлинности выданных сайтом документов сделайте запрос в редакцию.

О работе с сайтом

Мы используем cookie.

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

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

Если вы обнаружили, что на нашем сайте незаконно используются материалы, сообщите администратору — материалы будут удалены.

Свидетельство и скидка на обучение каждому участнику

Зарегистрироваться 15–17 марта 2022 г.

Дата: 12-19.01.2016г.

Класс: 10 а

Предмет : Информатика

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

Задачи урока:

образовательные:

формирование знаний учащихся о графических средствах языка Lazarus ;

стимулирование интереса учащихся к программированию;

развивающие:

развитие памяти, внимания;

формирование познавательной активности;

развитие умения применять полученные знания при решении задач;

воспитательные:

повышение информационной культуры учащихся;

воспитание стремления к получению новых знаний;

воспитание у учащихся самостоятельности.

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

Практическая работа на компьютере.

Подведение итогов урока.

1. Организационный момент

Учитель приветствует учащихся, отмечает отсутствующих, проверяет внешний вид учащихся – соответствие одежды безопасным условиям труда.

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

Учитель знакомит учащихся с новым материалом, используя компьютерную презентацию и мультимедийный проектор.

В языке Lazarusе сть графические средства , к которым относятся графические методы и графические объекты [4].

На объектах Форма (Form) и Графическое окно (PictureBox) можно рисовать с использованием графических методов Scale , PSet , Line , Circle , Cls .

Метод Scale позволяет задать объекту новую систему координат:
object . Scale (X1, Y1) – (X2, Y2) ,
где object – имя объекта,
X1, Y1 – новые координаты левого верхнего угла объекта,
X2, Y2 – новые координаты правого нижнего угла объекта.

Метод PSet позволяет нарисовать точку:
object . PSet (X, Y) [,color] ,
где object – имя объекта,
X, Y – координаты точки,
color – цвет точки.

Метод Line служит для рисования отрезков, прямоугольников или закрашенных прямоугольников:
object . Line (X1, Y1) – (X2, Y2) [,color] [, B ] [ F ] ,
где object – имя объекта,
X1, Y1 и X2, Y2 – координаты концов отрезка или противолежащих вершин прямоугольника,
color – цвет отрезка или прямоугольника,
параметр B задает рисование прямоугольника,
параметр F – закрашенного прямоугольника (этот параметр можно использовать только вместе с параметром B ).

Метод Circle позволяет нарисовать окружность, эллипс, дугу или сектор:
object . Circle (X, Y), radius [,color, start, end, aspect] ,
где object – имя объекта,
X, Y – координаты центра окружности, эллипса, дуги или сектора,
radius – радиус окружности, эллипса, дуги или сектора,
color – цвет линии,
start и end – начальный и конечный углы дуги или сектора в радианах (могут принимать значения от –2π до +2π),
aspect – коэффициент сжатия.

Метод Cls служит для очистки объекта:
object . Cls ,
где object – имя объекта.

Если графический метод применяется к объекту Форма (Form) , то при его записи имя объекта object можно опускать.

3. Практическая работа на компьютере

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

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

Полярные координаты. Обычно точки на плоскости представляют их декартовыми координатами. Но есть и другой способ определения расположения точек на плоскости – задание полярных координат .

В этом случае имеется единственная ось и некая точка на ней, называемая полюсом. Любую точку на плоскости теперь можно определить парой чисел (r, z), где r – расстояние от полюса и z – угол между осью и прямой, соединяющей полюс и данную точку (угол изменяется в направлении против часовой стрелки от оси).

Графики в полярных координатах. Функции, в которых используются полярные координаты, будем называть функциями в полярных координатах . Например, r = Sin(z) – функция в полярных координатах. Здесь для каждого значения z из некоторой заданной области строится точка с полярными координатами (r, z). Чтобы упростить построение, обратимся снова к декартовым координатам. Точка (r, z) в полярных координатах – это то же самое, что точка (r*Cos(z), r* Sin(z)) в декартовых координатах, и именно ее мы строим.

Разместим на форме frmGraph графическое окно picGraph, в котором будет строиться график, командную кнопку cmdGraph для реализации событийной процедуры построения графика и метку lbl1 для обозначения графического окна.

Для графического окна picGraph зададим удобную систему координат, учитывающую диапазоны изменения аргумента и функции, с помощью графического метода Scale . Для рисования точек графика воспользуемся методом PSet . Для очистки графического окна используем метод Cls .

Построение графика будет производиться с помощью цикла со счетчиком, в котором значение аргумента z будет меняться от 0 до 2π с шагом 0,001.

Введем программный код событийной процедуры cmdGraph_Click () для кнопки cmdGraph:
Dim z, r As Single
Private Sub cmdGraph_Click ()
picGraph . Scale (-1.25, 1.25) - (1.25, -1.25)
For z = 0 To 2 * 3.14 Step 0.001
r = Sin (8 * z)
picGraph . PSet (r * Cos (z), r * Sin (z)), vbMagenta
Next z
End Sub

Запустим проект. Щелкнем по кнопке График .

Усовершенствуем наш проект.

Вместо использования при построении декартовых координат (r * Cos (z), r * Sin (z)), введем два дополнительных параметра a и b и построим (r * Cos (a * z), r * Sin (b * z)).

Разместим на форме два текстовых поля txtA и txtB для ввода значений переменных a и b и две метки lbl2 и lbl3 для обозначения текстовых полей (имен переменных и диапазона изменения их значений).

Внесем изменения в программный код событийной процедуры cmdGraph_Click ():
picGraph . PSet (r * Cos (Val (txtA . Text) * z), r * Sin (Val (txtB . Text) * z)), vbMagenta

Добавим две кнопки: cmdClear – для очистки текстовых полей и графического окна и cmdExit – для завершения работы приложения.

Введем программный код событийной процедуры для кнопки cmdClear:
Private Sub cmdClear_Click ()
txtA . Text = ""
txtB . Text = ""
picGraph . Cls
End Sub

Для кнопки cmdExit код событийной процедуры следующий:
Private Sub cmdExit_Click ()
End
End Sub

Запустим проект. Меняя значения a от 1 до 9 и значения b от 1 до 6, получим массу замечательных картинок.

4. Подведение итогов урока

Учитель подводит итоги урока, отмечает учащихся, успешно справившихся с работой.

5. Домашнее задание

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

Графы используют в связи с развитием теории вероятности, математической логики и информационных технологий.

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

Мультиграф — это граф, у которого пара вершин соединены несколькими ребрами. А такие ребра, которые соединяют одну и ту же пару вершин, называют кратными. Две различные вершины графа, соединенные ребром, называются смежными.

Ребро не всегда соединяет разные вершины.

Петля — это ребро, которое соединяет вершину саму с собой.

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

Степенью вершины называют количество ребер, выходящих из одной вершины. Для петли ребро выходит из вершины дважды. Обозначать степень вершины а будем как γ(а).

На рисунке 2 изображен граф с 7 вершинами.

Рис. 2

Составим список степеней вершин этого графа: γ(a)=1,γ(b)=5,γ(c)=2,γ(d)=2,γ(e)=3,γ(f)=2,γ(g)=1.

Свойства графов:

В любом графе есть, по крайней мере, две вершины, имеющие одинаковую степень.

Для любого графа количество вершин нечетной степени всегда будет четное.

Сумма степеней всех вершин графа равна удвоенному числу его ребер.

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

Рассмотрим граф на рисунке.

Замечаем, что на графе всего 6 ребер, из них 1 петли. Составим список этих ребер: AE, BC, BE, CE, DE и EE. Каждому ребру сопоставленно число:

AE — 4, BC — 10, BE — 13, CE — 15, DE — 6, EE — 2.

А ребрам AA, AB, AC, AD, BB, BD, CC, CD, DD — 0, так как не соединены.

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

Маршрут на графике — это последовательность ребер a1,a2. an, в которой конец одного ребра служит началом другого. Циклическим маршрут называется в том случае, если конец последнего ребра последовательности совпал с началом первого ребра.

Для графа, изображенном на рисунка 2, a1,a2,a3,a7,a1,a5 — маршрут, a6,a2,a5,a7 — циклический маршрут, а последовательность a7,a6,a2,a1,a4 — маршрутом не является.

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

Для графа, изображенном на рисунка 2, a1,a2,a6,a7,a4,a5,a7 — цепь, a2,a6,a7,a8,a4,a2,a6 — цикл.

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

Для графа, изображенном на рисунка 2, a1,a2,a6,a7,a4 — простая цепь, a2,a6,a7,a8,a4 — простой цикл.

Связанные вершины — это вершины a и b, для которых существует цепь, начинающаяся в a и заканчивающаяся в b.

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

Один и тот же граф может быть изображен по-разному. Например, граф на рисунке 2 тот же, что и изображен на рисунке 3.

2. Алгоритм обработки графов.

Пусть требуется граф с n вершинами и m ребрами. Поскольку из каждой вершины выходит не более чем n−1 ребер, а сумма всех степеней вершин равна удвоенному числу ребер, имеем соотношение 2m≤(n−1)n. Приведем алгоритм, в котором через SR[1:m;1:2] обозначен массив, содержащий список ребер, а через TS[1:n;1:n] обозначен массив, содержащий таблицу смежности.

Алгоритм Случайный граф

цел: n,m,i,j,k,SR[1:m;1:2];TS[1:n;1:n];

Запросить m; (* запрашивается количество ребер *)

> (* Первоначальное заполнение таблицы смежности нулями *)

Делать от i:=1 до m

Делать пока TS[j;k]:=1

> (* случайное добавление одного ребра *)

Сообщить TS[1:n;1:n]; (* в реальной программе это действие оформляется двойным циклом *)

Сообщить SR[1:m;1:2]; (* в реальной программе это действие оформляется двойным циклом *)

3.Алгоритмы поиск в глубину и поиск в ширину

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

Рассмотрим несколько таких алгоритмов, которые можно составить.

Алгоритм поиск в глубину. Пусть зафиксирована начальная вершина v0. Выберем смежную с ней вершину v1. Затем для вершины v1 выбираем смежную с ней вершину из числа еще не выбранных вершин и т.д.: если мы уже выбрали вершины v0,v1. vk, то следующая вершина выбирается смежной с вершиной vk из числа невыбранных. Если для вершины vk такой вершины не нашлось, то возвращаемся к вершине vk−1 и для нее ищем смежную среди невыбранных. При необходимости возвращаемся назад и т.д. Так будут перебраны все вершины графа и поиск закончится.

На рисунках 1 и 2 показаны реализации поиска в глубину для одного и того же графа (начальная вершина — 0).

Порядок обхода графа с помощью алгоритма поиск в глубину для рисунка 1 — 0,1,2,3,4,5,6,9,7,10,11,8, а для рисунка 2 — 0,1,2,4,5,3,6,7,8,9,10,11.

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

Если граф задан таблицей смежности, организуем одномерный массив В, число элементов в котором совпадает с числом вершин в графе. На k−м месте этого массива будем писать номер вершины, в которую мы попали на k−м шаге. Из всех смежных вершин будем выбирать вершину с наименьшим номером.

Алгоритм, реализующий поиск в глубину:

Алгоритм Поиск в глубину

Запросить G[1:n;1:n]; (*реально это действие — ввод таблицы смежности — оформляется двойным циклом*)

B[1]:=1; (*в качестве исходной взята вершина с номером 1*)

Делать от k:=2 до n

k:=1; (*счетчик количества пройденных вершин*)

m:=0; (*k - m — порядковый номер вершины для очередного шага поиска*)

Делать пока (k)

Делать от t:=1 до n

Делать от i:=1 до k

Если ( v=1 и G(B[k−m],t)=1) то

(*если существует смежная вершина, которая еще не просматривалась, то s=0*)

Если (s=0) то

Делать от k:=1 до n

Алгоритм поиск в ширину. Пусть зафиксирована начальная вершина v0. Рассматриваем все смежные с ней вершины v1,v2. vk. Затем рассматриваем смежные вершины каждой из рассмотренных вершин v1,v2. vk, и т.д. Так будут перебраны все вершины графа и поиск закончится.

На рисунках 3 и 4 показаны реализации поиска в ширину для одного и того же графа (начальная вершина — 0).

Порядок обхода графа с помощью алгоритма поиск в ширину для рисунка 3 — 0,1,2,3,4,5,6,7,8,9,12,1,0,11, а для рисунка 4 — 0,1,2,3,4,5,6,10,7,8,9,11,12.

Алгоритм, реализующий поиск в ширину:

Алгоритм Поиск в ширину

Запросить G[1:n;1:n]; (*реально это действие — ввод таблицы смежности — оформляется двойным циклом*)

B[1]:=1; (*в качестве исходной взята вершина с номером 1*)

Делать от k:=2 до n

Делать пока (G[s,t]=0 или t=s или B[t]≠0)

Если (t) то

Делать от k:=1 до n

Волновой алгоритм, мосты и точки сочленения

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

Длина цепи — это количество ребер, которые содержатся в этой цепи.

Волновой алгоритм. Исходной вершине припишем число 0. Каждой смежной с ней вершине припишем число 1. Каждой вершине, смежной с той, которая уже помечена числом 1 и не была помечена раньше, приписываем число 2. Каждой вершине, смежной той, которая уже помечена числом 2 и не была помечена раньше, приписывают число 3. И так далее до тех пор, пока такое действие можно будет производить. При этом могут оказаться вершины, добраться до которых так и не удастся.

На рисунке 1 показан результат обработки графа волновым алгоритмом после первого шага.

На рисунке 2 полностью обработанный результат обработки графа волновым алгоритмом.

Для волнового алгоритма граф указывается таблицей смежности, где таблицей смежности с 20 вершинами графа является целочисленный массив G[1:20;1:20]; результатом работы алгоритма — одномерный целочисленный массив P[1:20], для которого каждое значение элемента P[k] равно длине пути от заданной вершины с номером k. Элементу P[k] присваивается значение −1, если вершина с номером k недостижима.

Алгоритм Кратчайший путь

цел: I,J,A,K,G[1:20;1:20],P[1:20];

Запросить A; (*запрашивается номер начальной вершины*)

Данные, используемые в любой информационной модели, всегда определенным образом упорядочены, структурированы. Иначе можно сказать так: данные, на которых базируется информационная модель, представляют собой систему со всеми характерными признаками – элементным составом, структурой, назначением. Такие структурированные системы данных часто называют структурами данных.

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

Вложение	Размер
struktura_dannyh_derevya_grafy_tablitsy.docx	558.39 КБ

Предварительный просмотр:

Конспект открытого урока информатики на тему:

Класс: 10 (общеобразовательный)

Учитель: Гериханов Шахман Хамзатович

Дата проведения: 12.02.2019 г.

Тип урока: комбинированный

Учебник: Информатика и ИКТ. Базовый уровень: учебник для 10-11 классов/И.Г.Семакин, Е.К.Хеннер

Тема: Структуры данных: деревья, сети, графы, таблицы.

Создать условия для развития умения выделять главное, сравнивать, анализировать, обобщать.

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

Оборудование: компьютер учителя с мультимедийным проектором.

1. Организационный момент (2 мин)

2. Проверка домашнего задания – фронтальный опрос (5 мин)

3. Объяснение нового материала. (20 мин)

4. Закрепление нового материала (10 мин)

5. Подведение итогов (2 мин)

6. Задание на дом (1 мин)

1. Сообщить учащимся тему урока.

2. Проверка домашнего задания – фронтальный опрос.

Ответьте на следующие вопросы:

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

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

(Записывают тему урока в тетрадь)

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

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

Очевидно, первый путь более выгодный, он короче. Однако, если по какой-то причине дорога между К и Б окажется непроезжей, то единственным остается второй путь. Граф на рисунке 1 еще называют сетью.

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

Граф изображенный на рис.1 является неориентированным графом. На нем каждое ребро обозначает наличие дорожной связи между двумя пунктами. Но дорожная связь действует одинаково в обе стороны. Такую связь еще называют с имметричной .

Рассмотрим другой пример графа рис.2

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

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

Итак, запишем словарь урока: (слайд 4)

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

Вершины графа – это компоненты системы изображаемые кружками, овалами, прямоугольниками и пр.

Дуги – это направленные линии (стрелки), связывающие компоненты между собой определенным образом.

Ребра – это ненаправленные линии, связывающие компоненты между собой определенным образом.

Петля – это ребро, соединяющее вершину с нею самой.

Вершины, которым не соответствует ни одно ребро, называются "изолированными".

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

Следующий тип структур – это иерархические структуры (деревья)

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

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

Запишем в словарь урока:

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

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

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

Еще одним примером иерархической структуры является система доменных адресов в Интернете.

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

Читайте также: