Тема : Использование информационных моделей (таблицы, диаграммы, графики) icon

Тема : Использование информационных моделей (таблицы, диаграммы, графики)



НазваниеТема : Использование информационных моделей (таблицы, диаграммы, графики)
страница1/6
Дата конвертации24.06.2012
Размер0.77 Mb.
ТипДокументы
  1   2   3   4   5   6

© К. Поляков, 2009-2012

A2 (базовый уровень, время – 2 мин)


Тема: Использование информационных моделей (таблицы, диаграммы, графики).
Перебор вариантов, выбор лучшего по какому-то признаку.

Что нужно знать:

  • в принципе, особых дополнительных знаний, кроме здравого смысла и умения перебирать варианты (не пропустив ни одного!) здесь, как правило, не требуется

  • полезно знать, что такое граф (это набор вершин и соединяющих их ребер) и как он описывается в виде таблицы, хотя, как правило, все необходимые объяснения даны в формулировке задания

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

  • рассмотрим граф (рисунок слева), в котором 5 вершин (A, B, C, D и E); он описывается таблицей, расположенной в центре; в ней, например, число 4 на пересечении строки В и столбца С означает, что, во-первых, есть ребро, соединяющее В и С, и во-вторых, вес этого ребра равен 4; пустая клетка на пересечении строки А и столбца В означает, что ребра из А в В нет

gif" align=left hspace=12>






A

B

C

D

Е

A







3

1




B







4




2

C

3

4







2

D

1













Е




2

2












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

  • в приведенном примере матрица симметрична относительно главной диагонали; это может означать, например, что стоимости перевозки из В в С и обратно равны (это не всегда так)

  • желательно научиться быстро (и правильно) строить граф по весовой матрице и наоборот
^

Пример задания:


Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)




A

B

C

D

E

F

A




2

4










B

2




1




7




C

4

1




3

4




D







3




3




E




7

4

3




2

F













2




^ Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

1) 9 2) 10 3) 11 4) 12

Решение (вариант 1, использование схемы):

  1. построим граф – схему, соответствующую этой весовой матрице; из вершины А можно проехать в вершины B и C (длины путей соответственно 2 и 4):



  1. для остальных вершин можно рассматривать только часть таблицы над главной диагональю, которая выделена серым цветом; все остальные рёбра уже были рассмотрены ранее

  2. например, из вершины В можно проехать в вершины C и E (длины путей соответственно 1 и 7):



  1. новые маршруты из С – в D и E (длины путей соответственно 3 и 4):



  1. новый маршрут из D – в E (длина пути 3):



  1. новый маршрут из E – в F (длина пути 2):



  1. нужно проехать из А в F, по схеме видим, что в любой из таких маршрутов входит ребро EF длиной 2; таким образом, остается найти оптимальный маршрут из A в E

  2. попробуем перечислить возможные маршруты из А в Е:

А – В – Е длина 9

А – В – С – Е длина 7

А – В – C – D – Е длина 9

А –C – Е длина 8

А –C – B – Е длина 12

А –C – D – Е длина 10

  1. из перечисленных маршрутов кратчайший – A-B-C-E – имеет длину 7, таким образов общая длина кратчайшего маршрута A-B-C-E-F равна 7 + 2 = 9

  2. таким образом, правильный ответ – 1.

Решение (вариант 2, с начала маршрута):

  1. составим граф, который показывает, куда (и как) можно ехать из пункта А, рядом с дугами будем записывать увеличение пути, а рядом с названиями пунктов – общую длину пути от пункта A:



  1. видно, что напрямую в пункт F из A не доехать

  2. строим граф возможных путей дальше: определяем, куда можно ехать из B и C (конечно, не возвращаясь обратно); из B можно ехать только в A (обратно), в C и в E;

  3. узел C уже есть на схеме, и оказывается, что короче ехать в него по маршруту A-B-C, чем напрямую A-C, длина «окольного» пути составляет 3 вместо 4 для «прямого»;
    при движении по дороге B-E длина увеличивается на 7:



  1. строим маршруты из пункта C; кроме A и B, из пункта C можно ехать в D (длина 3) и E (длина 4), причем кратчайший маршрут из A в E оказывается A-B-C-E (длина 7); «невыгодные» маршруты на схеме показывать не будем:



  1. из пункта D, кроме как в С и E, ехать некуда; путь D-C – это возврат назад (нас не интересует), путь D-E тоже не интересует, поскольку он дает длину 6 + 3 = 9, а мы уже нашли, что в E из A можно доехать по маршруту длины 7

  2. из пункта E можно ехать в F, длина полного маршрута 7 + 2 = 9



  1. Ответ: 1

