Методическте указания по выполненю самостоятельной работы МДК.01.02 Математический аппарат для построения компьютерных сетей

Министерство образования, науки и молодёжи

Республики Крым

Государственное бюджетное профессиональное образовательное учреждение Республики Крым

«Симферопольский автотранспортный техникум»

УТВЕРЖДАЮ

Заместитель директора

по учебной работе

_____________

«_______»___________2017 г.

Методические указания
по выполненю САМОСТОЯТЕЛЬНОЙ работы

МДК.01.02 Математический аппарат для построения компьютерных сетей

Симферополь, 2017

Методические указания содержат рекомендации по выполнению внеаудиторных самостоятельных работ по междисциплинарному курсу МДК 01. 02. «Математический аппарат для построения компьютерных сетей» профессионального модуля ПМ 01. Участие в проектировании сетевой инфраструктуры.

Методические указания составлены в соответствии с рабочей программой и предназначены для обучающихся по специальности 09.02.02 Компьютерные сети (по программе углубленной подготовки)

Организация-разработчик:

Симферопольский автотранспортный техникум (САТТ)

Разработчик:

Безменова Е.Ю., преподаватель математики, высшая квалификационная категория

^{Ф.И.О., ученая степень, звание, должность,}

Рассмотрены на заседании цикловой комиссии математического и общего естественнонаучного цикла.

Протокол №___ от «___» ________ 2017г.

Председатель цикловой комиссии

_____________________

ОГЛАВЛЕНИЕ

Введение…………………………………………………………………………………….. Пояснительная записка…………………………………………………………....................	4 4
Объем МДК и виды учебной работы……………………………………………………….	6
Перечень внеаудиторной самостоятельной работы………………………………………..	6
Организация самостоятельной работы и контроль за качеством её выполнения……….	7
Методические рекомендации по выполнению реферата………………………………….	7
Методические указания по подготовке к практическим занятиям……………………….	9
Методические указания по подготовке презентации	9
Тематика и задания самостоятельной работы……………………………………………...	12
Литература и интернет-ресурсы …………………………………	20

Введение

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

Самостоятельная работа проводится с целью:

- систематизации и закрепления полученных теоретических знаний и практических умений обучающихся;

- углубления и расширения теоретических знаний;

- формирования умений использовать справочную документацию, специальную литературу, Интернет;

- развития познавательных способностей и активности обучающихся: творческой инициативы, самостоятельности, ответственности, организованности;

- формирование самостоятельности мышления, способностей к саморазвитию, совершенствованию и самоорганизации;

- формирования общих и профессиональных компетенций

- развитию исследовательских умений.

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

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

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

Выполнение самостоятельной внеаудиторной работы по МДК 01.02. «Математический аппарат для построения компьютерных сетей» направлено формирование у студентов системы знаний, практических умений, необходимых для профессиональной деятельности .

Цели и задачи МДК – требования к результатам освоения МДК:

В результате освоения междисциплинарного курса обучающийся должен

уметь:

• использовать современные информационные технологии и инструментальные средства для решения различных задач в своей профессиональной деятельности;

• применять алгоритмы поиска кратчайшего пути;

• использовать математический аппарат теории графов.

В результате освоения междисциплинарного курса обучающийся должен

знать:

• основные понятия теории вероятностей и математической статистики;

• элементы теории автоматов;

• основные понятия теории графов;

• алгоритмы поиска кратчайшего пути;

• элементы теории массового обслуживания.

Критерии оценки результатов самостоятельной работы

Критериями оценки результатов внеаудиторной самостоятельной работы обучающихся являются:

• уровень освоения  учебного материала;

• уровень умения  использовать теоретические знания при выполнении практических задач;

• уровень сформированности общепрофессиональных умений;

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

• обоснованность и четкость изложения материала;

• уровень умения ориентироваться в потоке информации, выделять главное;

• уровень умения четко сформулировать проблему, предложив ее решение, критически оценить решение и его последствия;

• уровень умения определить, проанализировать альтернативные возможности, варианты действий;

• уровень умения сформулировать собственную позицию, оценку и аргументировать ее.

Объем МДК и виды учебной работы

Объем междисциплинарного курса МДК 01.02. «Математический аппарат для построения компьютерных сетей» и виды учебной работы приведены в таблице 1.

Таблица 1.

