Моделирование: Графы и таблицы в задачах (ЕГЭ)

Слайд 1

Слайд 2

1.Вступление: что такое граф и таблица 2.Основная часть: Решение некоторых задач Построение графа по таблице или построение таблицы по графу (3) Построения графа при работе с БД (4) Граф и коды (5) Электронные таблицы (7) Поиск кратчайшего пути в ориентированном графе (15) Граф или таблица (22) 3.Вывод (о применении графов и таблиц в жизни, когда что лучше).

Слайд 3

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

Слайд 4

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

Слайд 5

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

Слайд 6

Таблица (из лат. tabula — доска) — способ структурирования данных. Представляет собой распределение данных по однотипным строкам и столбцам. Электронные таблицы - это работающее в диалоговом режиме приложение, хранящее и обрабатывающее данные в прямоугольных таблицах. Столбцы, строки, ячейки. Электронная таблица состоит из столбцов и строк. Заголовки столбцов обозначаются буквами или сочетаниями букв (А, С, АВ и т. п.), заголовки строк - числами (1, 2, 3 и далее).

Слайд 7

Задача о кратчайшем пути́ — задача поиска самого короткого пути(цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов ребер, составляющих путь. Значимость данной задачи определяется её различными практическими применениями. Например в GPS-навигаторах, где осуществляется поиск кратчайшего пути между двумя перекрестками. В качестве вершин выступают перекрестки, а дороги являются ребрами, которые лежат между ними. Сумма расстояний всех дорог между перекрестками должна быть минимальной, тогда найден самый короткий путь.

Слайд 8

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

Слайд 9

A B C D A 0 1 10 - B 1 0 2 10 C 10 2 0 3 D - 10 3 0 Матрица смежности Sm - это квадратная матрица размером N x N (N - количество вершин в графе)

Слайд 10

ГРАФЫ V S ТАБЛИЦА Графы представляют собой наглядные примеры математических моделей, описывающие различные реальные ситуации. Иллюстрируют, что математика постоянно присутствует в окружающем мире. Изучение теории графов стимулирует индуктивное, комбинаторное и пространственное мышление (различные схемы, деревья, сети (семантическая сеть) и т.д.). Помогают решать занимательные и прикладные задачи. Что лучше, как вы думаете при решении задач? Таблицы представляют собой наглядные примеры математических моделей, описывающие различные реальные ситуации. Позволяет систематизировать информацию Таблицы стимулирует индуктивное, дедуктивное, абстрактное мышление (базы данных, сравнительные таблицы и т.д.). Помогают решать занимательные и прикладные задачи.

Слайд 12

. На рисунке справа схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о длинах этих дорог (в километрах). Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта А в пункт Д. В ответе запишите целое число – так, как оно указано в таблице. П1 П2 П3 П4 П5 П6 П7 П1 30 25 18 П2 17 12 П3 30 17 23 34 15 П4 12 23 46 П5 25 37 П6 34 46 18 П7 18 15 37 18 А Б В Г Д Е К

Слайд 13

Решение: Определим степени вершин по весовой матрице и по изображению графа (как в предыдущей задаче): По изображению графа находим, что обе интересующих нас вершины, А и Д, имеют степени 3; кроме того, степень 3 имеет еще и вершина Г В таблице тоже есть три вершины со степенью 3 (это П1, П4 и П6), но вершина П1 (это вершина Г на рисунке!) не имеет общих ребёр с вершинами П4 и П6 (а это А и Д!); Таким образом, ответ – это длина ребра между вершинами П4 и П6 (эти ячейки выделены в весовой матрице фиолетовым фоном). Ответ: 46. П1 П2 П3 П4 П5 П6 П7 П1 30 25 18 3 П2 17 12 2 П3 30 17 23 34 15 5 П4 12 23 46 3 П5 25 37 2 П6 34 46 18 3 П7 18 15 37 18 4 А Б В Г Д Е К 3 3 3

Слайд 14

В фрагменте базы данных представлены сведения о родственных отношениях. На основании приведённых данных определите, сколько прямых потомков (т.е. детей и внуков) Павленко А.К. упомянуты в таблице 1. Таблица 1 ID Фамилии_И.О. Пол 2146 Кривич Л.П. Ж 2155 Павленко А.К. М 2431 Хитрук П.А. М 2480 Кривич А.А. М 2302 Павленко Е.А. Ж 2500 Сокол Н.А. Ж 3002 Павленко И.А. М 2523 Павленко Т.Х. Ж 2529 Хитрук А.П М 2570 Павленко П.И. М 2586 Павленко Т.И. Ж 2933 Симонян А.А. Ж 2511 Сокол В.А. Ж 3193 Биба С.А. Ж Таблица 2 ID _Родителя ID _Ребенка 2146 2302 2146 3002 2155 2302 2155 3002 2302 2431 2302 2511 2302 3193 3002 2586 3002 2570 2523 2586 2523 2570 2529 2431 2529 2511

Слайд 15

Решение: Сначала находим в таблице 1 Павленко А.К. ( Id = 2155) Теперь по таблице 2 ищем его детей – их идентификаторы 2302 и 3002; можно строить генеалогическое дерево: Далее так же определяем внуков 2155, то есть, детей 2302 и 3002: Как следует из таблицы, данных о правнуках 2155 в таблице нет Всего прямых потомков 7 – двое детей и 5 внуков. Ответ: 7. 2155 2302 3002 2155 2302 3002 2586 2570 2431 2511 3193

Слайд 16

По каналу связи передаются сообщения, содержащие только 4 буквы П, О, С, Т; для передачи используется двоичный код, допускающий однозначное декодирование. Для букв Т, О, П используются такие кодовые слова: Т: 111, О: 0, П: 100. Укажите кратчайшее кодовое слово для буквы С, при котором код будет допускать однозначное декодирование. Если таких кодов несколько, укажите код с наименьшим числовым значением.

Слайд 17

Решение: условие Фано означает, что ни одно кодовое слово не совпадает с началом другого кодового слова; при этом в дереве кода все кодовые слова должны располагаться в листьях дерева, то есть в узлах, которые не имеют потомков; построим дерево для заданных кодовых слов О – 0, Т – 111 и П – 100: штриховыми линиями отмечены две «пустые» ветви, на которые можно «прикрепить» лист для кодового слова буквы С: 101 или 110; из них минимальное значение имеет код 101 таким образом, выбрав кодовые слова А – 0, Б – 110, В – 10, Г – 111, получаем суммарную длину кодовых слов 9 символов Ответ: 101 . О 1 0 1 0 0 0 1 П Т О 1 0 1 0 0 0 П 1 С Т

Слайд 18

Коле нужно с помощью электронных таблиц построить таблицу квадратов двузначных чисел от 20 до 59. Для этого сначала в диапазоне В1:К1 он записал числа от 0 до 9, и в диапазоне А2:А5 он записал числа от 2 до 5. Затем в ячейку В5 записал формулу квадрата двузначного числа (А5 – число десятков; В1 – число единиц), после чего скопировал её во все ячейки диапазона B2:К5. В итоге получил таблицу квадратов двузначных чисел. На рисунке ниже представлен фрагмент этой таблицы. Какая формула была записана в ячейку В5? 1) = (B1+10* А5)^2 2) = ( $ B1+10* $ А5)^2 3) = (B $ 1+10* $ А5)^2 4) = ( $ B1+10* А$5)^2 А В С D Е 1 0 1 2 3 2 2 400 441 484 529 3 3 900 961 1024 1089 4 4 1600 1681 1764 1849 5 5 2500 2601 2704 2809