Решение (вариант 3, с конца маршрута):

  1. можно точно так же начинать с пункта F и искать кратчайший маршрут до A; судя по таблице, из F можно ехать только в E:




  1. из E ведут дороги в B, C и D



  1. из B можно сразу попасть в A, длина пути будет равна 11:



  1. из пункта C есть прямая дорога в A длиной 4, таким образом, существует маршрут длиной
    6 + 4 = 10



  1. кроме того, есть дорога C-B, которая дает маршрут F-E-C-B-A длиной 9



  1. рассмотрение пути C-D не позволяет улучшить результат: оптимальный маршрут имеет длину 9

  2. Ответ: 1

Возможные ловушки и проблемы:

    • можно не заметить, что маршруты, проходящие через большее число пунктов, оказываются короче (A-B-C короче, чем A-C, A-B-C-E короче, чем A-B-E)
  1   2   3   4   5   6




Похожие:

Тема : Использование информационных моделей (таблицы, диаграммы, графики) iconТема : Использование информационных моделей (таблицы, диаграммы, графики)
В и столбца с означает, что, во-первых, есть ребро, соединяющее в и С, и во-вторых, вес этого ребра равен 4; пустая клетка на пересечении...
Тема : Использование информационных моделей (таблицы, диаграммы, графики) iconМинимальные требования к проектам по курсу «современные информационные технологии в науке и образовании»
Включение разных типов слайдов (многоабзацные тексты (списки), таблицы, диаграммы, организационные диаграммы, изображения из ms clip...
Тема : Использование информационных моделей (таблицы, диаграммы, графики) iconИспользование информационных технологий как средство повышения эффективности подготовки учащихся к егэ по математике
Использование современных информационных технологий в образовании – это уже не новшество, а реальность сегодняшнего дня для всего...
Тема : Использование информационных моделей (таблицы, диаграммы, графики) iconИспользование компьютерных информационных технологий в начальной школе. План выступления. Использование икт в учебном процессе. Иип «км-школа»
В письме Министерства образования России от 13. 08. 2002 г. №01- 51-088 ин предлагается «осуществить организацию образовательного...
Тема : Использование информационных моделей (таблицы, диаграммы, графики) iconУрок №1 Тема урока: Знакомство с электронными таблицами excel. Введение основных понятий и правил работы
Цель урока: Ввести основные понятия excel, показать правила создания простейшей таблицы, объяснить суть и назначение электронных...
Тема : Использование информационных моделей (таблицы, диаграммы, графики) iconБелорусский государственный университет выпускная работа по «Основам информационных технологий» Использование информационных технологий в преподавании русского языка как иностранного
Использование информационных технологий в преподавании русского языка как иностранного
Тема : Использование информационных моделей (таблицы, диаграммы, графики) iconПлан мероприятий гимназии №88 по реализации темы «Использование информационных технологий на уроках физики в гуманитарной школе». 2008-2009 учебный год
«Использование информационных технологий на уроках физики в гуманитарной школе»
Тема : Использование информационных моделей (таблицы, диаграммы, графики) iconСоставьте круговую диаграмму, в которой будут отображаться данные таблицы
Придумайте и напечатайте название этой диаграмме (название должно быть в поле диаграммы)
Тема : Использование информационных моделей (таблицы, диаграммы, графики) iconИз опыта работы Савинкиной М. В. Проблема, над которой я работаю в течение последних 5 лет – «Использование информационных технологий в обучении истории»
Проблема, над которой я работаю в течение последних 5 лет – «Использование информационных технологий в обучении истории». В моем...
Тема : Использование информационных моделей (таблицы, диаграммы, графики) iconМетодические рекомендации по использованию новых информационных технологий на уроках английского языка
Для достижения всех перечисленных целей, безусловно, эффективную помощь учителю оказывает использование новых информационных технологий...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов