Деревья Традиционная математическая символика является формальным языком математики. В отличие от естественных языков, формальные языки не носят национального. - презентация

1 деревья

2 Традиционная математическая символика является формальным языком математики. В отличие от естественных языков, формальные языки не носят национального характера. Они придуманы для профессиональной деятельности людей и понятны специалистам всего мира. Смысл математического выражения заключается в определяемой им последовательности вычислительных операций. Чтобы его понять, нужно знать правила старшинства операций, правила раскрытия скобок. Например, в выражении 7-5*3 в первую очередь следует выполнить действие, записанное вторым, что может показаться противоестественным. Если этого правила не знаешь, то ошибешься в вычислениях. Наглядным средством изображения последовательности вычисления математических выражений, т.е. их смысла, являются графы. Такой граф представляет собой дерево, листьями которого являются числа, а прочими вершинами – операции. Дуги связывают вершину-операцию с вершинами-операндами.

3 Например для формулы 5 * (3+7) * (8-2) дерево будет иметь такой вид: Последовательность выполнения операции определяется при прохождении дерева от листьев к корню (снизу-вверх). Последней выполняется операция, отмеченная в корне. * *

4 Задачи 1. Постройте деревья для следующих арифметических выражений: 1) 7 – 3 * / 4; 2) 6 * * (9 – 1); 3) (2 + 8) * (4 + 6) * 7. 2.Запишите арифметические выражения, соответствующие следующим деревьям: 1) 2) / * /

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

6 Граф игры Пусть на столе лежит 5 спичек. Двое игроков по очереди берут 1 или 2 спички. Выигрывает тот, кто забирает последнюю. Нарисуем граф всевозможных продолжений игры. Видно, что после первого хода на столе остается 3 или 4 спички. Если тот, кто начинает, оставит на столе 3 спички, то он выиграет: ведь его партнер вынужден будет оставить 1 или 2 спички, которые начинавший и заберет на следующем ходу. Если же начинающий оставит 4 спички, то он проиграет, так как партнер, взяв 1 спичку, оставит ему 3, что, как мы уже видели, ведет к проигрышу игрока, делающего очередной ход. Конечно же, второй игрок может оставить 2 спички и тут же проиграть, но надеяться на это не приходится. Можно сделать вывод: начинающий проигрывает, если исходное число спичек делится на 3, и выигрывает в остальных случаях, оставляя партнеру всякий раз количество спичек, которое делится на

7 Железные дороги Предполагается проложить железную дорогу, которая соединит несколько крупных городов. Для любой пары городов известна стоимость прокладки пути между ними. Требуется найти наиболее дешевый вариант строительства. Интересно, что алгоритм нахождения оптимального варианта строительства довольно прост (чего нельзя сказать о других задачах теории графов). Продемонстрируем его на примере дороги, соединяющей пять городов: A, B, C, D и E. Стоимость прокладки пути между каждой парой городов указана в таблице. АВСDE A1,5122,5 B1,51,230,8 C11,21,10,9 D231,12,7 E2,50,80,92,7

8 Сначала строим ту дорогу, которая имеет наименьшую стоимость. В нашем случае это маршрут В – Е. теперь найдем самую дешевую линию, соединяющую город В или Е с каким то из остальных городов. Это путь между Е и С. Включаем его в схему. Далее поступаем аналогично – ищем самый дешевый из путей, соединяющих один из городов В, С, Е с одним из оставшихся – А или D. Дешевле всего соединить его с С. Получим сеть, изображенную на рисунке. Описанный алгоритм относится к категории «жадных»: на каждом шаге мы выбираем самое дешевое продолжение пути. С E А В С D

9 Географическая экспедиция В состав экспедиции кроме начальника должны войти три географа, повар, радист, врач и техник. Участвовать в экспедиции изъявили желание десять человек, причем каждый владеет одной или несколькими из этих профессий. Всегда ли начальник экспедиции сможет из такой группы набрать нужных ему специалистов? 1- географ, 2 – географ, 3- географ и врач, 4-радист, повар и техник, 5-радист и техник, 6- повар, 7- радист и техник, 8- радист и техник, 9- повар и техник, 10- повар и техник. решение

10 Биржа труда На биржу пришли семь человек. Им предложили десять рабочих мест по тем специальностям, которыми они владеют. Смогут ли все семеро получить работу по специальности? 1- столяр, плотник и паркетчик 2 – столяр, плотник и паркетчик 3- столяр, плотник и паркетчик 4- паркетчик 5- монтажник, сварщик, бетонщик и шофер 6- монтажник, маляр, крановщик и бульдозерист 7- сварщик, бетонщик, шофер, крановщик и бульдозерист решение

