extracted_text:
Современные педагогические
технологии по ФГОС
Инновационные технологии.
- информационно-коммуникативные технологии;
которой отводится большое значение, т.к. ученик должен владеть информацией,
уметь ею пользоваться, выбирать из нее необходимое для принятия решения,
работать со всеми видами информации и т.д. И сегодня учитель должен понимать,
что в информационном обществе он перестает быть единственным носителем знания,
как это было раньше. В некоторых ситуациях ученик знает больше, чем он, и роль
современного учителя – это в большей степени роль проводника в мире информации.

- проектная технология (создание проектов,
презентаций)
- коммуникативное обучение (обучение в
процессе общения)
- портфолио (дневник личностного роста
ученика)
- исследовательская деятельность.
- проблемное обучение (использование
проблемных ситуаций)
- игровые технологии (использование
развивающих игр с определённой педагогической целью).
 - диалог культур;
- развивающее обучение (Занков, Эльконин,  Давыдов)

Использование
ИКТ
Уроки с использованием информационных
технологий имеют ряд преимуществ перед традиционными уроками.

        Урок с использованием
информационных технологий становится более интересным для учащихся, следствием
чего, как правило, становится более эффективное усвоение знаний; улучшается
уровень наглядности на уроке.

        Использование некоторых
компьютерных программ позволяет облегчить труд педагога: подбор заданий,
тестов, проверка и оценка качества знаний, тем самым на уроке освобождается
время для дополнительных заданий (за счет того, что материалы заранее
заготовлены в электронном виде).
        Повышение эффективности урока за
счет наглядности. Конечно, достигнуть этого можно и другими методами (плакаты,
карты, таблицы, записи на доске), но компьютерные технологии, бесспорно,
создают гораздо более высокий уровень наглядности.
        Возможность продемонстрировать явления,
которые в реальности увидеть невозможно. Современные персональные компьютеры и
программы позволяют с помощью анимации, звука, фотографической точности
моделировать различные учебные ситуации, имеют возможность представления в
мультимедийной форме уникальных информационных материалов (картин, рукописей,
видеофрагментов); визуализации изучаемых явлений, процессов и взаимосвязей
между объектами.
       Информационные технологии
предоставляют широкие возможности для индивидуализации и дифференциации обучения,
причем не только за счет разноуровневых заданий, но также и за счёт
самообразования учащегося.

Единую структуру урока с использованием
ИКТ выделить сложно, так как каждый урок индивидуален.
     Разработка урока с использованием
информационных технологий возможна лишь при наличии электронного ресурса.
Учебные электронные ресурсы содержат:
         1.  Иллюстрации учебного
материала (таблицы, схемы, опыты, видеофрагменты);
         2.  Поддержку учебного материала
(задания, тесты и т.д.)
         3.  Источник учебного материала
(электронный учебник, разработка задания для самостоятельной работы учащегося).

По способу
разработки они могут принадлежать к одному из следующих видов:
1.  Интернет
ресурсы (могут использоваться не только непосредственно на уроке, но и для
подготовки).
          2.  Специальные (сюда включаются
все электронные ресурсы, выпускаемые различными издательствами).
          3.  Универсальные (Word, Excel,
Power Point и т.д.- предназначены для создания педагогами собственных образовательных
ресурсов).
          Самыми интересными и
эффективными уроками являются уроки с использованием универсальных
образовательных ресурсов, то есть уроки, разработанные педагогом с учётом
особенностей конкретного ученического коллектива и для конкретных учащихся. В
процессе создания такого урока возникает уникальный образовательный ресурс, в
который вложены не только знания, умения и опыт педагога-разработчика, но и
частичка его души. Именно такие уроки будут наиболее интересны детям, а значит,
и наиболее эффективными.
           Использование компьютерных
технологий в процессе обучения влияет на рост профессиональной компетентности
учителя. Это способствует значительному повышению качества образования, что
ведет к решению главной задачи образовательной политики.

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

Основные требования к проекту.
     В современной педагогике метод
проектов используется не вместо систематического предметного обучения, а наряду
с ним как компонент системы образования.
1.Необходимо наличие социально значимой
задачи (проблемы) –исследовательской, информационной, практической.
2.Выполнение проекта начинается с планирования
действий по разрешению проблемы, (пооперационная разработка проекта)

3.Каждый проект обязательно требует исследовательской
работы учащихся.
Таким образом, отличительная черта
проектной деятельности – поиск информации, которая затем будет обработана,
осмыслена и представлена участникам проектной группы.
4.Результатом работы над проектом является
продукт.
5.Подготовленный продукт должен быть
представлен заказчику и (или) представителям общественности, и представлен
достаточно убедительно (презентация своего продукта).

То есть проект – это “пять П”:
Проблема – Проектирование (планирование) –
Поиск информации – Продукт – Презентация.
Шестое “П” проекта – его Портфолио, т.е.
папка, в которой собраны все рабочие материалы проекта, в том числе черновики,
дневные планы и отчеты и др.
Важное правило: каждый этап работы над
проектом должен иметь свой конкретный продукт!

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

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

Информационный проект
направлен на сбор информации о каком-то объекте, явлении с целью ее анализа,
обобщения и представления для широкой аудитории.
    Выходом такого проекта часто
является публикация в СМИ, в т.ч. в Интернете. Результатом такого проекта
может быть и создание информационной среды класса или школы.

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

Ролевой проект.
Разработка и реализация такого проекта наиболее сложна. Участвуя в нем,
проектанты берут на себя роли литературных или исторических персонажей,
выдуманных героев и т.п. Результат проекта остается открытым до самого
окончания. Чем завершится судебное заседание? Будет ли разрешен конфликт и
заключен договор?
По комплексности можно
выделить два типа проектов.
1) Монопроекты
проводятся, как правило, в рамках одного предмета или одной области знания,
хотя и могут использовать информацию из других областей знания и деятельности.
2) Межпредметные проекты
выполняются исключительно во внеурочное время и под руководством нескольких
специалистов в различных областях знания.
Проекты могут различаться и по
характеру контактов между участниками. Они могут быть:
- внутриклассными;
 - внутришкольными;
 - региональными;
 - межрегиональными;
 - международными.
Последние два типа проектов
(межрегиональные и международные), как правило, являются телекоммуникационными,
поскольку требуют для координации деятельности участников взаимодействия в сети
Интернет и, следовательно, ориентированы на использование средств современных
компьютерных технологий.
Классификация проектов по
продолжительности.
Мини – проекты могут укладываться в один
урок или менее.
Краткосрочные проекты требуют выделения 4
– 6 уроков.
Недельные проекты выполняются в группах в
ходе проектной недели.
Их выполнение занимает примерно 30 – 40
часов и целиком проходит при участии руководителя.
Годичные проекты могут выполняться как в
группах, так и индивидуально. Весь годичный проект – от определения проблемы и
темы до презентации выполняются во внеурочное время.

Презентация проектов.
Как уже отмечалось, одним из важных этапов
осуществления учебного проекта является презентация. Выбор формы презентации
проекта – задача не менее, а то и более сложная, чем выбор формы продукта
проектной деятельности. Набор “типичных” форм презентации, вообще говоря,
весьма ограничен, а потому здесь требуется особый полет фантазии (в сочетании с
обязательным учетом индивидуальных интересов и способностей проектантов –
артистических, художественных, конструкторско-технических, организационных и
т.п.)

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

В процессе проектной деятельности,
формируются следующие общеучебные умения и навыки:

1.Рефлексивные умения:
  - умение осмыслить задачу, для решения
которой недостаточно знаний;
  - умение отвечать на вопрос: чему нужно
научиться для решения поставленной задачи?
2.Поисковые (исследовательские) умения:
  - умение самостоятельно генерировать
идеи, т.е. изобретать способ действия, привлекая знания из     различных
областей;
  - умение самостоятельно найти
недостающую информацию в информационном поле;
 - умение запросить недостающую информацию
у эксперта (учителя, консультанта, специалиста);
 - умение находить несколько вариантов
решения проблемы;
 - умение выдвигать гипотезы;
 - умение устанавливать
причинно-следственные связи.
3.Навыки оценочной самостоятельности.
4.Умения и навыки работы в сотрудничестве:
 - умение коллективного планирования;
 - умение взаимодействовать с любым
партнером;
 - умения взаимопомощи в группе в решении
общих задач;
 - навыки делового партнерского общения;
 - умение находить и исправлять ошибки в
работе других участников группы.
5.Коммуникативные умения:
- умение инициировать учебное
взаимодействие со взрослыми – вступать в диалог, задавать вопросы и т.д.;
 - умение вести дискуссию;
 - умение отстаивать свою точку зрения;
 - умение находить компромисс;
 - навыки интервьюирования, устного опроса
и т.п.
6.Презентационные умения и навыки:
- навыки монологической речи;
 - умение уверенно держать себя во время
выступления;
 - артистические умения;
 - умение использовать различные средства
наглядности при выступлении;
 - умение отвечать на незапланированные
вопросы.

Проблемное обучение
         Проблемная ситуация - это
интеллектуальное затруднение человека, возникающее в случае, когда он не знает,
как объяснить возникшее явление, факт, процесс действительности, не может
достичь цели известным ему способом действия. Это побуждает человека искать
новый способ объяснения или способ действия. Проблемная ситуация есть
закономерность продуктивной, познавательной творческой деятельности. Она
побуждает начало мышления, активную, мыслительную деятельность, которая
протекает в процессе постановки и решения проблемы.
Познавательная потребность возникает у
человека в том случае, когда он не может достичь цели с помощью известных ему
способов действия, знаний. Эта ситуация и называется проблемной. Именно
проблемная ситуация помогает вызвать познавательную потребность учащегося, дать
ему необходимую направленность мысли и тем самым создать внутренние условия для
усвоения нового материала, обеспечить возможность управления со стороны
педагога.
Проблемная ситуация стимулирует
мыслительную деятельность учащегося в процессе обучения.
Проблемная ситуация - центральное звено
проблемного обучения, с помощью которого пробуждается мысль, познавательная
потребность, активизируется мышление, создаются условия для формирования
правильных обобщений.
   Совершенствование процесса обучения
определяется стремлением учителей активизировать учебно-познавательную
деятельность учащихся. Суть активизации обучения младшего школьника заключается
в такой организации учебной деятельности, при которой учащийся приобретает
основные навыки получения знаний и на основе этого научится самостоятельно
«добывать знания».
    Педагогическая практика показывает,
что возникновение проблемной ситуации и ее осознание учащимися возможно при
изучении почти каждой темы. Подготовленность ученика к проблемному обучению
определяется, прежде всего, его умением (или возникшую в ходе урока) увидеть
выдвинутую учителем проблему, сформулировать ее, найти решение и решить ее
эффективными приемами. На основе анализа психолого-педагогических исследований
можно сделать вывод, что проблемная ситуация представляет собой затруднение,
новых знаний и действий. В проблемной ситуации ученик ставится перед
противоречиями и потребностью самостоятельного поиска выхода из этих
противоречий.
    Основными элементами проблемной
ситуации являются вопросы, задача, наглядность, задание. Вопрос имеет
первостепенное значение, т. к. стимулирует и направляет мыслительную
деятельность учащихся.
    Задача является важным фактом
повышения познавательной активности учеников. Наглядность служит инструментом
«схватывания» обобщенного «видения» содержания новых абстрактных понятий и
представлений и облегчает формирование научных понятий.
   Человечество постоянно развивается,
поток информации постоянно увеличивается, но сроки ее интерпретации в школе
остаются прежними. Приоритет отдается осознанному усвоению знаний. Опора на
мотивационную сферу позволяет удерживать внимание к данному предмету, развивая
не только интеллектуальные, но и личностные качества учащихся. Учить, используя
традиционные формы, не оптимально. Поэтому именно за проблемным обучением
будущее современной школы.

Исследовательская
деятельность
  Цель работы
– стимулировать развитие интеллектуально-творческого потенциала младшего
школьника через развитие и совершенствование исследовательских способностей и
навыков исследовательского поведения.
  Задачи:
- обучение проведению учебных исследований
младших школьников
 - развитие творческой исследовательской
активности детей
 -стимулирование у детей интереса к
фундаментальным и прикладным наукам - ознакомление с научной картиной мира
 - вовлечение родителей в учебно-воспитательный
процесс
   Любая исследовательская работа (проект)
состоит из нескольких этапов.
Выбор темы.
Постановка цели и задач.
Гипотеза исследования.
Организация исследования.
Подготовка к защите и защита работы.
    Специфика исследовательской работы в
начальной школе заключается в систематической направляющей, стимулирующей и
корректирующей роли учителя. Главное для учителя – увлечь и “заразить” детей,
показать им значимость их деятельности и вселить уверенность в своих силах, а
так же привлечь родителей к участию в школьных делах своего ребёнка. Многие
родители никогда не имели возможности участвовать в каких-либо делах, не
связанных с их профессией или чисто родительской деятельностью. Родители,
вместе с детьми делают фотографии, выполняют несложные исследования по
наблюдению за выращиванием растений, погодными явлениями, помогают подбирать
информацию для теоретического обоснования проектов, помогают ребенку готовить
защиту своей работы. Работы получаются очень интересными, ведь это общий
интерес и совместный труд ребенка и родителей.

 Исследовательская работа может быть:
- фантастической (ребенок выдвигает
какую-то фантастическую гипотезу);
 - экспериментальной;
 - изобретательской;
 - теоретической.
    Исследовательская деятельность
заставляет и приучает детей работать с книгой, газетой, журналом, что в наше
время очень важно.
    Любой исследовательский проект должен
быть защищен. Для этого нужна подготовка. Подготовка к защите включает
следующие этапы.
1.Выделить из текста основные понятия и
дать им определения:
а) разъяснение посредством примера,
 б) описание,
 в) характеристика,
 г) сравнение,
 д) различие.
2.Классифицировать основные предметы,
процессы, явления и события.
3. Выявить обозначить все замеченные тобой
парадоксы.
4.Расставить по важности основные идеи.
5. Предложить сравнения и метафоры.
6. Сделать выводы и умозаключения.
7. Указать возможные пути дальнейшего
изучения проблемы.
8. Подготовить текст доклада.
9. Подготовить средства наглядного
представления доклада.

Игровые технологии
   Уровень обучения и воспитания в школе в
значительной степени определяется тем, насколько педагогический процесс
ориентирован на психологию возрастного и индивидуального развития ребенка.
В связи с этим возникает актуальность в разработках игровых технологий для
современной школы.
        Изученный в процессе игровой
деятельности материал забывается учащимися в меньшей степени и медленнее, чем
материал, при изучении которого игра не использовалась. Это объясняется, прежде
всего, тем, что в игре органически сочетается занимательность, делающая процесс
познания доступным и увлекательным для школьников, и деятельность, благодаря
участию которой в процессе обучения, усвоение знаний становится более
качественным и прочным.
      В отличие от игр вообще педагогическая
игра обладает существенным признаком — наличием четко поставленной цели
обучения и соответствующего ей педагогического результата, которые могут
быть обоснованы, выделены в ясном виде и характеризуются учебно-познавательной
направленностью.
             В развивающих играх,  в этом
заключается их главная особенность — удалось объединить один из основных
принципов обучения — от простого к сложному — с очень важным принципом
творческой деятельности — самостоятельно по способностям, когда ребенок может
подняться до «потолка» своих возможностей.
       Игровая технология строится как
целостное образование, охватывающее определенную часть учебного процесса и
объединенное общим содержанием, сюжетом, персонажем.

file_name: Современные педагогические технологии по ФГОС.docx

alt: Ролевой проект . Разработка и реализация такого проекта наиболее сложна

alt: Защита на Ученом Совете. -

alt: Презентационные умения и навыки: - навыки монологической речи; - умение уверенно держать себя во время выступления; - артистические умения; - умение использовать различные средства наглядности…


extracted_text:
Минобрнауки
россии
ФЕДЕРАЛЬНОЕ
ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО
ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
БОРИСОГЛЕБСКИЙ ФИЛИАЛ
(БФ ФГБОУ ВО «ВГУ»)
Факультет физико-математического и естественно-научного
образования
Кафедра прикладной математики, информатики, физики и
методики их преподавания
ИССЛЕДОВАТЕЛЬСКИЕ ЗАДАЧИ ТЕОРИИ ГРАФОВ В ПРОЦЕССЕ
ИЗУЧЕНИЯ ШКОЛЬНОГО КУРСА ИНФОРМАТИКИ
Курсовая работа по дисциплине Методика обучения
информатике
44.03.05 Педагогическое образование (с двумя профилями
подготовки)
Профили подготовки Математика. Информатики и информационные
технологии в образовании

Зав. кафедрой                канд. пед. наук, доцент
Елена Александровна Позднова
Обучающийся              Сергей Александрович Губаревич

Руководитель                канд. пед. наук, доцент
Любовь Владимировна Лободина

Борисоглебск 2017
Содержание
Введение. 3
Глава
1:Теория. 4
1.1
История возникновения теории графов. 4
1.2
Основные понятия теории графов. 6
1.3 Основные
теоремы теории графов. 9
1.4
Способы представления графов в компьютере. 12
1.4.1
Требования к представлению графов. 13
1.4.2
Матрица смежности. 13
1.4.3
Матрица инциденций. 13
1.4.4
Списки смежности. 14
1.4.5
Массив дуг. 14
1.5 Обзор
задач теории графов. 14
Глава 2:
Практика. 17
2.1 Общая
характеристика задачи. 17
2.2
Описание алгоритма решения задачи. 18
Заключение. 22
Список
использованной литературы.. 23

Введение
Началo теории графов как математической
дисциплины было положено Эйлером в его знаменитом рассуждении о Кенигсбергских
мостах. Однако эта статья Эйлера 1736 года была единственной в течение почти ста
лет. Интерес к проблемам теории графов возродился около середины прошлого
столетия и был сосредоточен главным образом в Англии. Имелось много причин для
такого oживления изучения графов. Естественные науки оказали свое влияние на
это благодаря исследованиям электрических цепей, моделей кристаллов и структур
молекул. Развитие формальной логики привело к изучению бинарных отношений в
форме графов. Большое число популярных головоломок подавалось формулировкам
непосредственно в терминах графов, и это приводило к пониманию, чтo многие
задачи такого рода содержат некоторое математическое ядро, важность которого выходит
за рамки конкретного вопроса. Наиболее знаменитая среди этих задач –проблема
четырех красок, впервые поставленная перед математиками Де Морганом около 50х
годов XIX века. Никакая проблема не вызывала
столь многочисленных и остроумных работ в области теории графов.
Настоящее стoлетие было свидетелем неуклонного развития теории графов,
которая за последние пятнадцать – двадцать пять лет вступила в новый период
интенсивных разработок. В этом процессе явно заметно влияние запросов новых
областей: теории игр и программирования, теории передачи сообщений,
электрических сетей и контактных цепей, а также проблем психологии и биологии.
Вследствие этогo развития предмет теории графов является настолько
обширным, что все его основные направления невозможно изложить в одной главе. В
первом главе сделан акцепт на основные пoнятия и на результаты, вызывающие
особый системaтический интерес.

Глава 1. Теория
1.1 История возникновения теории графов
Родoначальником
теории графов принято считать математика Леонарда Эйлера (1707-1783). Однако
теoрия графов многократно переоткрывалась разными авторами при решении
различных прикладных задач. [1]

Рис. 1.1. Леонард
Эйлер(1707-1783)
1.
Задача о Кенигсбергских мостах. На
рис. 1.2 представлен схематический план центральной части города Кенигсберг, включающий
два берега реки Пeргoля, два острова в ней и семь соединяющих мостов. Задача
состоит в том, чтобы обойти все четыре части суши, пройдя по каждому мосту один
раз, и вернуться в исходную точку. Эта задача была решена (показано, что
решение не существует) Эйлером в 1736 году. [1]

Рис. 1.2. Схематическое
изображение Кенигcбергских мостов
2.
Задача о трех домах и трех
колодцах. Имеется три дома и три колодца, каким-то образом расположенные на
плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы
тропинки не пересекались (рис. 1.3). Эта задача была решена (показано, что
решение не существует) Куратoвским в 1930 году. [1]

Рис. 1.3
Схематичное изображение трех домов и трех колодцев
3.
Задача о четырех красках.
Разбиение на плоскости на непересекающиеся области называется картой. Области
на карте называются соседними, если они имеют общую границу. Задача состоит в
раскрашивании карты таким образом, чтобы никакие две соседние области не были
закрашены одним цветом (рис. 1.4). С конца позапрошлого века известна гипотеза,
что для этого достаточно четырех красок. В 1976 году Aппeль и Хeйкeн
опубликовали решение задачи о четырех красках, которое базировалось на переборе
вариантов с помощью компьютера. Решение этой задачи «программным путем» явилось
прецедентом, породившим бурную дискуссию, которая отнюдь не закончена. Суть
опубликованного решения состоит в том, чтобы перебрать большое, но конечное
число (около 2000) типов потенциальных контрпримeрoв к теореме о четырех
красках и показать, что ни один случай кoнтрпримeром не является. Этот перебор
был выполнен программой примерно за тысячу часов работы суперкомпьютера.
Проверить «вручную» полученное решение невозможно – объем перебора выходит
далеко за рамки человеческих возможностей. Многие математики ставят вопрос:
можно ли считать такое «программное доказательство» действительным
доказательством? Ведь в программе могут быть ошибки… Методы формального
доказательства правильности программ не применимы к программам такой сложности,
как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок и в
данном случае вообще невозможно. Таким образом, остается уповать на
программистскую квалификацию авторов и верить, что они сделали все верно. [1]

Рис. 1.4. Схематичное
изображение задачи о четырех красках
1.2 Основные понятия теории графов
1)
Графом G(V,E)
называется совокупность двух множеств – непустого множества V(множества
вершин) и множества E двухэлементных подмножеств множества V(E –
множество ребер).
2)
Ориентированный граф – это граф, в
котором  – множество упорядоченных пар
вершин вида (x,y), где x называется началом, а y –
концом дуги. Дугу (x, y) часто записывают как .
Говорят также, что дуга ведет от вершины
x к вершине y, а вершина y
смежная с вершиной x.
3)
Если элементом множества E
может быть пара одинаковых (не различных) элементов V, то такой
элемент множества E называется петлей, а граф называется графом с
петлями.
4)
Если E является не
множеством, а набором, содержащим несколько одинаковых элементов, то эти
элементы называются кратными ребрами, а граф называется мультиграфом.
5)
Если элементами множества E
являются не обязательно двухэлементные, а любые подмножества множества V, то
такие элементы множества E называются гипердугами, а граф называется
гиперграфом.
6)
Если задана функция F : V
→ M и/или F : E → M, то
множество M называется множеством пометок, а граф называется
помеченным.
В
качестве множества пометок обычно используются буквы или целые числа. Если
функция F инъективна, то есть разные вершины (ребра) имеют
разные пометки, то граф называют нумерованным.
7)
Подграфом называется граф G′(V′,E′),
где и/или .
a)
Если V′ = V, то
G′ называется остовным подграфом G.
b)
Если ,
то граф G′ называется собственным подграфом графа G.
c)
Подграф G′(V′,E′)
называется правильным подграфом графа G(V,E),
если G′ содержит все возможные рёбра G.
8)
Степень (валентность) вершины –
это количество ребер, инцидентных этой вершине (количество смежных с ней
вершин).
9)
Маршрутом в графе называется
чередующаяся последовательность вершин и ребер ,
в которой любые два соседних элемента инциденты. [2]
a)
Если ,
то маршрут замкнут, иначе открыт.
b)
Если все ребра различны, то
маршрут называется цепью.
c)
Если все вершины (а значит, и
ребра) различны, то маршрут называется простой цепью.
d)
Замкнутая цепь называется циклом.
e)
Замкнутая простая цепь называется простым
циклом.
f)
Граф без циклов называется
ациклическим.
g)
Для орграфов цепь называется
путем, а цикл – контуром.
h)

Рис. 1.5. Маршруты, цепи, циклы
Пример
В
графе, диаграмма которого приведена на рис.1.5:
1.
v1, v3, v1, v4 – маршрут, но не цепь;
2.
v1, v3, v5, v2, v3, v4 – цепь, но не простая цепь;
3.
v1, v4, v3, v2, v5 –
простая цепь;
4.
v1, v3, v5, v2, v3, v4, v1 – цикл,
но не простой цикл;
5.
v1, v3, v4, v1 – простой цикл.
10)
Если граф имеет цикл (не
обязательно простой), содержащий все ребра графа по одному разу, то такой цикл
называется эйлеровым циклом.
11)
Если граф имеет простой цикл,
содержащий все вершины графа (по одному разу), то такой цикл называется
гамильтоновым циклом.
12)
Деревом называется связный граф
без циклов.
13)
Остовом называется дерево,
содержащее все вершины графа.
14)
Паросочетанием называется
множество ребер, в котором никакие два не смежны.
15)
Паросочетание называется
максимальным, если никакое его надмножество не является независимым.
16)
Две вершины в графе связаны, если
существует соединяющая их простая цепь.
17)
Граф, в котором все вершины
связаны, называется связным.
18)
Граф, состоящий только из
изолированных вершин, называется вполне несвязным.
19)
Длиной маршрута называется
количество ребер в нем (с повторениями).
20)
Расстоянием между вершинами u и v
называется длина кратчайшей цепи , а сама
кратчайшая цепь называется геодезической.
21)
Диаметром графа G
называется длина длиннейшей геодезической.
22)
Эксцентриситетом вершины v в
связном графе G(V,E) называется максимальное расстояние от вершины v до
других вершин графа G.
23)
Радиусом графа G
называется наименьший из эксцентриситетов вершин.
24)
Вершина v называется
центральной, если ее эксцентриситет совпадает с радиусом графа.
25)
Множество центральных вершин
называется центром графа. [2]

Рис. 1.6. Эксцентриситеты вершин и центры графов
(выделены)
1.3 Основные теоремы теории графов
Опираясь
на приведенные выше определения теории графов, приведем формулировки и
доказательства теорем, которые затем найдут свои приложения при решении задач.
Теорема 1. Удвоенная сумма степеней вершин любого графа равна числу
его ребер.
Доказательство. Пусть А1, А2, А3,
..., An – вершины данного графа, a p(A1), p(А2), ..., p(An) – степени этих вершин. Подсчитаем число ребер, сходящихся в каждой
вершине, и просуммируем эти числа. Это равносильно нахождению суммы степеней
всех вершин. При таком подсчете каждое ребро будет учтено дважды (оно ведь
всегда соединяет две вершины).
Отсюда
следует: p(A1)+p(А2)+
... +p(An)=0,5N, или
2(p(A1)+p(А2)+ ... +p(An))=N , где N — число ребер.
▪ [3]
Теорема 2. Число нечетных вершин любого графа четно.
Доказательство. Пусть a1, a2, a3, …, ak – это степени четных вершин
графа, а b1, b2, b3, …, bm – степени нечетных вершин графа. Сумма a1+a2+a3+…+ak+b1+b2+b3+…+bm ровно в два раза превышает число ребер графа.
Сумма a1+a2+a3+…+ak четная (как сумма четных чисел), тогда сумма b1+b2+b3+…+bm должна быть четной. Это возможно лишь в том случае,
если m – четное, то есть четным является и число нечетных
вершин графа. Что и требовалось доказать.
Следствие 1. Нечетное число знакомых в любой компании всегда четно.
Следствие 2. Число вершин многогранника, в которых сходится нечетное
число ребер, четно.
Следствие 3. Число всех людей, когда-либо пожавших руку другим
людям, нечетное число раз, является четным. [3]
Теорема 3. Во всяком
графе с n вершинами,
где n больше
или равно 2, всегда найдутся две или более вершины с одинаковыми степенями.
Доказательство. Если граф имеет n вершин, то каждая из них может иметь степень 0, 1, 2,
..., (n-1). Предположим,
что в некотором графе все его вершины имеют различную степень, то есть, и
покажем, что этого быть не может. Действительно, если р(А)=0, то это значит,
что А – изолированная вершина, и поэтому в графе не найдется вершины Х со
степенью р(Х)=n-1. В самом деле, эта вершина должна быть соединена с
(n-1) вершиной, в
том числе и с А, но ведь А оказалась изолированной. Следовательно, в графе,
имеющем n вершин, не могут быть одновременно вершины степени 0
и (n-1). Это значит, что из n вершин
найдутся две, имеющие одинаковые степени.▪ [3]
Теорема 4. Если в
графе с n вершинами
(n больше или
равно 2) только одна пара имеет одинаковую степень, то в этом графе всегда
найдется либо единственная изолированная вершина, либо единственная вершина,
соединенная со всеми другими.
Доказательство
данной теоремы мы опускаем. Остановимся лишь на некотором ее пояснении.
Содержание этой теоремы хорошо разъясняется задачей: группа, состоящая из n школьников,
обменивается фотографиями. В некоторый момент времени выясняется, что двое
совершили одинаковое число обменов. Доказать, что среди школьников есть либо
один еще не начинавший обмена, либо один уже завершивший его. [3]
Теорема 5. Если у
графа все простые циклы четной длины, то он не содержит ни одного цикла четной
длины.
Суть
теоремы в том, что на этом графе невозможно найти цикл (как простой, так и
непростой) нечетной длины, то есть содержащий нечетное число ребер. [3]
Теорема 6. Для того,
чтобы граф был эйлеровым, необходимо и достаточно, чтобы он был связным и все
его вершины имели четную степень. [3]
Теорема 7. Для того
чтобы на связном графе можно было бы проложить цепь АВ, содержащую все его
ребра в точности по одному разу, необходимо и достаточно, чтобы А и В были
единственными нечетными вершинами этого графа. [3]
Доказательство
этой теоремы очень интересно и характерно для теории графов. Его также следует
считать конструктивным (обратите внимание на то, как использована при этом
теорема 3.6). Для доказательства к исходному графу присоединяем ребро (А, В);
после этого все вершины графа станут четными. Этот новый граф удовлетворяет
всем условиям теоремы 3.6, и поэтому в нем можно проложить эйлеров цикл Ψ.
И если теперь в этом цикле удалить ребро (А, В), то останется искомая цепь АВ.
На
этом любопытном приеме основано доказательство следующей теоремы, которую
следует считать обобщением теоремы 7. [3]
Теорема 8. Если данный граф является связным и имеет 2k вершин
нечетной степени, то в нем можно провести k различных цепей, содержащих все его
ребра в совокупности ровно по одному разу. [3]
Теорема 9. Различных
деревьев с n перенумерованными вершинами можно построить nn-2.
По
поводу доказательства этой теоремы сделаем одно замечание. Эта теорема известна,
в основном, как вывод английского математика А. Кэли (1821—1895). Графы-деревья
издавна привлекали внимание ученых. Сегодня двоичные деревья используются не
только математиками, а и биологами, химиками, физиками и инженерами (подробнее
об этом – в параграфе 6). [3]
Теорема 10. Полный граф
с пятью вершинами не является плоским.
Доказательство. Воспользуемся формулой Эйлера: В-Р+Г=2, где В – число
вершин плоского графа, Р – число его ребер, Г – число граней. Формула Эйлера
справедлива для плоских связных графов, в которых ни один из многоугольников не
лежит внутри другого.
Эту
формулу можно доказать методом математической индукции. Это доказательство мы
опускаем. Заметим только, что формула справедлива и для пространственных
многогранников. Пусть все пять вершин графа соединены друг с другом. Замечаем,
что на графе нет ни одной грани, ограниченной только двумя ребрами. Если через φ1
обозначить число таких граней, то φ2=0. Далее рассуждаем от
противного, а именно: предположим, что исследуемый граф плоский. Это значит,
что для него верна формула Эйлера. Число вершин в данном графе В=5, число ребер
Р=10, тогда число граней Г=2-В+Р=2-5+10=7.
Это
число можно представить в виде суммы: Г=φ1+φ2+φ3+…,
где φ3 – число граней, ограниченных тремя ребрами, φ4
– число граней, ограниченных четырьмя ребрами и т. д.
С
другой стороны, каждое ребро является границей двух граней, а поэтому число
граней равно 2Р, в то же время 2Р=20=3φ3+4φ4+...
. Умножив равенство Г=7=φ3+ φ4 + φ5
+ … на три, получим ЗГ=21=3( φ3 + φ4 +
φ5 + …).
Ясно,
что (3φ3+3φ4+3φ5+…) < (3φ3+4φ4+
5φ5+…) или 3Г<2Р, но по условию, 2Р=20, а ЗГ=21;
поэтому вывод, полученный при введенном нами предположении (граф плоский),
противоречит условию. Отсюда заключаем, что полный граф с пятью вершинами не
является плоским.▪ [3]
Теорема 11. (Теорема Понтрягина-Куратовского) Граф является плоским тогда и только тогда, когда он
не имеет в качестве подграфа полного графа с пятью вершинами. [3]
1.4 Способы представления графов в компьютере
Конструирование
структур данных для представления в программе объектов математической модели –
это основа искусства практического программирования. Далее приводится четыре
различных базовых представления графов. Выбор наилучшего представления
определяется требованиями конкретной задачи. Более того, при решении конкретных
задач используются, как правило, некоторые комбинации или модификации указанных
представлений, общее число которых необозримо. Но все они так или иначе
основаны на тех базовых идеях, которые описаны в этом разделе. [4]
1.4.1 Требования к представлению графов
Известны
различные способы представления графов в памяти компьютера, которые различаются
объемом занимаемой памяти и скоростью выполнения операций над графами.
Представление выбирается, исходя из потребностей конкретной задачи. Далее
приведены четыре наиболее часто используемых представления с указанием
характеристики n(p,q) – объема памяти для каждого представления. Здесь p –
число вершин, а q – число ребер. [4]
1.4.2 Матрица смежности
Представление
графа с помощью квадратной булевой матрицы M, отражающей
смежность вершин, называется матрицей смежности, где
Для
матрицы смежности n(p,q) = O(p2).
Замечание
Матрица
смежности неориентированного графа симметрична относительно главной диагонали,
поэтому достаточно хранить только верхнюю (или нижнюю) треугольную матрицу. [4]
1.4.3 Матрица инциденций
Представление
графа с помощью матрицы H, отражающей инцидентность вершин и ребер, называется
матрицей инциденций, где для неориентированного графа

