Презентация по информатике "Графы в нашей жизни"

• 1 слайд

  Учитель:
  Подповедная Светлана
  Александровна
  Графы в нашей жизни
  виды
  Вербальные
  математи-ческие
  графические
  табличные
  05.02.2017
  

• 2 слайд

  Цели:
  Образовательные: усвоение новых знаний, закрепление практических умений;
  Развивающие: развитие приемов умственной деятельности, логического и пространственного мышления, внимания, навыков коммуникативной работы в группах;
  Воспитательные: воспитание уважения к мнению другого, умение вести диалог, воспитание ответственности за свою работу в коллективе;
  
  
  
  
  
  19.06.2022
  

• 3 слайд

  Признаки информационной модели
  Состав
  Из каких элементов состоит?
  Структура
  Как элементы объединены?
  Назначение
  С какой целью создана?
  

• 4 слайд

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

• 5 слайд

  19.06.2022
  Граф
  это схема, которая наглядно отражает элементарный состав системы и структуру связей объектов системы.
  Описание местности
  Район состоит из 5 поселков: Дедкино, Бабкино, Репкино, Кошкино и Мышкино.
  Автомобильные дороги проложены между: Дедкино и Бабкино, Дедкино и Кошкино, Бабкино и Мышкино, Кошкино и Репкино.
  
  Вопрос
  Через какие поселки надо проехать, чтобы добраться из Репкино в Мышкино.
  Схема местности
  
  
  
  
  
  
  
  Ответ
  Р – К – Б – М;
  Р – К – Д – Б – М.
  Д
  Б
  М
  К
  Р
  

• 6 слайд

  Неориентированный граф
  граф, вершины которого соединены ребрами. С помощью таких графов могут быть представлены схемы двухсторонних (симметричных) отношений.
  По графу определите кто с кем переписывается:
  
  
  Маша
  Юра
  Аня
  Витя
  Коля
  19.06.2022
  

• 7 слайд

  19.06.2022
  Состав графа
  Граф состоит из вершин, связанных линиями.
  Направленная линия (со стрелкой) называется дугой.
  Линия ненаправленная (без стрелки) называется ребром.
  Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей.
  А
  В
  С
  петля
  ребро
  дуга
  

• 8 слайд

  Ориентированный граф
  граф, вершины которого соединены дугами. С помощью таких графов могут быть представлены схемы односторонних отношений.
  В чем отличие данного графа от предыдущего
  
  
  Маша
  Коля
  Юра
  Витя
  Аня
  19.06.2022
  

• 9 слайд

  Взвешенный граф
  граф, у которого вершины или рёбра (дуги) несут дополнительную информацию (вес).
  
  Маша
  10в
  Коля
  10в
  Юра
  10а
  Витя
  10б
  Аня
  10а
  3
  5
  1
  4
  2
  3
  19.06.2022
  

• 10 слайд

  Решение задач
  
  19.06.2022
  Между населенными пунктами A,B, C,D, Е построены дороги, протяженность которых указана в таблице. Определите длину кратчайшего пути между пунктами A и D
  
  
  Варианты ответов:
  9
  8
  12
  15
  
  
  

• 11 слайд

  Для решения задачи построим граф:
  Возможны 2 пути: 1) А – В – Д - Е; 2)А – Д - Е
  
  2
  
  3 4 4
  
  
  19.06.2022
  А
  В
  D
  E
  С
  1
  

• 12 слайд

  Вершина
  Ребро
  Описывают состав
  Описывают связи
  Из чего состоит граф?
  

• 13 слайд

  Сколько различных путей существует для проезда из P в М?
  Что такое сеть?
  СЕТЬ - граф, в котором существует несколько различных путей для перемещения по ребрам между парами вершин
  

• 14 слайд

  Замкнутый путь К – Д – Б – К называют циклом.
  Что такое цикл?
  

• 15 слайд

  19.06.2022
  Состав структуры «Дерево»
  Корень – главная вершина дерева.
  Предок – объект верхнего уровня.
  Потомок – объект нижнего уровня.
  Листья – вершины, не имеющие потомков.
  Чемпион
  Финалисты
  Участники ½ финала
  Участники ¼ финала
  Олимпийская система спортивных соревнований
  Первоначальные игроки
  

