Добавить материал и получить бесплатное свидетельство о публикации в СМИ
Эл. №ФС77-60625 от 20.01.2015

Автоматическая выдача свидетельства о публикации в официальном СМИ сразу после добавления материала на сайт - Бесплатно

Добавить свой материал

За каждый опубликованный материал Вы получите бесплатное свидетельство о публикации от проекта «Инфоурок»

(Свидетельство о регистрации СМИ: Эл №ФС77-60625 от 20.01.2015)

Инфоурок / Информатика / Конспекты / План урока по информатике "Введение в теорию графов" (11 класс)
ВНИМАНИЮ ВСЕХ УЧИТЕЛЕЙ: согласно Федеральному закону № 313-ФЗ все педагоги должны пройти обучение навыкам оказания первой помощи.

Дистанционный курс "Оказание первой помощи детям и взрослым" от проекта "Инфоурок" даёт Вам возможность привести свои знания в соответствие с требованиями закона и получить удостоверение о повышении квалификации установленного образца (180 часов). Начало обучения новой группы: 26 апреля.

Подать заявку на курс
  • Информатика

План урока по информатике "Введение в теорию графов" (11 класс)

Выбранный для просмотра документ #U041f#U043e#U0434#U0433#U043e#U0442#U043e#U0432#U043a#U0430_#U043a_#U0415#U0413#U042d_2015_(#U0438#U0437#U0431#U0440#U0430#U043d#U043d#U044b#U0435 #U0437#U0430#U0434#U0430#U0447#U0438)1.ppt

библиотека
материалов
Избранные задания к ЕГЭ по информатике 2015 года Книга книгой, а мозгами двиг...
5. Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённ...
A
A B 5 D G 12 25
A B 5 D 8 D G 12 25
A B 5 2 C D 8 D G 12 25
A B E F G 5 2 C 10 5 4 D 8 D G 12 25
A B E F G 5 2 C 10 5 4 D 8 G D G 12 5 25
A B E F G 5 2 C 10 5 4 D 8 G 24 D G 12 5 25
A B E F G 5 2 C 10 5 4 G 5 D 8 G 24 D G 12 5 25
A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 D G 12 5 25
A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D G 12 5 25
A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C G 12 8 2 5 25
A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C G 12 8 2 5 25
A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C E F G 10 5 4 G 12 8 2 5 25
A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C E F G 10 5 4 G 23 G 12 8 2 5...
A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C E F G 10 5 4 G 5 24 G 23 G 12...
A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C E F G 10 5 4 G 5 24 G 23 24 G...
A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C E F G 10 5 4 G 5 24 G 23 24 G...
A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C E F G 10 5 4 G 5 24 G 23 24 G...
Для решения задачи мы применили поиск решения путем построения всех возможных...
15. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К,...
Для нашего графа можно записать: П(А)=1 – из пункта в пункт А можно попасть е...
П(А)=1 П(Б)=П(А) П(Г)=П(А) П(В)=П(А)+П(Б)+П(Г) П(Д)=П(Б)+П(В) П(Е)=П(Г) П(Ж)=...
24 1

"Инфоурок" приглашает всех педагогов и детей к участию в самой массовой интернет-олимпиаде «Весна 2017» с рекордно низкой оплатой за одного ученика - всего 45 рублей

В олимпиадах "Инфоурок" лучшие условия для учителей и учеников:

1. невероятно низкий размер орг.взноса — всего 58 рублей, из которых 13 рублей остаётся учителю на компенсацию расходов;
2. подходящие по сложности для большинства учеников задания;
3. призовой фонд 1.000.000 рублей для самых активных учителей;
4. официальные наградные документы для учителей бесплатно(от организатора - ООО "Инфоурок" - имеющего образовательную лицензию и свидетельство СМИ) - при участии от 10 учеников
5. бесплатный доступ ко всем видеоурокам проекта "Инфоурок";
6. легко подать заявку, не нужно отправлять ответы в бумажном виде;
7. родителям всех учеников - благодарственные письма от «Инфоурок».
и многое другое...

Подайте заявку сейчас - https://infourok.ru/konkurs

Описание презентации по отдельным слайдам:

№ слайда 1 Избранные задания к ЕГЭ по информатике 2015 года Книга книгой, а мозгами двиг
Описание слайда:

Избранные задания к ЕГЭ по информатике 2015 года Книга книгой, а мозгами двигай! Графы, деревья

№ слайда 2 5. Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённ
Описание слайда:

5. Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.) Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам). Б A B C D E F G A 5 12 25 B 5 8 C 2 4 5 10 D 12 8 2 E 4 5 F 5 5 G 25 10 5 5

№ слайда 3 A
Описание слайда:

A

№ слайда 4 A B 5 D G 12 25
Описание слайда:

A B 5 D G 12 25

№ слайда 5 A B 5 D 8 D G 12 25
Описание слайда:

A B 5 D 8 D G 12 25

№ слайда 6 A B 5 2 C D 8 D G 12 25
Описание слайда:

A B 5 2 C D 8 D G 12 25

№ слайда 7 A B E F G 5 2 C 10 5 4 D 8 D G 12 25
Описание слайда:

A B E F G 5 2 C 10 5 4 D 8 D G 12 25

№ слайда 8 A B E F G 5 2 C 10 5 4 D 8 G D G 12 5 25
Описание слайда:

A B E F G 5 2 C 10 5 4 D 8 G D G 12 5 25

№ слайда 9 A B E F G 5 2 C 10 5 4 D 8 G 24 D G 12 5 25
Описание слайда:

A B E F G 5 2 C 10 5 4 D 8 G 24 D G 12 5 25

№ слайда 10 A B E F G 5 2 C 10 5 4 G 5 D 8 G 24 D G 12 5 25
Описание слайда:

A B E F G 5 2 C 10 5 4 G 5 D 8 G 24 D G 12 5 25

№ слайда 11 A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 D G 12 5 25
Описание слайда:

A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 D G 12 5 25

№ слайда 12 A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D G 12 5 25
Описание слайда:

A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D G 12 5 25

№ слайда 13 A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C G 12 8 2 5 25
Описание слайда:

A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C G 12 8 2 5 25

№ слайда 14 A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C G 12 8 2 5 25
Описание слайда:

A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C G 12 8 2 5 25

№ слайда 15 A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C E F G 10 5 4 G 12 8 2 5 25
Описание слайда:

A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C E F G 10 5 4 G 12 8 2 5 25

№ слайда 16 A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C E F G 10 5 4 G 23 G 12 8 2 5
Описание слайда:

A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C E F G 10 5 4 G 23 G 12 8 2 5 5 25

№ слайда 17 A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C E F G 10 5 4 G 5 24 G 23 G 12
Описание слайда:

A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C E F G 10 5 4 G 5 24 G 23 G 12 8 2 5 5 25

№ слайда 18 A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C E F G 10 5 4 G 5 24 G 23 24 G
Описание слайда:

A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C E F G 10 5 4 G 5 24 G 23 24 G 12 8 2 5 5 25

№ слайда 19 A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C E F G 10 5 4 G 5 24 G 23 24 G
Описание слайда:

A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C E F G 10 5 4 G 5 24 G 23 24 G 12 8 2 5 5 25 25

№ слайда 20 A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C E F G 10 5 4 G 5 24 G 23 24 G
Описание слайда:

A B E F G 5 2 C 10 5 4 G 5 25 D 8 G 24 25 D B C E F G 10 5 4 G 5 24 G 23 24 G 25 12 8 2 5 5 25

№ слайда 21 Для решения задачи мы применили поиск решения путем построения всех возможных
Описание слайда:

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

№ слайда 22 15. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К,
Описание слайда:

15. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л? П

№ слайда 23 Для нашего графа можно записать: П(А)=1 – из пункта в пункт А можно попасть е
Описание слайда:

Для нашего графа можно записать: П(А)=1 – из пункта в пункт А можно попасть единственным путем – оставаться на своем месте. П(Б)=П(А) П(В)=П(А)+П(Б)+П(Г) П(Г)=П(А) П(Д)=П(Б)+П(В) П(Е)=П(Г) П(Ж)=П(В)+П(Е) П(И)=П(Д) П(К)=П(Е) П(Л)=П(И)+П(Д)+П(Ж)+П(К)

№ слайда 24 П(А)=1 П(Б)=П(А) П(Г)=П(А) П(В)=П(А)+П(Б)+П(Г) П(Д)=П(Б)+П(В) П(Е)=П(Г) П(Ж)=
Описание слайда:

П(А)=1 П(Б)=П(А) П(Г)=П(А) П(В)=П(А)+П(Б)+П(Г) П(Д)=П(Б)+П(В) П(Е)=П(Г) П(Ж)=П(В)+П(Е) П(И)=П(Д) П(К)=П(Е) П(Л)=П(И)+П(Д)+П(Ж)+П(К) Выбирая подходящий порядок вычислений получим П(А)=1 П(Б)=П(А)=1 П(Г)=П(А)=1 П(В)=П(А)+П(Б)+П(Г)=1+1+1=3 П(Д)=П(Б)+П(В)=1+3=4 П(Е)=П(Г)=1 П(Ж)=П(В)+П(Е)=3+1=4 П(И)=П(Д)=4 П(К)=П(Е)=1 П(Л)=П(И)+П(Д)+П(Ж)+П(К)=4+4+4+1=13

Выбранный для просмотра документ #U0423#U0440#U043e#U043a #U0412#U0432#U0435#U0434#U0435#U043d#U0438#U0435 #U0432 #U0442#U0435#U043e#U0440#U0438#U044e #U0433#U0440#U0430#U0444#U043e#U0432 11 #U043a#U043b#U0430#U0441#U0441.docx

библиотека
материалов

hello_html_m68fa5f81.gifhello_html_m2d3aeb09.gifhello_html_24ffa806.gifhello_html_m2f1272ec.gifПЛАН-КОНСПЕКТ УРОКА

«Введение в теорию графов»


ФИО Гайдыш Лариса Васильевна

Место работы МБОУ «Ардатовская средняя общеобразовательная

школа № 2 им. С. И. Образумова»

Должность учитель информатики и ИКТ

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

Класс 11 (профильный уровень)

Тема: Графы и их исследование с использованием языка объектно-ориентированного программирования Visual Basic

(Учебник для 11 класса профильного уровня, Н. Угринович)

Цель: введение понятий теории графов, приобретение навыков представления графа в форму матрицы смежности, преобразования весовой матрицы в граф, умений строить граф, умений преобразовывать граф в остовное связное дерево минимального веса, умений решать задачи на графы демо-версий ЕГЭ

Обучающие задачи:

  • Сформировать у учащихся основные понятия теории графов, познакомить с видами графов, сформировать навыки построения графов;

  • Научить описывать граф с помощью матрицы смежности;

  • Научить преобразовывать граф в остовное связное дерево минимального веса;

  • Научить применять теорию графов для решения задач демо-версий ЕГЭ;

Развивающие задачи:

  • Развивать логическое мышление, т.е. умение анализировать, сравнивать, обобщать;

  • Развивать познавательные умения: выделять главное, планировать работу, вести поисковую деятельность;

  • Критически оценивать результаты своего труда, регулировать и контролировать свои действия при работе на компьютере;

  • Развивать умения учебного труда - работать в хорошем темпе;

  • Развивать волю и самостоятельность, инициативу, уверенность в своих силах, умения преодолевать трудности, действовать самостоятельно.