а
для орграфа

Для
матрицы инциденций n(p,q) = O(pq). [4]
1.4.4 Списки смежности
Представление
графа с помощью списочной структуры, отражающей смежность вершин и состоящей из
массива указателей на списки смежных вершин, где элемент списка представлен
структурой
N : record v : 1..p; n :↑ N end
record,
называется
списком смежности. В случае представления неориентированных графов списками
смежности n(p,q) = O(p+2q), а в случае ориентированных графов n(p,q) = O(p+q). [4]
1.4.5 Массив дуг
Представление
графа с помощью массива структур
E : array [1..q] of record b,e : 1..p end
record,
отражающего
список пар смежных вершин, называется массивом ребер (или, для орграфов,
массивом дуг). Для массива ребер (или дуг) n(p,q) = O(2q). [4]
1.5
Обзор задач теории графов
Развитие
теории графов в основном обязано большому числу всевозможных приложений.
По-видимому, из всех математических объектов графы занимают одно из первых мест
в качестве формальных моделей реальных систем.
Графы
нашли применение практически во всех отраслях научных знаний: физике, биологии,
химии, математике, истории, лингвистике, социальных науках, технике и т.п.
Наибольшей популярностью теоретико-графовые модели используются при
исследовании коммуникационных сетей, систем информатики, химических и
генетических структур, электрических цепей и других систем сетевой структуры.
Далее
перечислим некоторые типовые задачи теории графов и их приложения:
- Задача о кратчайшей цепи
 замена оборудования
 составление расписания движения транспортных средств
 размещение пунктов скорой помощи
 размещение телефонных станций
- Задача о максимальном
потоке
 анализ пропускной способности коммуникационной сети
 организация движения в динамической сети
 оптимальный подбор интенсивностей выполнения работ
 синтез двухполюсной сети с заданной структурной
надежностью
 задача о распределении работ
- Задача об упаковках и
покрытиях
 оптимизация структуры ПЗУ
 размещение диспетчерских пунктов городской
транспортной сети
- Раскраска в графах
 распределение памяти в ЭВМ
 проектирование сетей телевизионного вещания
- Связность графов и сетей
 проектирование кратчайшей коммуникационной сети
 синтез структурно-надежной сети циркуляционной связи
 анализ надежности стохастических сетей связи
- Изоморфизм графов и сетей
 структурный синтез линейных избирательных цепей
 автоматизация контроля при проектировании БИС
- Изоморфное вхождение и пересечение графов
 локализация неисправности с помощью алгоритмов поиска
МИПГ
 покрытие схемы заданным набором типовых подсхем
- Автоморфизм графов
 конструктивное перечисление структурных изомеров для
производных органических соединений
 синтез тестов цифровых устройств. [2]

Глава 2: Практика
2.1 Общая
характеристика задачи
Агентство по грузоперевозкам "Летучий
голландец" предоставляет услуги по перевозке грузов по различным
маршрутам. Дaнные o маршрутах, выполненных в течение недели, по каждому
водителю приведены на таблице 2.1.
Таблица 2.1. Данные о
маршрутах

Сведения о выполненных маршрутах

№ п/п

ФИО водителя

Марка автомобиля

№ рейса

Выполнено рейсов, шт.

Протяженность рейса, км.

Расход топлива на 100
   км, л

Израсходовано топлива, л

Грузоподъемность, т

Вес перевезенного груза, т

1

Соловьев В.В.

КАМАЗ

А112

4

2

Михайлов С.С.

ЗИЛ

С431

3

3

Кузнецов Я.Я.

МАЗ

А112

5

4

Иванов К.К.

МАЗ

М023

7

5

Сидоров А.А.

ЗИЛ

В447

2

6

Волков Д.Д.

КАМАЗ

С431

8

7

Быков Л.Л.

КАМАЗ

В447

4

ИТОГО

Х

Х

В СРЕДНЕМ

Х

Х

Справочные
данные o технических характеристиках автомобилей и протяженности маршрутов
представлены на  таблице 2.1.

Технические
  характеристики

№ п/п

Марка автомобиля

Расход топлива на 100
   км, л

Грузоподъем-ность, т

1

ЗИЛ

42

7

2

КАМАЗ

45

16

3

МАЗ

53

12

Таблица 2.2.
Данные о технических характеристиках автомобилей и протяженности маршрутов

Протяженность

№п/п

№ рейса

Протяженность

1

А112

420

2

В447

310

3

М023

225

4

С431

250