11 Транспортная задача. Между городами А и В имеется сеть дорог, и на некоторых из них движение одностороннее. Кроме того, задана пропускная способность каждой дороги, скажем в тысячах машин в час. Попробуем ответить на вопрос: какой максимальный поток машин возможен из А в В и из В в А? Как видим, хотя из А может выезжать в час 7 тыс. машин, но въехать в В в час смогут лишь 4 тыс. из них. Несложно проверить, что 4 тыс. машин в час остальные дороги в состоянии пропустить. С другой стороны, из В в А могут выехать 3 тыс. машин в час, однако въехать в А за час смогут лишь 2 тыс. Поток в 2 тыс. машин из В в А остальные дороги, как нетрудно убедиться, также смогут пропустить.

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

13 Задача о четырех красках Внимательно рассматривая географическую карту, можно заметить, что кроме графов, изображающих железные или шоссейные дороги, есть еще один – граф, состоящий из границ между странами (областями, районами). Сами границы служат ребрами, а вершинами этого графа являются точки, в которых сходятся границы трех или более стран. Задача, о которой мы хотим рассказать, ведет свою историю с 1852 года. Однажды английский студент Френсис Гутри раскрашивал карту Великобритании. Каждое графство он выделял цветом. К сожалению, выбор красок у него был невелик, и приходилось их использовать повторно. Гутри старался, чтобы два графства, имеющие общий участок границы, были окрашены в разные цвета. Это занятие заставило его задуматься о том, какого наименьшего числа красок достаточно для раскрашивания любой карты. Гутри считал, что четырех красок всегда хватит, но доказать это не мог. Проблема некоторое время активно обсуждалась среди лондонских студентов, а потом о ней забыли. В 1879 г. известный английский математик Артур Кэли опубликовал эту задачу в первом томе «Трудов Королевского географического общества», и она получила широкую известность. Со временем интерес к «проблеме четырех красок» рос, но она не поддавалась усилиям даже выдающихся математиков. В 1890 г. английский математик Перси Хивуд доказал, что пяти красок хватит для раскрашивания любой карты. В 1968 г. было доказано, что карту, на которой обозначено меньше 40 стран, всегда можно раскрасить с помощью четырех красок.

14 Наконец, в 1976 г. американские математики Кеннет Аппель и Вольфганг Хакен решили эту задачу с помощью компьютера. Они разбили все карты на 2000 типов. Компьютер по составленной ими программе исследовал, может ли в рассматриваемом типе карт найтись такая, для которой не достаточно четырех красок. С тремя типами карт компьютер не справился, и над ними пришлось потрудиться самим математикам. Получив ответ «нет» для всех 2000 типов, исследователи объявили, что проблема четырех красок решена. Почтовое отделение при университете, в котором работали Аппель и Хакен, в тот день гасило марки на письмах штемпелем со словами: «Четырех красок достаточно». Задачу о четырех красках можно представить и несколько иначе. Рассмотрим для произвольной карты следующий граф: его вершины – столицы государств, а ребрами связаны те из них, чьи государства имеют общий участок границы. Для полученного графа задача формулируется так: раскрасить его вершины, используя только четыре краски, чтобы при этом любые две вершины, которые соединены ребром, были разного цвета.

15 Рим Париж Берн Вена Люксембург Брюссель Гаага Берлин Копенгаген Мадрид Лиссабон

16 1- географ, 2 – географ, 3- географ и врач, 4-радист, повар и техник, 5-радист и техник, 6- повар, 7- радист и техник, 8- радист и техник, 9- повар и техник, 10- повар и техник географ врач радист повар техник

17 1- столяр, плотник и паркетчик 2 – столяр, плотник и паркетчик 3- столяр, плотник и паркетчик 4- паркетчик 5- монтажник, сварщик, бетонщик и шофер 6- монтажник, маляр, крановщик и бульдозерист 7- сварщик, бетонщик, шофер, крановщик и бульдозерист столяр плотник паркетчик монтажник сварщик маляр бетонщик шофер крановщик бульдозерист

18 Строительст во котлована Укладка фундамент а Монтаж стен и перекрыти й Устройств о кровли Утвержде ние проекта Строительство дорог Подвод электроэнерги и Установка электрооборудован ия Установка газовых плит Прокладка канализации Установка сантехники Приемка Прокладк а телефонн ого кабеля Подвод газа Прокладка водопрово да Отделка Установка телефоно в