Воспитательные задачи:

  • Воспитывать добросовестное отношение к труду и к результатам своей деятельности;

  • Воспитывать дисциплинированность и организованность;

  • Воспитывать эстетическое отношение к выполняемой работе;

  • Воспитывать мотивы учения.

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

Формы работы учащихся фронтальная, индивидуальная

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

План урока с хронометражем:

п\п

Этапы работы на уроке

Время этапа

1

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

2 мин

2

Целеполагание и мотивация

1 мин

3

Актуализация

3 мин

4

Первичное усвоение материала

13 мин

5

Осознание и осмысление учебной информации

3 мин

6

Первичное закрепление учебного материала

10 мин

7

Самостоятельная работа

11 мин

8

Информация о домашнем задании

2 мин

9

Рефлексия (подведение итогов урока)

2 мин


п/п

Этап урока

Название используемых ЭОР

(с указанием порядкового номера из Таблицы 2)

Деятельность учителя

(с указанием действий с ЭОР, например, демонстрация)

Деятельность ученика

Время

(в мин.)


1

2

3

4

5

6

1

Орг. момент, приветствие


Приветствует учащихся, отмечает отсутствующих. Сообщает учащимся тему урока, отмечает отсутствующих на уроке.

Приветствуют учителя, садятся. Настраиваются на урок, воспринимают информацию. Записывают число и тему урока.


2

2

Целеполагание и мотивация


Формулирует цели урока:
«Сегодня мы познакомимся с основными понятиями теории графов, научимся строить граф, описывать его с помощью матрицы смежности, преобразовывать граф в остовное связное дерево минимального веса, применять полученные на уроке знания для решения задач демо-версий ЕГЭ».

Учащиеся знакомятся с целью урока

1

3

Актуализация


Учитель определяет проблему.

Решите задачу. Между ребятами существуют следующие отношения: дружат Андрей и Даша, Андрей и Маша, Даша и Коля, Коля и Андрей. С кем Андрей может поделиться секретом, не рискуя, что он станет известен кому – либо?


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

Учащиеся вместе с учителем определяют проблему и пытаются ее решить

3

4

Первичное усвоение материала


Самостоятельная работа с книгой.

Учитель предлагает вопросы учащимся (на слайде презентации), на которые им нужно ответить, прочитав материал учебника «Введение в теорию графов» (стр 112-116):

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

Назовите виды графов.

Какой граф называют ориентированным?

Какой граф называют неориентированным?

Какой граф называют взвешенным?

Что такое вес сети?

Что такое матрица смежности?

Какие особенности есть у матрицы смежности?

Что называется подграфом графа? Остовным связным подграфом?

Что такое дерево? Остовное связное дерево

hello_html_30cc278a.gifУчитель объясняет преобразование графа в остовное связное дерево минимального веса с помощью алгоритма Крускала. Рассматривается пример построения остовного связного дерева минимального веса в учебнике стр 118-119.

Учащиеся находят ответы в учебнике и представляют их.












































Учащиеся слушают учителя, находят алгоритм в учебнике стр 117-118, делают записи в тетради.

13

5

Осознание и осмысление учебной информации


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

А



М



К


Д



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


Ребята работают в тетрадях, строят граф и дают ответ задачи

3

6

Первичное закрепление учебного материала

Ресурс № 2. Подготовка_к_ЕГЭ_2015_(избран-ные задачи)1. Баханский А. Г.

В демо-версии ЕГЭ 2015 г включены задачи, которые можно решить, применяя теорию графов, это задания № 5, 15, 22. Рассмотрим их решения, используя Презентацию.

hello_html_2aed086e.gif

hello_html_23bdc795.gif

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

11

7

Самостоятельная работа















Ресурс № 1 «Основы теории графов. Способы представления графов. Обход графов». Барская М. И., Лещев А.

1) Решите задачу

hello_html_4784a893.png



2)Изучение дополнительного материала.

Тем, кто раньше всех справился с задачей, предлагается самостоятельная работа с ЭОР.

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

