Содержание к диссертации
Введение
Глава 1. Теоретические основы активизации обучения с учетом психологических и педагогических аспектов работы с ЭВМ .
1. Теоретические основы активизации обучения 11
2. Развитие мышления 22
3. Формирование мотивов учения 26
4. Пробуждение интереса к предмету 30
5. Развитие логического мышления при изучении нового материала 31
6. Характеристика математического редактора 35
7. Возможности математического редактора по обмену информацией 38
8. Включение математического редактора в учебный процесс 42
9. Информационные процессы 45
10. Операционное освоение математического редактора 48
11. Ввод математического текста 51
12. Общие дидактические замечания 55
Глава 2. Реализация педагогического эксперимента и анализ результатов исследования
1. История рождения и развития теории графов 62
2. Понятия, определения, свойства 63
3. Применение теории графов 68
4. Прикладные задачи, решаемые на графах 74
5. Загрузка программы MAPLE 81
6. Ввод и назначение команд 82
7. Общие приемы работы в среде Maple 97
8. Условия работы Maple 101
9. Некоторые недостатки работы программы Maple 101
10. Анализ результатов исследования 104
Заключение 115
Литература 117
Приложение N1: лабораторные работы 126
Приложение N2: выявление карты интересов 159
- Теоретические основы активизации обучения
- Формирование мотивов учения
- История рождения и развития теории графов
- Применение теории графов
Введение к работе
Актуальность темы исследования.
Воспитание полноценной личности в плане хорошего владения вычислительной техникой - одна из главных задач современных высших учебных заведений. Необходимость информатизации и компьютеризации общества и образования рассматривается в работах Кана Р.Е., Бобко И.М., Молокова Ю.Г., Скибицкого Э.Г., Клеймана Г.М., Ростовцева А.Н., Роберта И.В., Хантера Б. "Национальная стратегия: а) достижение всеобщей компьютерной грамотности молодежи, обеспечивающей глубокое освоение основ наук и подготовку к будущей практической деятельности, б) повышение эффективности системы образования и воспитания на основе новых информационных технологий". "Стратегический подход к информатизации общества состоит в том, что она выступает как новый существенный фактор его социально-экономического развития". [31, с.4].
"Информатизация образования существенно влияет на качество образовательной системы, готовящей специалистов для будущего образовательного общества" [12, с.9]. Задача компьютерного образования, наряду с другими учебными дисциплинами - в полной мере способствовать индивидуальному развитию учащихся в процессе познания ими окружающего мира с помощью ЭВМ.
Анализ вузовского учебного плана приводит к выводу, что уровень изучения математики качественно повышается только первые два или три года, затем идет "спиралевидное" повторение уже изученного. Начинается рутинная работа по вычислениям и решениям различного рода однотипных примеров. Учащийся начинает задумываться об ускорении процесса и если не находит выхода, то у студента пропадает в большей части интерес к математическим дисциплинам. А ведь "интерес к предмету - это наиболее действенный мотив учения, делающий процесс познания привлекательным для учащихся" [28, с.38]. Тем более к
такой специфичной области, как теория графов, которая хотя и читается не только в университетах, но и является обязательной дисциплиной во многих технических вузах, все-таки для начинающего изучение теории графов приводит к затруднениям, т.к. часто игнорируется большинство задач на графах. А в педагогических институтах графы изучаются в лучшем случае на спецкурсах или факультативах. Причем, графы подаются либо мелом на доске, а если применяют компьютер, то ориентируются на моделирование графов с помощью языков программирования, а программирование понятно далеко не всем.
С другой стороны происходит совершенствование компьютерной техники, бурное увеличение количества различных программных средств и новых пользовательских технологий естественно привлекает к себе учащихся. "В процессе широкой информатизации современного общества существенное значение приобретает использование компьютерной техники как носительницы программных и информативных систем при организации учебного процесса разного уровня. Роль этой техники (и прежде всего персональных компьютеров) сопоставима с ролью книг, бумаги, ручек в процессе обучения. " [22, с.68] "Целесообразность применения компьютерной техники в учебном процессе обуславливается целями повышения эффективности обучения и расширения педагогических возможностей учителя" [85, с.78].
Информатика в учебных планах занимает по объему все больше и больше места, хотя компьютерной практики по-прежнему недостаточно. Студенты старших курсов физико-математического факультета, владея основным арсеналом действий по управлению компьютером и программным обеспечением, стремятся к самостоятельной работе по освоению новых незнакомых пакетов программ и эту способность надо поддержать педагогу, развить интерес, дать систему действий для самосовершенствования студентов.
Очевидна необходимость интеграции информатики и математики с целью оптимизации и активизации обучения, которая позволит высвободить значи
тельное время для изучения новых современных направлений в математике, одним из которых является молодая, по историческим меркам, теория графов. "Можно поставить проблему разработки новых технологий обучения, основанных на применении компьютера в качестве средства формирования (организации и управления) учебной деятельностью, постановки и решения учебных задач, выполнения учебных действий в полном составе их компонентов. Для реализации этого должны быть разработаны специальные компьютерные обучающие среды (КОСы), ориентированные на применение ЭВМ " [22, с.69]. То есть компьютер выступает как средство обучения и эффективность его применения определяется качеством и совершенством соответствующих педагогических программных средств, отвечающих частным дидактическим принципам: принципу уместности и целесообразности, принципу ориентации на потребности обучаемого в знаниях, умениях и навыках по конкретной дисциплине, принципу информационной упорядоченности теоретического материала, принципу диалоговой формы взаимодействия, принципу сочетания различных видов заданий, принципу систематичности и последовательности предъявления обучающимся проблемных сшуаций, принципу соблюдения адекватности автоматизированных дидактических актов функциям деятельности преподавателя и обучающегося, принцип модульного построения [13, с.5].
Таких программ в мире немало, но не все они доступны обучающимся в силу объективных причин и не все целесообразны для конкретного учебного процесса. Поэтому надо искать подходящие программы среди доступных, которые наглядно, быстро и доступно поддерживали работу человека, решающего какую-либо прикладную задачу, с графами. Одна из таких программ называется Maple for Windows, разработана фирмой WATERLOO MAPLE SOFTWARE в 1994 году как инструментальное средство для решения различных математических задач. Так как применение компьютера как средства обучения основано прежде всего на графических и вычислительных возможностях, то Maple в пол ной мере обладает этими возможностями. Но просто наличие программы для педагога еще ничего не значит. Эту программу нужно проанализировать самому педагогу с точки зрения качественности программного обеспечения, овладеть этой программой, чтобы затем преподнести ее в понятном виде для обучающихся. На этот аспект стоит обратить особое внимание, так как лавинообразное увеличение программного обеспечения не сопровождается учебно-методической литературой и большинство справочных программ на английском языке. Преподаватель остается один на один с таинственной программой, которую надо освоить за короткий срок и включить в учебный процесс в виде лекций, практических и лабораторных занятий, являющихся для остальных лишь вершиной айсберга громадной работы. То есть нужно разработать технологию обучения, как систему способов и методов, выбранных в соответствии с поставленными дидактическими задачами.
Таким образом, анализируя содержание учебных планов современных вузов и науки (информатики, математики и педагогики) можно сделать вывод о существовании противоречия между потенциально высокой эффективностью компьютерных занятий и незначительным использованием компьютеров в обучении теории графов.
Указанное противоречие позволяет сформулировать проблему исследования: как организовать деятельность студентов по применению теории графов и компьютеров для решения прикладных задач.
Исходя из поставленной проблемы можно определить объект, предмет и цель исследования.
Объект исследования - процесс изучения теории графов при выполнении студентами лабораторных занятий в компьютерном классе.
Предмет исследования - педагогические средства активизации учебной деятельности, направленной на изучение теории графов.
Цель исследования: разработать и экспериментально апробировать педагогическую систему активизации обучения студентов теории графов с применением компьютеров.
В ходе исследования была выдвинута гипотеза, согласно которой система занятий в курсе теории графов будет эффективна, если:
1) в основу организации учебной деятельности будет положен комплекс учебных задач, отражающий изучение студентами основных положений теории графов;
2) часть задач будет иметь прикладной характер, отражающих основные задачи теории графов;
3) использовать средство обучения, представляющее собой программное обеспечение MAPLE на современных компьютерах (IBM 586, Pentium) и специальное пособие для студентов, ориентированное на применение MAPLE в изучении теории графов.
Исходя из цели и гипотезы определены следующие задачи исследования:
1. Разработать систему лабораторных занятий в курсе теории графов, включающую систему заданий по основам теории и прикладные задачи.
2. Развить и закрепить навыки практической работы студентов компьютером.
3. Экспериментально проверить эффективность авторской программы компьютерного курса теории графов с использованием разработанного учебного пособия.
Для решения поставленных задач был использован комплекс методов исследования: наблюдение, собеседование, тестирование, анализ литературы, эксперимент, теоретический анализ.
Научная новизна и практическая значимость исследования.
1. Разработана система компьютерных занятий в курсе теории графов, позволяющая использовать адаптированные для студентов методы и способы применения MAPLE для решения прикладных задач теории графов.
2. Составлено учебное пособие для студентов физико-математического факультета по использованию программы MAPLE в курсе теории графов.
3. Разработана система тестирования знаний учащихся.
Апробация и внедрение результатов исследования.
Основные положения диссертации доложены на заседаниях региональных научно-практических конференциях в городе Новокузнецке.
По теме диссертационного исследования прочитаны лекции и проведены занятия со студентами Новокузнецкого государственного педагогического института.
По теме диссертации опубликовано 8 работ.
На защиту выносится:
1. Система компьютерных занятий по курсу теории графов, позволяющая использовать адаптированные для студентов методы и способы использования MAPLE для решения основных прикладных задач теории графов.
2. Педагогические условия, позволяющие эффективно развивать познавательные интересы учащихся.
1Структура диссертационного исследования.
Диссертация состоит из введения, двух глав, приложения, списка использованной литературы. Объем основного текста 116 страниц. В приложении приводятся лабораторные работы, которые апробировались на студентах физико-математического факультета НГПИ. Все файлы, имена которых указаны в заданиях, имеются в компьютерных классах, где проводились занятия. Список литературы состоит из 113 источников.
Теоретические основы активизации обучения
Различные стороны активизации обучения рассматриваются в трудах Ивановой Л.А., Бабанского Ю.К., Коптелова А.В., Кузнецова В.Е., Савченкова А.И., Кулыгиной Л.С., Лосевой С.А., Харламова И.Ф., Шамоновой Т.И., Щукиной Г.И.
Любая деятельность человека имеет определенную цель. Основная цель работы учителя по активизации познавательной деятельности обучающихся -развитие их творческих способностей. Достижение этой цели позволяет решить многие задачи обучения: обеспечить прочные и осознанные знания изучаемого материала; подготовить обучающихся к активному участию в производственной деятельности, умению самостоятельно выполнять задания; воплощать в жизнь научно-технические решения; осваивать новые специальности; дать высшим учебным заведениям страны хорошо подготовленных абитуриентов, способных творчески овладеть выбранной специальностью.
Умелое применение приемов и методов, обеспечивающих высокую активность обучающихся в обучении, их самостоятельность в учебном познании, является средством развития познавательных способностей обучаемых.
Итак, развитие творческих познавательных способностей обучающихся -цель деятельности педагога, а применение различных приемов активизации является средством достижения этой цели.
Учение предполагает усвоение обучаемым социального опыта предшествующих поколений в диалектическом единстве с развитием и воспитанием личности. Участие в этом процессе принимают и преподаватель, и учащиеся. "Внешняя природа, люди и вся их жизнь дают организму лишь побуждение и материал для деятельности, но самая деятельность есть его собственная, своеобразная" [32, с.358].
Это положение принципиально определяет сущность понимания образовательного процесса как выражения внутренней самодеятельности человеческого организма. Знания, умения и навыки - результат самодеятельности учащегося в учебном процессе.
С современных позиций дидактов процесс учения "представляет собой организованную учителем или самим учеником целенаправленную самоуправляемую отражательно-преобразующую деятельность по овладению знаниями, способами их добывания, переработки и применения" [108, с.32]. Структура самоуправления учением включает в себя мотивационный, ориентационный, содержательно-операционный, ценностно-волевой и оценочный компоненты. Поскольку учение всегда носит до некоторой степени вынужденный характер, наблюдается противоречие, связанное с невозможностью осуществить его иначе как через самодеятельность человеческого организма. Не принуждение, а побуждение к активности и предполагает истинная активизация учения. Успешность ее практической реализации определяется не только применения средств, активизирующих учение, но главным образом целесообразностью их выбора и направленностью воздействия. Отдельные средства активизации учения и эпизодические удачные уроки не могут полноценно влиять на этот процесс. Поэтому вполне закономерно выделить критерии выбора и эффективности применения совокупности средств активизации учения, включающих элементы учебного содержания, конкретные методы, приемы и организационные формы обучения.
Заботясь о развитии обучающихся, необходимо чаще использовать активные методы обучения. Одновременно необходимо отдавать себе отчет в том, являются ли используемые приемы и методы оптимальными, отвечающими имеющемуся развитию обучающихся и задаче дальнейшего совершенствования их познавательных умений.
Психолог К.А. Абульханова-Славская, исследуя активность и сознание личности как субъекта деятельности, следующим образом определяет это понятие: "В самом общем виде активность - это присущий личности способ объективизации, самовыражения (и в деятельности, и в обучении, и в жизненном пути в целом) в соответствии с ее высшими потребностями в признании, ценности и т. д. . Личность посредством своей активности находит предметы, условия и ситуации удовлетворения потребностей, регулирует отдельные действия и поступки и определенным образом категоризирует, моделирует, преобразует действительность.
Активность в широком смысле слова - это гфисущий личности способ организации жизни, регуляции саморегуляции на основе интеграции потребностей, способностей, отношений личности к жизни, с одной стороны, и требований к личности общества и обстоятельств - с другой. [78, с. 113].
Активность индивида в ее динамическом аспекте определяется как совокупность признаков, характеризующих силу внутренней тенденции и стремлений индивида к действованию, проявляющихся в скорости, энергичности, инициативности и разнообразии совершаемых им действий в процессе того или иного взаимодействия.
В исследованиях В. С. Ротенберга и В. В. Аршавского показано, что основным компонентом поведения, определяющим устойчивость организма и степень сохранности его здоровья, является поисковая активность. Состояние отказа от поиска отрицательно сказывается на результатах любой деятельности. Поисковая активность раскрывает сущность жизненной активности человека. Психология однозначно определяет ее основной источник в познавательной и практической деятельности - это потребности. "Чтобы удовлетворить свои потребности, человек должен найти для этого пути и средства в сложном социальном мире, он должен уметь ставить перед собой и решать практические и теоретические задачи. В связи с этим мышление выступает в качестве такого психического процесса, который обеспечивает поиск необходимых средств, способов и методов удовлетворения возникших потребностей" [97 , с. 14]. Потребность в поиске - как бы пружина, движущая сила саморазвития и самосовершенствования.
Формирование мотивов учения
Мотивы, побуждающие к приобретению знаний, могут быть различными. К ним относятся прежде всего широкие социальные мотивы: необходимо хорошо учиться, в будущем овладеть желаемой специальностью, больше пользы Родине, чувство долга, ответственность перед коллективом и т. д. Однако, как показывают исследования, среди всех мотивов обучения самым действенным является интерес к предмету. Интерес к предмету осознается учащимися раньше, чем другие мотивы учения, им оно чаще руководствуются в своей деятельности, он для них более значим (имеет личностную ценность) и потому является действенным, реальным мотивом учения. Из этого, конечно, не следует, что обучать нужно лишь тому, что интересно. Познание - труд, требующий большого напряжения. Поэтому необходимо воспитывать у учащихся силу воли, преодолевать трудности, прививать им ответственное отношение к своим обязанностям. Но одновременно стремиться облегчать им процесс познания, делая его привлекательным. Еще К. Д. Ушинский писал:" ученье, лишенное всякого интереса и взятое только силою принуждения... убивает в ученике охоту к учению, без которого он далеко не уйдет". [ 96, с.249]
Под познавательным интересом к предмету понимается избирательная направленность психических процессов человека на объекты и явления окружающего мира, при которой наблюдается стремление личности заниматься именно данной, областью. Интерес - мощный побудитель активности личности, под его влиянием все психические процессы протекают особенно интенсивно и напряженно, а деятельность становится увлекательной и продуктивной. "Сущность познавательного интереса в стремлении проникнуть в познаваемую область более глубоко и основательно, в постоянном побуждении заниматься предметом своего интереса" [ПО, с.24]
В формировании познавательного интереса учащихся можно выделить несколько этапов. Первоначально он проявляется в виде любопытства - естественной реакции человека на все неожиданное, интригующее. Любопытство, вызванное неожиданным результатом опыта, интересным фактам, приковывает внимание учащегося к материалу данного урока, но не переносится на другие уроки. Это неустойчивый, ситуативный интерес.
Более высокой стадией интереса является любознательность, когда учащийся проявляет желание глубже разобраться, понять изучаемое явление. В этом случае умник обычно активен на уроке, задаст учителю вопросы, участвует в обсуждении результатов демонстраций, приводит свои примеры, читает дополнительную литературу, конструирует приборы, самостоятельно проводит опыты и т. д.
Какими же качествами должен обладать учитель, чтобы его отношения с учащимися содействовали появлению и проявлению интереса к предмету? Как показывают исследования Г.И. Щукиной [111, 112], ими прежде всего являются:
1) эрудиция учителя, умение предъявлять ученикам необходимые требования и последовательно усложнять познавательные задачи, такие учителя обеспечивают в классе интеллектуальный настрой, приобщают учащихся к радости познания;
2) увлеченность предметом и любовь к работе, умение побуждать учащихся к поиску различных решений познавательных задач;
3) доброжелательное отношение к учащимся, создающее атмосферу полного доверия, участливости. Все это располагает к тому, что можно спокойно подумать, найти причину ошибки, порадоваться своему успеху и успеху товарища и т.д.;
4) педагогический оптимизм - вера в ученика, в его познавательные силы, умение своевременно увидеть и поддержать слабые, едва заметные ростки познавательного интереса и тем побуждать желание узнавать, учиться.
Наука есть наука и ничего не носит в себе. Воспитательный же элемент лежит в преподавании наук, в любви учителя к своей науке и в любовной передаче ее, в отношении учителя к ученику. Хочешь наукой воспитать ученика, люби свою науку и знай ее, и ученики полюбят и тебя, и науку, и ты воспитаешь их; но ежели ты сам не любишь ее, то сколько бы ты ни заставлял учить, наука не произведет воспитательного влияния [Лев Толстой, "Воспитание и образование", т.8, с.245].
Учитель может не обладать всеми указанными достоинствами (хотя должен к этому стремиться). Но опыт показывает, что если учитель в совершенстве обладает хотя бы одним из этих качеств, то он часто добивается значительных успехов в обучении и развитии учащихся.
Сниженный уровень требований к познавательной деятельности учащихся, формальный подход учителя к своей работе, раздражительность учителя ведут к потере у учащихся интереса к предмету, к конфликту с учителем, к разрушению взаимного понимания между учителем и учащимися.
Правильный стиль отношений с учащимися (деловой, увлеченный, доброжелательный) - основа успеха педагогической деятельности.
Чтобы пробуждать и развивать интерес, учитель должен любить свой предмет, рассматривать воспитание учащихся и обучение их своему предмету как высокий гражданский долг, соотносить задачи обучения и воспитания учащихся с социально-экономическими задачами общества и во всех своих действиях и поступках проявлять себя как личность, обладающая активной жизненной позицией.
Итак, формирование интереса к предмету - сложный процесс, предполагающий использование различных приемов в системе средств развивающего обучения и правильного стиля отношений между учителем и учащимися.
История рождения и развития теории графов
Вторая половина 18 века. Господин Эйлер, гуляя по кенигсбергским мостам, однажды задумался на задачей: можно ли обойти все мосты ровно по одному разу и вернуться в исходную точку. Взяв перо и бумагу, Эйлер нарисовал следующую схему, в которой точки обозначают острова, а отрезки - мосты (см. рис.1)
Графы - это не динозавры и не микробы, не сугубо теоретическая вещь, а достаточно простое понятие, потому они встречаются повсюду, просто мы не задумываемся, что это - граф: схема железных дорог и карта метро, электросхемы и созвездия, лабиринты и каналы и многое другое.
До 20 века единой теории еще не было, имелись лишь занимательные задачи и головоломки, решение которых сводилось к графам, так как другое решение было ненаглядным, долгим, нерациональным, неполным или неточным. Как самостоятельная ветвь математики теория графов начала складываться в начале 20 века, а особенно бурное развитие получила с развитием вычислительной техники - компьютеров.
Построим граф G, вершины которого биективно (т.е. взаимнооднозначно) соответствуют лекциям, и две вершины смежны тогда и только тогда, когда соответствующие лекции нельзя читать одновременно. Очевидно, что любая правильная раскраска этого графа определяет допустимое расписание: лекции, соответствующие вершинам графа, составляющим цветной класс (вершины одного цвета), читаются одновременно. И, обратно, любое допустимое расписание определяет правильную раскраску графа G. Оптимальные расписания соответствуют минимальным раскраскам, а число часов, необходимое для прочтения всех лекций, равно минимальному числу красок.
Заданы множества V=(vi,..,vn) и S= (si,..,Sn) работ и механизмов соответственно. Для выполнения каждой из работ требуется некоторое время, одинаковое для всех работ, и некоторые механизмы. При этом никакой из механизмов не может быть одновременно занят в нескольких работах. Нужно распределить механизмы так, чтобы общее время выполнения всех работ было минимальным.
Построим граф G, в котором вершины смежны тогда и только тогда, когда для выполнения работ v, и Vj требуется хотя бы один общий механизм. При правильной раскраске графа G работы, соответствующие вершинам одного цвета, можно выполнять одновременно, а наименьшее время выполнения всех работ достигается при минимальной раскраске.
3. Задача о проектировании коробки скоростей. Коробка скоростей - механизм для изменения частоты вращения ведомого вала при постоянной частоте вращения ведущего. Это изменение происходит за счет того, что находящиеся внутри коробки шестерни вводятся в зацепление специальным образом. Одна из задач, стоящая перед конструктором коробки, заключается в минимизации ее размеров, а это часто сводится к минимизации числа валов, на которых размещаются шестерни.
Построим граф G, вершины которого биективно соответствуют шестерням. Если по какой-то причине две шестерни не должны находиться на одном валу, то соответствующие вершины соединим ребром. Вершины, имеющие один цвет при правильной раскраске этого графа, определяют шестерни, кото 76 рые могут находиться на одном валу, а хроматическое число равно количеству валов.
4. Политическая карта. Раскрасить карту так, чтобы любые два граничащие государства имели разный цвет. Государства - вершины, если граничат - соединяем ребром.
Задачи, решаемые поиском остовного графа минимального веса (разновидность евклидовой задачи Штейнера [13,с.б2]). Задача. Проектирование линий электропередачи, трубопроводов, дорог и т.п., когда требуется заданные центры соединить системой каналов связи так, чтобы любые два центра были связаны либо непосредственно, либо через другие центры и чтобы сумма длин была минимальной.
Решение. Надо создать полный граф из этих центров-вершин и найти остов минимального веса.
Имеются три дома А,В,С и три колодца 1,2,3. Каждый хозяин пользуется любым из трех колодцев. В некоторый момент обитатели домов решили проложить дорожки до колодцев так, чтобы исключить встречи на них, т.е. чтобы дорожки не пересекались. Возможно ли это Задачи, сводящиеся к поиску кратчайшего пути.
Задача. Имеется лабиринт. Найти кратчайший путь к выходу. Решение. Вершины - перекрестки, ребра - коридоры.
1. Замкнутое кругосветное путешествие. Пусть даны 20 городов. Будем считать для простоты, что они расположены в вершинах правильного додекаэдра, условно изображающего Землю. Тогда оказывается возможным осуществить "кругосветное путешествие", двигаясь по ребрам додекаэдра, побывав в каждом городе один только раз.
2. Ход шахматного коня. Обойти шахматным конем шахматную доску так, чтобы побывать в каждой клетке ровно по одному разу.
3. Задачи о коммивояжере. Район, который должен посетить бродячий торговец, содержит некоторое количество городов, расстояния между которыми известны. Требуется найти маршрут, проходящий через все пункты по одному разу и возвращающийся в исходный. Если таких маршрутов много, требуется найти кратчайший из них. Часто встречается на практике там, где возникает вопрос о наилучшем упорядочении каких-либо действий, объектов, предметов и т.
Различные варианты задачи оптимального упорядочения объектов возникают при планировании рационального использования транспорта. Например, при определении маршрута развозки продуктов по торговым точкам города так, чтобы суммарная длина пробега машин была бы минимальной; при выборе минимальной по протяженности автобусной линии в городе, на ряде улиц которого возможно лишь одностороннее движение и фиксировано местоположение остановок автобуса. Некоторые варианты этой задачи используются также при рациональной расстановке указателей в музее, когда известно местоположение каждого экспоната и расстояние между любыми двумя из них и требуется установить такой порядок осмотра, при котором затрачивается минимум времени на переходы между экспонатами.
Применение теории графов
В настоящее время такие дисциплины, как физика, химия, экономика, исследование операций, социология, а также многие другие, имеющие важное прикладное значение, широко используют методы дискретной математики и полученные в ней результаты. Эти результаты очень важны, например, при разработке различных технических устройств с дискретным принципом действия, построения машинных алгоритмов, в планировании и радиоэлектронике.
В дискретной математике особое место занимают задачи, связанные с упорядочиванием тех или иных объектов и построением сложных конструкций путем "правильного" соединения отдельных элементов, а также задачи, в которых изучаются отношения между различного рода объектами.
В рамках теории графов хорошо моделируются на математическом языке задачи, связанные с построением схем, планированием, идентификацией в органической химии, изучением функционированием "малых групп" в социологии и другие.
Граф на рис.15 изображает схему дорог между селами М, А, Б, В и Г. Здесь каждые две вершины соединены между собой ребром. Числа на рисунках указывают расстояния между селами по этим дорогам. Пусть в селе М находится почта и почтальон должен развести письма в остальные четыре села. Существует много различных маршрутов поездки. Как из них выбрать наикратчайший?
Проще всего проанализировать все варианты. Сделать это может новый граф, на котором легко увидеть возможные маршруты. Вершина М - начало пути. Из нее можно начать путь четырьмя различными способами: в А, в Б, в В или в Г. После посещения одного из сел остается три возможности продолжения маршрута, потом две, потом дорога в последнее село и вновь в М. Всего 4*3*2*1=24 способа.
Все они на рисунке 16:
Расставим вдоль его ребер цифры, обозначающие расстояния между селами, а в конце каждого маршрута напишем сумму этих расстояний по маршруту. Из полученных 24 чисел наименьшими являются два числа по 28 км, соответствующие маршрутам М-В-Б-А-Г-М и М-Г-А-Б-В-М. Нетрудно заметить, что это один и тот же путь, но пройденный в разных направлениях. Подобные задачи возникают часто при нахождении наилучших вариантов развозки товаров по магазинам, материалов по стройкам.
В строительстве графы используются при планировании проведения работ. Граф, изображенный на рис.17, называется сетевым графиком строительства. В данном случае он составлен для строительства жилого дома. Вершины этого графа обозначают отдельные виды работ на стройке, кроме того, есть еще две вершины: начало строительства и его окончание. Стрелки означают, что один вид работ не может начаться раньше другого. Нельзя начинать монтаж стен, не закончив строить фундамент, чтобы приступить к отделке, нужно иметь на этажах воду, а для сварочных работ нужно иметь подвод электричества. Около вершин графа указаны в числа- продолжительность в днях соответствующей работы. Теперь мы можем узнать наименьшую возможную продолжительность строительства. Для этого из всех путей по графу нужно выбрать тот, у которого сумма чисел при вершинах наибольшая. Он называется критическим путем. В нашем случае получаем 170 дней.
Графы часто используются для решения логических проблем, связанных с перебором вариантов. Например. В ведре 8 л воды, и имеются две кастрюли емкостью 5 и 3 л. Требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4 л, то есть разлить воду поровну в ведро и большую кастрюлю. Ситуацию в каждый момент можно описать тремя числами (x,y,z), где х - количество литров в ведре, у - в большой кастрюле, z - в меньшей. В начальный момент ситуация описывалась тройкой чисел (8,0,0), от нее мы можем перейти в одну их двух ситуаций: (3,5, 0), если наполним водой большую кастрюлю, или (5,0,3), если наполним меньшую кастрюлю. В результате получаем (см. рис Л 8) два решения: одно в 7 ходов, другое в 8 ходов.
Подобным образом можно составить граф любой позиционной игры: шахмат, шашек, "крестиков-ноликов", где позиции станут вершинами, а направленные отрезки между ними будут означать, что одним ходом можно перейти от одной позиции к другой, по направлению стрелки. Однако для шахмат и шашек такой граф будет очень большим, поскольку различные позиции в этих играх исчисляются миллионами. А вот для игры в "крестики-нолики" на доске соответствующий граф нарисовать не так уж и трудно, хотя и он будет содержать несколько десятков (но не миллионов) вершин.
Свойства графов не зависят от того, соединены вершины отрезками или кривыми линиями, что дает возможность изучения их свойств с помощью одной из молодых наук - топологии.