1. Построить таблицы по приведенным выше данным.
2.Выполнить расчет количества израсходованного топлива
каждым водителем и веса перевезенного груза, данные расчета занести в таблицу.
3. Организовать межтабличные связи для автоматического
формирования ведомости расхода топлива за неделю.
4. Сформировать и заполнить ведомость расхода топлива
каждым водителем за неделю.
5. Результаты расчета количества израсходованного
топлива за неделю представить в графическом виде. [5]
2.2 Описание
алгоритма решения задачи
1.
Запустить табличный процессор МS Excel.
2.
Создать книгу с именем “Летучий
голландец”.
3.
Лист 1 переименовать в лист с
названием Сведения.
4.
На рабочем листе Сведения создать
таблицу Сведения о выполненных маршрутах (табл. 2.3).
5.
Заполнить таблицу Сведения о
выполненных маршрутах.
6.
Лист 2 переименовать в лист
Характеристики.
7.
На рабочем листе Характеристики
создать таблицу, в которой будут содержаться технические характеристики
автомобилей (табл. 2.4).
8.
Заполнить таблицу со списком
Технических характеристик автомобилей.
9.
Лист 3 переименовать в лист
Протяженность.
10.
На рабочем листе Протяженность,
создать таблицу протяженности рейсов (табл. 2.5).
11.
Заполнить таблицу Протяженность
рейсов исходными данными.
12.
Лист 4 переименовать в Ведомость
(табл. 2.6).
13.
На рабочем листе Ведомость создать
таблицу Ведомость расхода топлива.
14.
Лист 5 переименовать в лист График
(табл. 2.7).
15.
На рабочем листе График создать
график учета расхода топлива на каждого водителя.
16.
Заполнить графу Израсходовано
топливо таблицы “Сведения о выполненных маршрутах” находящейся на листе
Сведения следующим образом:
Занести
в ячейку H3 формулу: =СУММ(F3*G3/100).
Размножить
введенную в ячейку Н3 формулу для остальных ячеек (с Н4 по Н7) данной графы,
соответственно меняя строки F3, G3 на соответствующие строкам в столбце Н.
Таким
образом, будет выполнен автоматический подсчет израсходованного топлива.
17.
Заполнить графу Вес перевезенного
груза таблицы “Сведения о выполненных маршрутах” находящейся на листе Сведения
следующим образом:
Занести
в ячейку J3 формулу: =СУММ(I3*E3).
Размножить
введенную в ячейку J3 формулу для остальных ячеек (с J4 по
J7) данной графы, соответственно меняя строки I3, E3 на
соответствующие строкам в столбце J.
Таким
образом, будет выполнен автоматический подсчет суммы перевезенного груза.
18.
На листе Ведомость заполнить графу
Израсходовано топлива следующим образом:
Занести
в ячейку Е12 формулу: =СУММ(Сведения!H3).
Размножить
введенную в ячейку Е12 формулу для остальных ячеек (с Е12 по Е18) данной графы,
соответственно меняя строки формулы с Н3 по Н9.
Таким
образом, будет выполнен автоматический подсчет израсходованного топлива.
19.
На листе Ведомость заполнить графу
Выполнено рейсов следующим образом:
Занести
в ячейку D12 формулу =СУММ(Сведения!E3).
Размножить
введенную в ячейку D12 формулу для остальных ячеек (с D13
по D18) данной графы, соответственно меняя строки формулы
с Е3 по Е9.
Таким
образом, будет выполнен автоматический подсчет количества выполненных рейсов.
20.
Пo результатам заполненных параметров в таблице «Ведомость расхода топлива»
создать график расхода топлива на листе «график».
Таблица 2.3. Сведения о выполненных маршрутах

Сведения о
  выполненных маршрутах

№ п/п

ФИО водителя

Марка автомобиля

№ рейса

Выполнено рейсов,шт.

Протяженность
  рейсов,км

Расход топлива
  на 100км,л

Израсходовано
  топлива,л

Грузоподъемность,т

Вес
  перевезенного груза,т

1

Соловьев В.В.

КАМАЗ

А112

4

420

45

189

16

64

2

Михайлов С.С.

ЗИЛ

С431

3

250

42

105

7

21

3

Кузнецов Я.Я.

МАЗ

А112

5

42

53

222,6

12

60

4

Иванов К.К.

МАЗ

М023

7

225

53

119,25

12

84

5

Сидоров А.А.

ЗИЛ

В447

2

310

42

130,2

7

14

6

Волков Д.Д.

КАМАЗ

С431

8

250

45

112,5

16

128

7

Быков Л.Л.

КАМАЗ

В447

4

310

45

139,5

16

64

ИТОГО

33

2185

325

1018,05

86

435

В СРЕДНЕМ

4,71

312,14

46,43

145,44

12,29

62,14

Таблица 2.4. Технические
характеристики автомобилей

Технические характеристики автомобилей

№ п/п

Марка
  автомобиля

Расход топлива
  на 100 км, л

Грузоподъемность,
  т

1

ЗИЛ

42

7

2

КАМАЗ

45

16

3

МАЗ

53

12

Таблица 2.5.  Протяженность
рейсов

Протяженность рейсов

№ п/п

№ рейса

Протяженность
  рейса, км

1

А112

420

2

В447

310

3

М023

225

4

С431

250

Таблица 2.6. Ведомость

ФИО водителя

№ рейса

Выполнено рейсов, шт

Израсходовано топлива, л

Соловьев В.В.

А112

4

189

Михайлов С.С.

С431

3

105

Кузнецов Я.Я.

А112

5

222,6

Иванов К.К.

М023

7

119,25

Сидоров А.А.

В447

2

130,2

Волков Д.Д.

С431

8

112,5

Быков Л.Л.

В447

4

139,5

ИТОГО

33

1018,05

Таблица 2.7. График

 Данная задача решена в приложении Microsoft Office Excel.

Заключение
В
работе были рассмотрены задачи из теории графов, которые уже стали
классическими. Особенно часто в практическом программировании возникают вопросы
о построении кратчайшего остова графа и нахождении максимального паросочетания.
Известно также, что задача о нахождении гамильтонова цикла принадлежит к числу NP-полных,
т.е. эффективный алгоритм для ее решения не найден. Таким образом, задачи
теории графов актуальны, так как могут принести экономию времени и средств на
производстве и в быту. Теория графов находит широкое применение в различных
областях науки и техники: в частности в информатике.
Двоичные
деревья играют весьма важную роль в теории информации. Предположим, что
определенное число сообщений требуется закодировать в виде конечных
последовательностей различной длины, состоящих из нулей и единиц. Если
вероятности кодовых слов заданы, то наилучшим считается код, в котором средняя
длина слов минимальна по сравнению с прочими распределениями вероятности.
Задачу о построении такого оптимального кода позволяет решить алгоритм
Хаффмана.
Двоичные
кодовые деревья допускают интерпретацию в рамках теории поиска. Каждой вершине
при этом сопоставляется вопрос, ответить на который можно либо "да",
либо "нет". Утвердительному и отрицательному ответу соответствуют два
ребра, выходящие из вершины. "Опрос" завершается, когда удается
установить то, что требовалось.
Таким
образом, если кому-то понадобится взять интервью у различных людей, и ответ на
очередной вопрос будет зависеть от заранее неизвестного ответа на предыдущий
вопрос, то план такого интервью можно представить в виде двоичного дерева.

Список использованной литературы
1.
История возникновения теории
графов. Историческая справка. – URL: https://sites.google.com/site/teoriagrafov96/
(дата обращения: 10.11.2016)
2.
Некоторые задачи теории графов.
Базовые понятия теории графов. – URL: http://www.bourabai.kz/dm/graph.htm#5 (дата
обращения: 15.01.2017)
3.
Основные теоремы теории графов. – URL: http://mirznanii.com/a/312693/teoriya-grafov
(дата обращения: 25.12.2016)
4.
Требования к представлению графов.
– URL: http://www.studfiles.ru/preview/2619537/page:14/
(дата обращения: 12.02.2017)
5.
Разбор и решение задач. – URL: http://filling-form.ru/turizm/3077/index.html?page=22
(дата обращения: 15.01.2017)

Скачано с www.znanio.ru

file_name: Курсовая работа (Губаревич Сергей).doc

alt: Минобрнауки россии ФЕДЕРАЛЬНОЕ

alt: Содержание Введение . 3 Глава 1:Теория

alt: Введение Начал o теории графов как математической дисциплины было положено

alt: Куратoвским в 1930 году. [ 1]

alt: Если V ′ = V , то G ′ называется остовным подграфом

alt: Следствие 1 . Нечетное число знакомых в любой компании всегда четно

alt: Доказательство . Воспользуемся формулой

alt: Для матрицы инциденций n ( p , q ) =

alt: конструктивное перечисление структурных изомеров для производных органических соединений синтез тестов цифровых устройств . [2]

alt: Таблица 2.6. Ведомость

alt: Список использованной литературы 1

информатика

group: Дисциплины


extracted_text:
Инструкция
по охране труда при работе в кабинете информатики

1.
  Общие требования безопасности