Вид учебной работы	Объем часов
Всего часов (макс. учебная)	86
Обязательная аудиторная учебная нагрузка (всего)	63
в том числе:
- лабораторные работы и практические занятия
Самостоятельная работа обучающегося (всего)	20
в том числе: Подготовка к практическим занятиям с использованием методических рекомендаций преподавателя, подготовка к их защите	6
Подготовка реферата	4
Составление презентации	2
Выполнение расчетных задач	8
Промежуточная аттестация в форме дифференцированного зачета

Перечень внеаудиторной самостоятельной работы

Перечень внеаудиторной самостоятельной работы для учащихся по специальности 09.02.02 Компьютерные сети (по программе углубленной подготовки) по МДК 01.02. Математический аппарат для построения компьютерных сетей представлен в таблице 2.

Таблица2.

Наименование разделов, тем УД	Вид внеаудиторной самостоятельной работы	Количество часов на внеаудиторную самостоятельную работу (ВСР)
1	2	3
Раздел 1. Основные теории вероятностей и математической статистики	Подготовка к практическим занятиям с использованием методических рекомендаций преподавателя, подготовка к их защите	4
	Выполнение расчетного задания	4
Раздел 2. Элементы теории автоматов	Составление презентации	2
Раздел 3. Основы теории графов	Подготовка к практическим занятиям с использованием методических рекомендаций преподавателя, подготовка к их защите	1
	Подготовка реферата	4
	Выполнение расчетного задания	4
Раздел 4. Основы теории массового обслуживания	Подготовка к практическим занятиям с использованием методических рекомендаций преподавателя, подготовка к их защите	1
Всего			20

Организация самостоятельной работы и контроль

за качеством её выполнения

Основными задачами преподавателя при организации самостоятельной работы обучающихся по МДК являются:

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

• оказание им необходимой индивидуальной и групповой консультативной помощи;

• осуществление контроля за качеством выполнения самостоятельной работы.

Методические рекомендации по выполнению реферата

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

Реферат (от латинского слова refero – сообщаю) – краткое изложение в письменном виде или в форме доклада содержания научного труда, литературы по теме.

Изложение материала происходит в основном своими словами (т.е. основные мысли автора текста пересказываются автором реферата, причем некоторые положения могут приводиться в виде цитат, тех или иных цифровых данных, схем, таблиц и т.п.)

Требования к реферату

Реферат должен удовлетворять следующим требованиям:

• правильно отражать основное содержание реферируемого материала или научной темы;

• изложение основных вопросов должно быть сжатым;

• изложение должно вестись в порядке развертывания основных действий, вопросов, фактов;

• содержать критические замечания и собственные выводы;

• оформление - согласно предъявляемым требованиям.

Этапы работы над рефератом

Первый этап – уяснение содержания темы и целевых установок. На основе этого нужно наметить главные вопросы, подлежащие рассмотрению, и их краткое содержание.

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

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

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

Четвертый этап – включает подбор соответствующей литературы, интернет - ссылок. В этом деле целесообразно пользоваться каталогами библиотеки.

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

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

Полезно мысленно делить прочитанное на части, отмечая основные, важные моменты. Проведя, таким образом, анализ и синтез прочитанного, студент сможет глубоко понять содержание темы.

Структура реферата

1.Титульный лист.

2.Оглавление – излагается название составляющих реферата, указываются страницы.

3.Введение – формулируется суть исследуемой проблемы ее актуальность, обосновывается выбор темы. Указывается цель и задачи. Показывается научный интерес и практическое значение. Объем введения составляет 2-3 страницы.

4.Основная часть – доказательно раскрывается проблема или одна из ее сторон; могут быть представлены таблицы, графики, схемы. диаграммы. Основная часть должна включать в себя также собственное мнение студента.

5.Заключение – подводятся итоги или дается обобщенный вывод по теме реферата, указывается, что интересно, что спорно, предлагаются рекомендации.

Объем заключения 2–3 страницы.

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

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

Выступление по реферату.

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

Оформление реферата

При выполнении внеаудиторной самостоятельной работы в виде реферата необходимо соблюдать следующие требования:

• на одной стороне листа белой бумаги формата А-4

• размер шрифта-12; Times New Roman, цвет - черный

• междустрочный интервал – 1,5.

• поля на странице – размер левого поля – 2 см, правого – 1 см, верхнего – 2см, нижнего – 2см.

• отформатировано по ширине листа

• на первой странице необходимо изложить план (содержание) работы.

• в конце работы необходимо указать источники использованной литературы

Критерии оценки реферата

Срок сдачи готового реферата определяется утвержденным графиком.

В случае отрицательного заключения преподавателя учащийся обязан доработать или переработать реферат. Срок доработки реферата устанавливается руководителем с учетом сущности замечаний и объема необходимой доработки.

Реферат оценивается по системе:

Оценка «отлично» выставляется за реферат, который носит исследовательский характер, содержит грамотно изложенный материал, с соответствующими обоснованными выводами.

Оценка «хорошо» выставляется за грамотно выполненный во всех отношениях реферат при наличии небольших недочетов в его содержании или оформлении.

Оценка «удовлетворительно» выставляется за реферат, который удовлетворяет всем предъявляемым требованиям, но отличается поверхностью, в нем просматривается непоследовательность изложения материала, представлены необоснованные выводы.

Методические указания по подготовке к практическим занятиям

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

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

На практических занятиях используются такие методы как: обсуждение прикладных вопросов темы; разрешение задач-казусов; устные ответы на контрольные вопросы; выполнение письменных заданий.

Для успешного решения задач студентам необходимо уяснить изложенную в задаче ситуацию и на основе всестороннего анализа задачи решить практические задачи. Решения должны быть представлены в письменной форме. Ответы на контрольные вопросы также предоставляются письменно.

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

Методические указания по подготовке презентации

В оформлении презентаций выделяют два блока: оформление слайдов и представление информации на них. Для создания качественной презентации необходимо соблюдать ряд требований, предъявляемых к оформлению данных блоков.

Оформление слайдов:

Стиль	· Соблюдайте единый стиль оформления · Избегайте стилей, которые будут отвлекать от самой презентации. · Вспомогательная информация (управляющие кнопки) не должны преобладать над основной информацией (текстом, иллюстрациями).
Фон	Для фона предпочтительны холодные тона
Использование цвета	· На одном слайде рекомендуется использовать не более трех цветов: один для фона, один для заголовка, один для текста. · Для фона и текста используйте контрастные цвета. · Обратите внимание на цвет гиперссылок (до и после использования).
Анимационные эффекты	· Используйте возможности компьютерной анимации для представления информации на слайде. · Не стоит злоупотреблять различными анимационными эффектами, они не должны отвлекать внимание от содержания информации на слайде.

Представление информации:

Содержание информации	· Используйте короткие слова и предложения. · Минимизируйте количество предлогов, наречий, прилагательных. · Заголовки должны привлекать внимание аудитории.
Расположение информации на странице	· Предпочтительно горизонтальное расположение информации. · Наиболее важная информация должна располагаться в центре экрана. · Если на слайде располагается картинка(фото), надпись должна располагаться под ней.
Шрифты	· Для заголовков – не менее 24. · Для информации не менее 18. · Шрифты без засечек легче читать с большого расстояния. · Нельзя смешивать разные типы шрифтов в одной презентации. · Для выделения информации следует использовать жирный шрифт, курсив или подчеркивание. · Нельзя злоупотреблять прописными буквами (они читаются хуже строчных).
Способы выделения информации	· Следует использовать: рамки; границы, заливку; штриховку, стрелки; рисунки, диаграммы, фото.
Объем информации	· Не стоит заполнять один слайд слишком большим объемом информации: люди могут единовременно запомнить не более трех фактов, выводов, определений. · Наибольшая эффективность достигается тогда, когда ключевые пункты отображаются по одному на каждом отдельном слайде.
Виды слайдов	Для обеспечения разнообразия следует использовать разные виды слайдов: с текстом; с таблицами; с диаграммами, иллюстрациями, фото и т.д.

Основные критерии оценки презентации:

1. Структура. Структура презентации соответствует общепринятой структуре (Наличие заголовка, фамилии авторов).

2. Содержание.

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

4. Коллективная работа. Слаженная работа в группе.

5. Понятность. Презентация не содержит логических ошибок и понятна практически без комментариев.

Тематика и задания самостоятельной работы

1. Подготовка к практическим занятиям с использованием методических рекомендаций преподавателя, подготовка к их защите.

Цель работы:

• Закрепление теоретических знаний, полученных при прослушивании лекций;