Слайд 19

Решение: посмотрим, куда ссылаются правильные формулы в B5 и в какой-нибудь другой ячейке, которая отличается от B5 и строкой, и столбцом, например, в D 3: смотрим, что в этих формулах меняется, а что не меняется; видим, что в первой ссылке не меняется строка 1, а во второй – столбец А, их и нужно сделать абсолютными, заблокировать с помощью знака $ поэтому в B5 нужно ввести формулу =(B$1+10*$ A 5)^2 Ответ: 3. А В С D Е 1 0 1 2 3 2 2 3 3 = (D1+10*A3)^2 4 4 5 5 = (B1+10* A5 )^ 2

Слайд 20

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

Слайд 21

На рисунке изображена схема дорог, связывающих города А, Б, В, Г, Д, Е, К, Л, М, Н, П, Р, Т. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Т? А Б Д Е Л Н П Р Т В Г М К 1 1 2 2 7 8 8 16 32 32 64 96 Ответ: 96

Слайд 22

Исполнитель Июнь15 преобразует число на экране. У исполнителя есть две команды, которым присвоены номера: 1. Прибавить 1 2. Умножить на 2 Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Июнь15 – это последовательность команд. Сколько существует программ, для которых при исходном числе 1 результатом является число 21 и при этом траектория вычислений содержит число 10? Траектория вычислений программы – это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.

Слайд 23

В этом случае не целесообразно решать задачу графом, так как количество решений может быть большое и граф будет очень большим. 1 +1 *2 +1 *2 +1 *2 2 2 3 4 3 4 +1 *2 +1 *2 4 6 5 8

Слайд 24

Решение: заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться) для начального числа 1 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через обозначить количество разных программ для получения числа N из начального числа 1, то . Теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую с предыдущими элементами последовательности , то есть с решениями таких же задач для меньших N Число N могло быть получено одной из двух операций: - увеличением на 1 числа N-1; - умножением на 2 числа N/2 (только для N, которые делятся на 2); - для нечётных чисел - для чётных чисел

Слайд 25

Поскольку траектория должна проходить через число 10, сначала выясняем, сколькими способами можно получить 10 из 1, а затем будем считать, сколько есть способов получить 21 из 10 Заполняем таблицу от 1 до 10 по полученным формулам: Второй этап – определяем таким же образом (и по таким же формулам!), сколько есть способов получить конечное число 21 из 10, только левую часть таблицы (от 1 до 10) мы уже не рассматриваем: Ответ: 28. N 1 2 3 4 5 6 7 8 9 10 1 2 2 4 4 6 6 10 1 0 14 N 10 11 12 13 14 15 16 17 18 19 20 21 14 14 14 14 14 14 14 14 14 14 28 28

Слайд 26

Как вы увидели, графы и таблицы одинаково важны при решении задач. Иногда лучше использовать граф, а иногда таблицу! И таблицы и графы, как вы наверняка знаете, очень важные способы моделирования при решении не только школьных задач, но и в обычной повседневной жизни! Часто графы и таблицы – модели взаимозвязанные ! Заметки: С помощью таблиц решаются задачи на истинность и ложность высказываний – таблицы истинности Логические уравнения и системы можно решить с помощью графа Источники: Сайты «Решу ЕГЭ», Константина Полякова и др.