1.1. К работе в кабинете информатики допускаются учащиеся с
  1-го класса, прошедшие инструктаж по охране труда, медицинский осмотр и не
  имеющие противопоказаний по состоянию здоровья.
  1.2. При работе в кабинете информатики учащиеся должны соблюдать правила
  поведения, расписание учебных занятий, установленные режимы труда и отдыха.
  1.3. При работе в кабинете информатики возможно воздействие на учащихся
  следующих опасных и вредных производственных факторов:
  - неблагоприятное воздействие на организм человека неионизирующих
  электромагнитных излучений видеотерминалов;
  - неблагоприятное воздействие на зрение визуальных эргономических параметров
  видеотерминалов, выходящих за пределы оптимального диапазона;
  - поражение электрическим током.
  l.4. Кабинет информатики должен быть укомплектован медицинской аптечкой с
  набором необходимых медикаментов и перевязочных средств для оказания первой
  помощи при травмах или при плохом самочувствии.
  1.5. При работе в кабинете информатики соблюдать правила пожарной
  безопасности, знать места расположения первичных средств пожаротушения.
  Кабинет информатики должен быть оснащен двумя углекислотными огнетушителями.
  1.6. О каждом несчастном случае пострадавший или очевидец несчастного случая
  обязан немедленно сообщить учителю (преподавателю). При неисправности
  оборудования прекратить работу и сообщить об этом учителю (преподавателю).
  1.7. В процессе работы с видеотерминалами учащиеся должны соблюдать порядок
  проведения работ, правила личной гигиены, содержать в чистоте рабочее место.
  1.8. Учащиеся, допустившие невыполнение или нарушение инструкции по охране
  труда, привлекаются к ответственности, и со всеми учащимися проводится
  внеплановый инструктаж по охране труда.
2.
  Требования безопасности перед началом работы

2.1.
  Тщательно проветрить кабинет информатики и убедиться, что температура воздуха
  в кабинете находится в пределах 19 — 21' С, относительная влажность воздуха в
  пределах 62 — 55%.
  2.2. Убедиться в наличии защитного заземления оборудования, а также защитных
  экранов видеотерминалов.
  2.3. Включить видеотерминалы и проверить стабильность и четкость изображения
  на экранах.

3. Требования безопасности во время работы

3.1. Не включать видеотерминалы без разрешения учителя
  (преподавателя).
  3.2. Недопустимы занятия за одним видеотерминалом двух и более человек.
  3.3. При работающем видеотерминале расстояние от глаз до экрана должно быть
  0,6 — 0,7 м, уровень глаз должен приходиться на центр экрана или на 2/3 его
  высоты.
  3.4. Тетрадь для записей располагать на подставке с наклоном 12—I50 на
  расстоянии 55 — 65 см от глаз, которая должна быть хорошо освещена.
  3.5. Изображение на экранах видеотерминалов должно быть стабильным, ясным и
  предельно четким, не иметь мерцаний символов и фона, на экранах не должно
  быть бликов и отражений светильников, окон и окружающих предметов.
  3.6. Длительность работы с видеотерминалами не должно превышать: для учащихся
  1-х классов (6 лет) — 10 мин., для учащихся 2-5 классов — 15 мин., для
  учащихся 6-7 классов — 20 мин., для учащихся 1-9 классов — 25 мин., для
  учащихся 10-11 классов — при двух уроках подряд на первом из них — 30 мин.,
  на втором — 20 мин., после чего сделать перерыв не менее 10 мин. для
  выполнения специальных упражнений, снимающих зрительное утомление.
  3.7. Во время производственной практики ежедневная длительность работы за
  видеотерминалами не должна превышать 3-х часов для учащихся старше 16 лет и
  2-х часов для учащихся моложе 16 лет с обязательным проведением гимнастики
  для глаз через каждые 20 — 25 мин. работы и физических упражнений через
  каждые 45 мин. во время перерывов.
  3.8. Занятия в кружках с использованием видеотерминалов должны проводиться не
  раньше, чем через 1 час после окончания учебных занятий в школе, не чаще 2-х
  раз в неделю общей продолжительностью; для учащихся 2-5 классов — не более 60
  мин., для учащихся 6-х классов и старше — до 90 мин.
  3.9. Не рекомендуется использовать в кабинете для написания информации
  меловую доску.

  4. Требования безопасности в аварийных ситуациях

4.1. В случае появления неисправности в работе видеотерминала
  следует выключить его и сообщить об этом учителю (преподавателю).
  4.2. При плохом самочувствии, появлении головной боли, головокружения и пр.
  прекратить работу и сообщить об этом учителю (преподавателю).
  4.3. При поражении электрическим током немедленно отключить видеотерминалы,
  оказать первую помощь пострадавшему, при необходимости отправить его в
  ближайшее лечебное учреждение и сообщить об этом администрации учреждения.

5. Требования безопасности по окончании работы

5.1. С разрешения учителя (преподавателя) выключить
  видеотерминалы и привести в порядок рабочее место.
  5.2. Тщательно проветрить и провести влажную уборку кабинета информатики.

file_name: Инструкция по охране труда при работе в кабинете информатики.doc


extracted_text:
МБДОУ «Детский сад №44
«Красная Шапочка»

Конспект
интегрированного занятия в старшей группе с использованием игровой технологии
интеллектуально – творческого развития воспитанников
«Путешествие Муравьишки Кузи»

Воспитатель: Баранова М.В.

Цель: обогащение
представлений детей о жизни насекомых и развитие логического мышления.
Задачи:
-
закрепить знание состава числа первого десятка, умение составлять число из двух
меньших чисел;
-
закреплять знание цифр;
-
развивать навыки решения логико - арифметических задач на сложение пределах 10;
-
развивать умение измерять величину с помощью условной мерки;
-
воспитание доброго отношения к маленьким соседям по планете;
-
развивать логическое мышление детей; умение находить закономерность и
продолжать её;
-
развивать внимание детей, умение строить симметричные линии;
-
развивать социальные навыки детей: умение работать в команде.
Материал
и оборудование: «Шнур – малыш» и «Геовизор» на каждого ребёнка; листы формата А4,
с изображением реки на каждого ребёнка; линейки и простые карандаши на каждого
ребёнка; логические таблицы и элементы для дополнения таблиц на каждого
ребёнка; презентация (видеофильм «Пение птиц»); презентация (видеофильм
«Муравьи – друзья леса»); ИКТ; картинка муравьишки; кочки, дорожки, подлезалки
– для проведения физкультминутки.
Предварительная
работа: рассматривание картинок и иллюстраций на тему «Насекомые», беседы
о насекомых, загадки о насекомых, просмотр фильма «Муравей – красная точка».