Первый учащийся, решивший задачу, представляет её решение на доске.


Ребята знакомятся с дополни-тельным материалом, задают вопросы учителю, если они возникли. Пересказ представят для ответа на следующий урок.


8

Информация о домашнем задании


П 1.10.1 читать, учить понятия, алгоритм Крускала, устно отвечать на вопросы стр 119.

Демо-версия ЕГЭ 2014 г А2, В9, В13.

Учащиеся записывают домашнее задание в дневники

2

9

Рефлексия (подведение итогов урока)


Учитель просит высказать свое мнение о прошедшем уроке, ответив на вопросы:

Какие этапы урока для вас оказались наиболее сложными?
Какие этапы урока оказались наиболее интересными?
Что из данного урока запомнилось лучше?
Во всех ли тонкостях данной темы удалось разобраться?
Остались ли пробелы или можно утверждать, что тема полностью исчерпана?
Оцените свою работу по 10 бальной шкале.

Выставляет отметки за работу на уроке.

Обучающиеся отвечают на вопросы рефлексии. Получают отметки в дневник.

2

Приложение к плану-конспекту урока

«Введение в теорию графов»

ПЕРЕЧЕНЬ ИСПОЛЬЗУЕМЫХ НА ДАННОМ УРОКЕ ЭОР

Название ресурса

Тип, вид ресурса

Форма предъявления информации (иллюстрация, презентация, видеофрагменты, тест, модель и т.д.)

Гиперссылка на ресурс, обеспечивающий доступ к ЭОР

1

Основы теории графов. Способы представления графов. Обход графов». Барская М. И., Лещев А.

Текст/Текст с иллюстрациями. Иллюстация.

Текст «Способы представления графов»

http://85.142.23.53/packages/1C/30386185-809E-43EA-9F47-B314D5DCC251/1.0.0.2/unpacked/content/index.html

2

Подготовка_к_ЕГЭ_2015_ (избранные задачи)1. Баханский А.Г.

Мультимедиа

Презентация

Подготовка_к_ЕГЭ_2015_(избран-ные задачи)1. Баханский А. Г.




Автор
Дата добавления 08.10.2015
Раздел Информатика
Подраздел Конспекты
Просмотров762
Номер материала ДВ-041479
Получить свидетельство о публикации

"Инфоурок" приглашает всех педагогов и детей к участию в самой массовой интернет-олимпиаде «Весна 2017» с рекордно низкой оплатой за одного ученика - всего 45 рублей

В олимпиадах "Инфоурок" лучшие условия для учителей и учеников:

1. невероятно низкий размер орг.взноса — всего 58 рублей, из которых 13 рублей остаётся учителю на компенсацию расходов;
2. подходящие по сложности для большинства учеников задания;
3. призовой фонд 1.000.000 рублей для самых активных учителей;
4. официальные наградные документы для учителей бесплатно(от организатора - ООО "Инфоурок" - имеющего образовательную лицензию и свидетельство СМИ) - при участии от 10 учеников
5. бесплатный доступ ко всем видеоурокам проекта "Инфоурок";
6. легко подать заявку, не нужно отправлять ответы в бумажном виде;
7. родителям всех учеников - благодарственные письма от «Инфоурок».
и многое другое...

Подайте заявку сейчас - https://infourok.ru/konkurs


Выберите специальность, которую Вы хотите получить:

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

ПЕРЕЙТИ В КАТАЛОГ КУРСОВ


Идёт приём заявок на международный конкурс по математике "Весенний марафон" для учеников 1-11 классов и дошкольников

Уникальность конкурса в преимуществах для учителей и учеников:

1. Задания подходят для учеников с любым уровнем знаний;
2. Бесплатные наградные документы для учителей;
3. Невероятно низкий орг.взнос - всего 38 рублей;
4. Публикация рейтинга классов по итогам конкурса;
и многое другое...

Подайте заявку сейчас - https://urokimatematiki.ru

Похожие материалы

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