• Подготовка к выполнению практических работ и к их защите

Задание: Пользуясь интернет источниками, учебно-методическим обеспечением МДК, лекционным материалом, методическими указаниями к выполнению практических работ повторить теоретический материал по соответствующим темам работ м ответить на контрольные вопросы к ним.

Для подготовки ответов на контрольные вопросы по ПР необходимо воспользоваться методическими указаниями по выполнению практических работ (МУ к ПР).

МУ к ПР№1. Решение задач по комбинаторике.

МУ к ПР№2. Решение задач по теории вероятности

МУ к ПР№3. Сложные вероятности

МУ к ПР№4. Решение задач по математической статистике

МУ к ПР №5 Решение задач по теории графов

МУ к ПР №6 Решение задач по теории массового обслуживания

1. Подготовка реферата

Цели:

• сформировать навыки работы с учебной и технической литературой, интернет – источниками;

• получить более глубокие знания по данной теме;

• научиться составлять и оформлять рефераты.

Порядок выполнения работы

1. Подобрать, проанализировать и систематизировать материал по данной теме.

2. Изучить правила выполнения реферативных работ.

3. Подготовить реферат

4. Оформить реферат в соответствии со всеми требованиями и сдать для проверки в установленные сроки.

Тематика рефератов

Раздел 3. Основы теории графов

• Конечные графы;

• Бесконечные графы;

• Теорема Эйлера.

Форма контроля:

• проверка рефератов;

• заслушивание лучших рефератов на занятии;

Литература:

1. Составление презентации

Раздел 2. Элементы теории автоматов:

• Алгебраическая теория конечных автоматов.

• Определение конечного автомата.

• Способы задания автомата. Некоторые примеры автоматов

4 . Выполнение расчетного задания.

Раздел 1. Основные теории вероятностей и математической статистики

Расчетное задание №1.

1. Сколькими способами из 9 учебных предметов можно составить расписание учебного дня из 6 различных уроков?

2. Имеются помидоры, огурцы, лук. Сколько различных салатов можно приготовить, если в каждый салат должно входить 2 различных вида овощей?

3. Сколько различных пятизначных чисел можно составить из цифр 1, 2, 3, 4, 5?

4. В вазе стоят 10 красных и 5 розовых гвоздик. Сколькими способами можно выбрать из вазы пять гвоздик одного цвета?

5. Вычислить: 6! – 5!

6. Сколькими способами могут встать в очередь в билетную кассу 3 человека?

7. Сколькими способами можно выбрать трех дежурных из группы в 20 человек?

8. Сколько существует различных двузначных чисел, в записи которых можно использовать цифры 1, 2, 3, 4, 5, 6, если цифры в числе должны быть различными?

9. Сколькими способами один почтальон может разнести 7 писем по семи адресам.

10. Вычислите:

Рекомендации по выполнению: кратко записать условие задачи, привести решение, ответ.

Пример решение расчетного задания 5:

В ящике находится 15 деталей. Сколькими способами можно взять 4 детали?

Решение:

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

В задаче речь идёт о выборке из 4 деталей, в которой не имеет значения их «дальнейшая судьба» – грубо говоря, «просто выбрали 4 штуки и всё». Таким образом, у нас имеют место сочетания деталей. Считаем их количество:

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

 способами можно взять 4 детали из ящика.

Ещё раз: что это значит? Это значит, что из набора 15 различных деталей можно составить одну тысячу триста шестьдесят пять уникальных сочетания 4 деталей. То есть, каждая такая комбинация из четырёх деталей будет отличаться от других комбинаций хотя бы одной деталью.

Ответ: 1365 способами

Расчетное задание №2.

Уровень А.

1. На станции работает несколько касс по продаже жетонов. Среднее время обслуживания составляет 1 минуту, а интенсивность потока заявок на обслуживание равна 3 (чел в минуту). Определить среднюю длину очереди для семи работающих касс и время пребывания в очереди.

2. В мастерской работает 5 мастеров. Клиенты приходят на обслуживание в среднем каждые 20 минут, время обслуживания 1 клиента составляет 1,5 часа. Определить среднее число клиентов в системе и среднюю длину очереди.

Уровень В.

1. АТС имеет 6 линий связи. Поток заявок имеет интенсивность 1 вызов минуту, а время каждого разговора составляет в среднем 3 минуты. Определить вероятность отказа и вероятность того, что ни одна линия связи не будет занята.