Ход
занятия
Часть
1
Воспитатель: Ребята,
я приглашаю вас в путешествие по весеннему лесу полюбоваться распустившейся
листвой, послушать щебетание птиц.
Презентация
«Пение птиц».
Воспитатель:А как
нужно вести себя в лесу?
Дети: Не
оставлять в лесу мусор, не пугать птиц и животных громкими звуками, не разорять
птичьи гнёзда, не обижать лесных насекомых, не рвать редкие цветы, не разводить
костёр, в лес ходить только со взрослыми,…
Воспитатель: Кроме
птиц, животных, растений проснулись ещё кто-то…
….насекомые.
И я хочу рассказать вам сказку об одном любопытном муравьишке.
Под
старой березой муравьи сделали большой муравейник. Жили они в нем дружно,
каждый выполнял свою работу, никто не ленился. Был среди муравьев один
очень-очень любознательный. Звали его Кузя. Этот Кузя не только работать
успевал, но еще и любопытствовал обо всём вокруг.
Однажды
Кузя решил посмотреть, как далеко видно со старой березы. Быстро побежал он
вверх по стволу, уселся на березовый листок и поглядел по сторонам. Но тут
налетел летний ветерок, лист сорвался с березы и полетел по воздуху, унося Кузю
далеко от муравейника.
Кузя
знал, что с наступлением темноты, как только солнцезайдёт за горизонт, все
входы в муравейник будут закрыты. А оставаться одному ночью в лесу очень опасно
для маленького муравьишки.
Заспешил
Кузя домой. Ветерок принес его на большой луг. Поднялся Кузя на высокую
травинку и увидел вдалеке верхушку своей берёзы. К ней и надо спешить.
Воспитатель:Но что
же делать? Как быть? Кто поможет Кузе?
Дети: Мы
поможем муравьишке.
Часть
2
Воспитатель:Раз мы
готовы помочь, то садитесь за столы и разомнём пальчики.
Физкультминутка
«Муравейник на поляне».
Муравейник
на поляне ночью крепко спит.
А, как
солнце заиграет, муравьишки выбегают:
Лапками
перебирают, и головками качают.
Муравьишек
ровно 5: 1-2-3-4-5!
Очень
дружные они!
Ты,
дружок, их береги.
Воспитатель: Молодцы,
размяли пальчики, а теперь возьмите «Шнур – малыш». Поможем муравьишке
перебраться через луг, укажем ему верный путь.
Приготовились!
- шнур
выныривает из 2 кнопочки 1 ряда;
-
далее закручивается вокруг 3 кнопочки 1 ряда;
-
затем закручивается вокруг 1 кнопочки 2 ряда;
-
далее закручивается вокруг 3 кнопочки второго ряда;
-
затем шнурочек закручивается вокруг 3 кнопочки 3 ряда;
- и
ныряет в 1 кнопочку 3 ряда.
Покажите
мне какая получилась дорожка, которую должен пройти Кузя.
Воспитатель: Молодцы,
все верно проложили путь, помогли Кузе. Отложите Шнур в сторону, а мы двигаемся
дальше.
Часть
3
Воспитатель:Пройдя
через луг, наш Кузя попал на берег реки. Как переправиться через реку? Кузя
попросил о помощи жука-плавунца. А жук ему сказал: «Я смогу перевезти тебя на
спине через
реку.
Но я должен точно знать ее ширину в самом узком и в самом
широком
месте, чтобы правильно рассчитать свои силы. Иначе
мы оба
погибнем».
Вот
перед нами река. Вы должны определить, где у речки самое узкое и самое широкое
место. Какможно измерить ее ширину? Правильно, с помощь линейки.
Возьмите
в руки линейку. Сначала измерьте самое узкое место. Вспомните, как правильно
прикладывать линейку, как увидеть результат измерения. Карандашом запишите в
клеточке результат своего измерения. А теперь измерьте самое широкое место.
Также запишите результат измерения. Сравните полученные результаты и скажите
где самое узкое место реки, выделите его красным цветом. Где муравьишке с
помощью жука-плавунца можно переправиться через речку. Молодцы!
Часть
4
Речка
позади. Но солнышко всё ниже, ночь всё ближе. Изо
всех
сил бежал Кузя, устал, выбился из сил. Присел на кочку,
отдышаться
не может. А неподалёку собралась пестрая компания божьих коровок - о чем-то
громко спорят, ссорятся.
Оказывается,
построили они себе дом. В домике 9 квартир.
8 уже
заселены, одна еще свободна. А желающих в нее поселиться - целых 6. Как же
быть? Попросили божьи коровки Кузю рассудить по справедливости, кому достанется
квартирка.
Воспитатель: «Я
раздаю каждому домик, в котором 8 квартир уже
заселены.
Предлагаю вам еще 6 божьих коровок, которые хотят
занять
пустую клетку в таблице - свободную квартиру. Подумайте и решите, какая из них
поселится в ней?»
Воспитатель
может предложить детям подсказки: закономерности заключаются в строках таблицы.
Сначала нужно внимательно рассмотреть букашек в верхней строке таблицы,
пересчитать
пятнышки
у них на крылышках. Какую закономерность заметили
дети?
Пятнышек у всех божьих коровок по 6, а распределены они
так: у
первой букашки - 2 и 4, у второй - 1 и 6, у третьей - 3 й 3.
Соблюдается
ли эта закономерность во второй строке? Да.
У
букашек во второй строке по 5 пятнышек на крыльях: 2 и 3,
1 и
4,0 и 5.
В
третьей строке у двух божьих коровок по 4 пятнышка:
1 и
3,0 и 4. Значит, у недостающей божьей коровки должно быть
4
пятнышка. Вспоминая состав числа 4, дети приходят к выводу,
что
пятен должно быть по 2 на каждом крылышке.
Воспитатель: Ребята,
вот вы и помогли божьим коровкам, рассудили, кому же заселяться в эту квартиру.
Часть
5
Воспитатель: А я
вам предлагаю отправиться с Кузей дальше.
Физкультминутка:
«Муравей
нашел былинку
Много
было с ней хлопот
Как
бревно взвалил на спинку
Он домой
ее несет
Он сгибается
под ношей
Он ползет
уже с трудом
Но зато
какой хороший
Муравьи
возводят дом».
Воспитатель:Молодцы,
прошли преграды!
Часть
6
Воспитатель:Дошёл
Кузя до цветочной полянки и вдруг увидел, что на одномцветке уже устроилась на
ночлег бабочка. «Осталось недалеко, - подумал Кузя, - если я сумею разбудить
бабочку, она мигом
домчит
меня до моей березы».
Кузя
стал тормошить бабочку, но та не хотела расправлять
свои
крылышки.
Воспитатель:Ребята,
я предлагаю вам помочь Кузе и нарисовать с помощью геовизора бабочку.
Взяли
в правую руку карандаш и отмечаем заданные точки:
-
Отмечаем Б1, Ф4, С3, центральная точка. Открываем геовизор, соединяем
отмеченные точки. Закрываем и отмечаем дальше.
- С1,
Г3, З1, центральная точка. Открываем геовизор, соединяем отмеченные точки.
Закрываем и отмечаем дальше.
-
Перед нами половинка бабочки, а правую половинку вы должны самостоятельно
отметить и дорисовать бабочку. Не забывайте, что крылышки левое и правое должны
быть одинаковы. Будьте внимательны.
Воспитатель: Вот
наша бабочка расправила свои крылышки, посадила к себе на спину муравьишку и
они полетели.
Часть
7
-
Бабочка принесла нашего Кузю на берёзу. Смотрит он сверху - почти все дверки в
муравейнике уже закрылись. Не успеть ему спуститься! И тут ему на помощь пришла
гусеница, которая устроилась на ночлег под березовым листком.
Вы
знаете, что гусеницы превращаются в куколок, а потом из куколки появляются
разные насекомые - бабочки, стрекозы, мухи. Чтобы стать куколкой, гусеница
опутывает себя тонкой нитью. А откуда ж она ее берет? Сама делает - выпускает
нитку из малюсенького отверстия в своем брюшке.
Ухватился
Кузя за гусеницу. Наша гусеница зацепила один конец нити за ветку и стала
спускаться. Быстро разматывается нить - быстро спускается гусеница, а с ней и
Кузя.
А
бабочка, улетая, сказала гусенице: «Ты тоже скоро станешь бабочкой. Это
произойдёт через неделю и еще три дня».
Воспитатель: Ребята,
давайте подскажем гусенице, через сколько дней она превратится в бабочку?»
Дети:Через
десять.
Воспитатель: Правильно,
через 10, так как в неделе 7 дней, да ещё 3, то получиться 10.
Часть
8
Воспитатель: Вот
Кузя и в муравейнике. Он еле успел заскочить внутрь. Его друзья-муравьи уже
закрыли почти все дверки, кроме одной.
А
сейчас я предлагаю посмотреть вам видеофильм «Муравьи – друзья леса»и увидеть
жизнь муравья в природе.
Видеофильм
«Муравьи – друзья леса».
Часть
9
Воспитатель: Вот и
подошло к концу наше путешествие. Кому же мы с вами помогали сегодня? Было
трудно?
Молодцы!
Я желаю вам чаще бывать, ведь лес хорош не только весной, но и в любое другое
время года, но стараться не наносить вред лесу и его жителям!

file_name: конспект игровые технологии.docx

alt: МБДОУ «Детский сад №44 «Красная

alt: Воспитатель: Вот Кузя и в муравейнике