• 16 слайд

  Граф с иерархией - дерево
  Корень
  Ветви
  Листья
  РФ
  Центральный округ
  Рязанская область
  Рязань
  Михайлов
  …
  Владимирская область
  …
  Приволжский округ
  …
  Уральский округ
  ….
  Северо-Западный округ
  ….
  1
  2
  3
  4
  

• 17 слайд

  Иерархическая система хранения файлов
  Диск D:
  Фото
  2014
  2015
  Музыка
  Документы
  Текстовые
  Графические
  Презентации
  

• 18 слайд

  Иерархическая система хранения файлов
  Диск D:
  Фото
  2014
  2015
  Музыка
  Документы
  Текстовые
  Графические
  Презентации
  

• 19 слайд

  Иерархическая система хранения файлов
  Диск D:
  Фото
  2014
  2015
  Музыка
  Документы
  Текстовые
  Графические
  Презентации
  

• 20 слайд

  Иерархическая система доменных адресов в сети Интернет
  
  ru
  edu
  shkola1
  com
  google
  maps
  Домен верхнего уровня
  Домен 1 уровня
  Домен 2 уровня
  Домен 3 уровня
  

• 21 слайд

  Использование графов при решении задач
  по материалам ГИА (9класс)
  

• 22 слайд

  19.06.2022
  Задача 1
  Сколькими способами можно рассадить в ряд на три стула трех учеников? Выписать все возможные случаи.
  

• 23 слайд

  19.06.2022
  Решение
  Представим решение в виде графа:
  O
  A
  B
  C
  1 стул
  

• 24 слайд

  19.06.2022
  Решение
  Представим решение в виде графа:
  O
  A
  B
  C
  1 стул
  B
  A
  A
  B
  C
  C
  2 стул
  

• 25 слайд

  19.06.2022
  Решение
  Представим решение в виде графа:
  O
  A
  B
  C
  1 стул
  B
  A
  A
  B
  C
  C
  2 стул
  C
  C
  B
  B
  A
  A
  3 стул
  

• 26 слайд

  19.06.2022
  Решение
  Представим решение в виде графа:
  O
  A
  B
  C
  1 стул
  B
  A
  A
  B
  C
  C
  2 стул
  C
  C
  B
  B
  A
  A
  3 стул
  Выпишем все решения:
  A-B-C, A-C-B, B-A-C, B-C-A, C-A-B, C-B-A.
  

• 27 слайд

  19.06.2022
  Задача 2
  Сколько трехзначных чисел можно записать с помощью цифр 1, 3, 5 и 7 при условии, что в записи числа не должно быть одинаковых цифр?
  

• 28 слайд

  19.06.2022
  Решение
  3
  1
  5
  7
  3
  5
  3
  3
  5
  5
  7
  7
  7
  1
  1
  1
  1
  1
  1
  1
  1
  5
  5
  5
  5
  5
  5
  1
  7
  7
  7
  7
  7
  7
  3
  3
  3
  3
  3
  3
  1 цифра
  2 цифра
  3 цифра
  Ответ: 24 числа.
  

• 29 слайд

  19.06.2022
  Задача 3. Отыскание пути
  1
  2
  3
  4
  5
  6
  7
  8
  9
  На рисунке изображена схема местности. Передвигаться из пункта в пункт можно только в направлении стрелок. В каждом пункте можно бывать не более одного раза. Сколькими способами можно попасть из пункта 1 в пункт 9? У какого из путей наименьшая длина? У какого наибольшая длина?
  

• 30 слайд

  Решение задачи
  2
  3
  4
  5
  6
  7
  8
  9
  1
  1
  2
  5
  4
  8
  9
  6
  9
  5
  8
  9
  8
  9
  7
  9
  5
  8
  9
  8
  9
  7
  9
  5
  8
  9
  8
  9
  7
  1 ярус
  2 ярус
  3 ярус
  4 ярус
  5 ярус
  6 ярус
  7 ярус
  7
  5
  9
  5
  3
  5
  Кратчайший путь: 1 5 9. Его длинна 2.
  Длина наиболее продолжительного пути 7: 1 2 3 6 5 7 8 9.
  Число путей 14
  9
  8
  9
  9
  5
  8
  7