2. АТС имеет 5 линий связи. Поток заявок имеет интенсивность 2 вызова в минуту, а время каждого разговора составляет в среднем 3 минуты. Определить вероятность отказа и вероятность того, что ни одна линия связи не будет занята.

3. На станции работает несколько касс по продаже жетонов. Среднее время обслуживания составляет 0.5 минуты, а интенсивность потока заявок на обслуживание равна 8 (чел. в минуту). Определить среднюю длину очереди для 5 работающих касс.

4. В мастерской работает 8 мастеров. Клиенты приходят на обслуживание в среднем каждые 10 минут, время обслуживания 1 клиента составляет 1 час. Определить среднее число свободных мастеров и среднюю длину очереди.

Рекомендации по выполнению: кратко записать условие задачи, привести решение, ответ.

Пример решение расчетного задания 7:

В мастерской работает 4 мастера. Клиенты приходят на обслуживание в среднем каждые 10 минут, время обслуживания 1 клиента составляет 30 минут. Определить вероятности первых 7-и состояний системы, вероятность отказа и среднюю длину очереди.

Решение:

Тип системы: СМО с ожиданием

Количество каналов: n=4

Интенсивность поступления заявок: λ = 1/10

Интенсивность обслуживания: µ = 1/30

Коэффициент загрузки каналов: α = λ/ µ = 3

Размеченный граф состояний системы:

S0 – состояние, в котором в системе отсутствуют заявки;

S1 – состояние, при котором в системе 1 заявка;

S4 – состояние, при котором в системе 4 заявки, все каналы заняты;

S5 – состояние, при котором в системе 5 заявок, 1 заявка в очереди.

P0 = 1/ ()

I. при knPk=P0* α^k/k!

II. при knPk=P0* α^k/(n!*n^k-n)

Pотк = Pn=P4

Lq= Pn*

P0=0.0379 P1=0.1132 P2=0.1698 P3=0.1698 P4=0.1274

Раздел 3. Основы теории графов

Расчетное задание №3.

Дан взвешенный связный неориентированный граф, состоящий из пяти вершин. Необходимо найти остов минимального веса с помощью алгоритма Краскаля.

Задача 1. Задача 2.

Задача 3. Задача 4.

Рекомендации по выполнению: кратко записать условие задачи, привести решение, ответ.

Пример решение расчетного задания 1:

Изображение	Описание
	Ребра AD и CE имеют минимальный вес, равный 5. Произвольно выбираетсяребро AD (выделено на рисунке).
	Теперь наименьший вес, равный 5, имеет ребро CE. Так добавление CE необразует цикла, то выбираем его в качестве второго ребра.
	Аналогично выбираем ребро DF, вес которого равен 6.
	Следующие ребра — AB и BE с весом 7. Произвольно выбирается ребро AB,выделенное на рисунке. Ребро BD выделено красным, так уже существуетпуть (зеленый) между B и D, поэтому, если бы это ребро было выбрано, тообразовался бы цикл ABD.
	Аналогичным образом выбирается ребро BE, вес которого равен 7. На этомэтапе красным выделено гораздо больше ребер: BC, потому что оно создастцикл BCE, DE, потому что оно создаст цикл DEBA, и FE, потому что оносформирует цикл FEBAD.
	Алгоритм завершается добавлением ребра EG с весом 9. Минимальноеостовное дерево построено.

Расчетное задание №4.

Найти кратчайшие расстояния

Задача 1. От 1-й вершины до 2-й вершины графа.

Задача 2. От 1-й вершины до 3-й вершины графа.

Задача 3. От 1-й вершины до 4-й вершины графа.

Задача 4. От 1-й вершины до 5-й вершины графа.

Задача 5. От 1-й вершины до 6-й вершины графа.

Рекомендации по выполнению: кратко записать условие задачи, привести решение, ответ.

Пример решение расчетного задания 2:

Требуется найти кратчайшие расстояния от 1-й вершины до всех остальных для графа, представленного на рисунке:

№	Алгоритм	Конкретные действия
1.	Инициализация.	Cтартовая вершина, от которой строится дерево кратчайших путей - вершина № 1. Задаем стартовые условия: d(1)=0, d(x)=∞. Окрашиваем вершину № 1, y=1. Находим ближайшую вершину к окрашенной нами, используя формулу: . Составим матрицу длин кратчайших дуг для данного графа. №/№ 1 2 3 4 5 6 1 7 9 14 2 7 10 15 3 9 10 11 2 4 15 11 6 5 6 9 6 14 2 9 или
2.	Первый шаг. Рассмотрим шаг алгоритма Дейкстры.	d(2)=min{d(2) ; d(1)+a(1,2)}=min{∞; 0+7}=7 d(3)=min{d(3) ; d(1)+a(1,3)}=min{∞; 0+9}=9 d(4)=min{d(4) ; d(1)+a(1,4)}=min{∞; 0+∞}=∞ d(5)=min{d(5) ; d(1)+a(1,5)}=min{∞; 0+∞}=∞ d(6)=min{d(6) ; d(1)+a(1,6)}=min{∞; 0+14}=14 Минимальную длину имеет путь от вершины № 1 до вершины № 2 d(2)=7. Включаем вершину № 2 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (1,2).
3.	Второй шаг.	d(3)=min{d(3) ; d(2)+a(2,3)}=min{9; 7+10}=9 d(4)=min{d(4) ; d(2)+a(2,4)}=min{∞; 7+15}=22 d(5)=min{d(5) ; d(2)+a(2,5)}=min{∞; 7+∞}=∞ d(6)=min{d(6) ; d(2)+a(2,6)}=min{14; 7+∞}=14 Минимальную длину имеет путь от вершины № 1 до вершины № 3 d(3)=9. Включаем вершину № 3 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (1,3)
4.	Третий шаг.	d(4)=min{d(4) ; d(3)+a(3,4)}=min{22; 9+11}=20 d(5)=min{d(5) ; d(3)+a(3,5)}=min{∞; 9+∞}=∞ d(6)=min{d(6) ; d(3)+a(3,6)}=min{14; 9+2}=11 Минимальную длину имеет путь от вершины № 1 до вершины № 6 d(6)=11. Включаем вершину № 6 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (1,6)=(1,3)+(3,6)
5.	Четвертый шаг.	d(4)=min{d(4) ; d(6)+a(6,4)}=min{20; 11+∞}=20 d(5)=min{d(5) ; d(6)+a(6,5)}=min{∞; 11+9}=20 Минимальную длину имеет путь от вершины № 1 до вершины № 4 и № 5 d(4)=d(6)=20. Включаем вершину № 4 и № 5 в текущее ориентированное дерево, а так же дугу ведущую в эту вершину. Согласно выражению это дуга (1,4)=(1,3)+(3,4) и (1,5)=(1,3)+(3,6)+(6,5).
6.	Заключение.	Мы получили ориентированное дерево кратчайших путей начинающихся в вершине №1 для исходного графа. d(1)=1 Длина маршрута L=0 d(2)=1-2 Длина маршрута L=7 d(3)=1-3 Длина маршрута L=9 d(4)=1-3-4 Длина маршрута L=20 d(5)=1-3-6-5 Длина маршрута L=20 d(6)=1-3-6 Длина маршрута L=11

Литература и интернет-ресурсы:

1. Асанов, М. О. Дискретная математика: графы, матроиды, алгоритмы: Учебное пособие. 2-е изд. / М.О. Асанов , В.А.Баранский , В.В. Расин - СПб. : Издательство «Лань» 2012г. 368с. - ISBN 978-5-8114-1068-2

2. Новиков, Ф.А. Дискретная математика: Учебник для вузов. 2-е изд. Стандарт третьего поколения: учебник / Ф.А. Новиков. - СПб. : Питер 2012, 400с.- ISBN 978-5-496-00015-4

3. Образовательный математический сайт «Еxponenta.ru» [Электронный ресурс] – Режим доступа: http://exponenta.ru/

Интернет-ресурсы

1. http://www.bestreferat.ru/.

2. http://www.coolreferat.com/

3. http://www.kazedu.kz/

4. http://otherreferats.allbest.ru/

5. http://referats.allbest.ru/

6. http://www.newreferat.com/

7. http://www.myshared.ru/

8. http://www.ilit.ru/

9. http://sihcompany.narod.ru/

10. http://xreferat.ru/

11. http://tgspa.ru/

12.http://www.dokanet.net

13.http://www.xnets.ru

14.http://twoysoft.ru твой софт