Учебной дисциплины «Теория графов» для направления 010400. 62 «Прикладная математика и информатика»



Скачать 35.87 Kb.
Дата08.10.2012
Размер35.87 Kb.
ТипДокументы
АННОТАЦИЯ

программы учебной дисциплины «Теория графов»

для направления 010400.62 «Прикладная математика и информатика»

профиль «Математическое и информационное обеспечение экономической деятельности»
Общее количество часов – 180 ч. (5 зачетных единиц)


  1. Цели и задачи дисциплины

Цель изучения дисциплины:

– формирование у студентов теоретических и методологических основ теории графов.

Задачи изучения дисциплины:

– расширение сферы компетенции студентов в теории графов;

– овладение студентами понятийно-терминологическим аппаратом теории графов;

– овладение приемами применение теории графов к решению прикладных задач.



  1. Требования к уровню освоения содержания дисциплины

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

Общекультурные компетенции (ОК):

способность работать в коллективе и использовать нормативные правовые документы в своей деятельности (ОК-13);

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

способность работы с информацией из различных источников, включая сетевые ресурсы сети Интернет, для решения профессиональных и социальных задач (ОК-15);

способность к интеллектуальному, культурному, нравственному, физическому и профессиональному саморазвитию, стремление к повышению своей квалификации и мастерства (ОК-16).
Профессиональные компетенции (ПК):

способность понимать и применять в исследовательской и прикладной деятельности современный математический аппарат (ПК-3);

способность в составе научно-исследовательского и производственного коллектива решать задачи профессиональной деятельности (ПК-4);

способность критически переосмысливать накопленный опыт, изменять при необходимости вид и характер своей профессиональной деятельности (ПК-5);

способность собирать, обрабатывать и интерпретировать данные современных научных исследований, необходимые для формирования выводов по соответствующим научным, профессиональным, социальным и этическим проблемам (ПК-7);

способность применять в профессиональной деятельности современные языки программирования и языки баз данных, операционные системы, электронные библиотеки и пакеты программ, сетевые технологии (ПК-10);

способность составлять и контролировать план выполняемой работы, планировать необходимые для выполнения работы ресурсы, оценивать результаты собственной работы (ПК-12).

В результате изучения дисциплины студент должен:

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

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

владеть: навыками практического использования современного математического инструментария для решения и анализа задач экономики, физики и информатики.


  1. Содержание дисциплины. Основные разделы

История возникновения и развития теории графов: задача о кенигсбергских мостах, головоломка Гамильтона, задача о четырех красках, задачи связанные с химией и физикой.

Основные понятия и определения:

понятие графа, основные определения (вершины, ребра, дуги, ориентированные и неориентированные графы, простой граф, петли, кратные ребра, виды графов, подграфы и дополнения, операции над графами и т.д.);

маршруты, цепи, пути, циклы;

связность, компоненты связности.

Эйлеровы и гамильтоновы графы: эйлеров путь, эйлеров цикл, гамильтонов путь, гамильтонов цикл.

Планарность графов, деревья:

планарные графы, формула Эйлера, критерий планарности;

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

Раскраска: раскраска графов, вершинная k-раскраска, задача о раскрашивании карт, ее связь с вершинной раскраской графа.

Представление графов в компьютере: матрица смежности, матрица инцидентности, списки смежности.

Алгоритмы на графах:

обходы графов (в ширину и глубину (рекурсивная и нерекурсивная реализация));

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

алгоритмы нахождения кратчайших путей от выделенной вершины (алгоритм Форда-Беллмана, Дейкстры, алгоритм Флойда).

Потоки в сетях: понятие сети, понятие потока в сети, алгоритм Форда-Фолкерсона для сети с одним источником и одним стоком.


Похожие:

Учебной дисциплины «Теория графов» для направления 010400. 62 «Прикладная математика и информатика» iconПрограмма наименование дисциплины: Теория графов Рекомендуется для направления (ий) подготовки (специальности (ей))
Курс «Теория графов» является дисциплиной по выбору в бакалаврской программе направления «Прикладная математика и информатика». Курс...
Учебной дисциплины «Теория графов» для направления 010400. 62 «Прикладная математика и информатика» iconПрограмма дисциплины Теория информации и комбинаторная теория поиска для направления 010400. 68 «Прикладная математика и информатика»

Учебной дисциплины «Теория графов» для направления 010400. 62 «Прикладная математика и информатика» iconУчебной дисциплины «Методы оптимизации» для направления 010400. 62 «Прикладная математика и информатика»
«Методы оптимизации» для направления 010400. 62 «Прикладная математика и информатика»
Учебной дисциплины «Теория графов» для направления 010400. 62 «Прикладная математика и информатика» iconРабочая программа дисциплины Прикладная статистика Направление подготовки 010400 Прикладная математики и информатика
Учебная дисциплина «Прикладная статистика» относится к вариативной части профессионального цикла (Б. 3) по направлению 010400 «Прикладная...
Учебной дисциплины «Теория графов» для направления 010400. 62 «Прикладная математика и информатика» iconПрограмма дисциплины Дискретная математика для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров

Учебной дисциплины «Теория графов» для направления 010400. 62 «Прикладная математика и информатика» iconПрограмма дисциплины Дискретная математика для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров

Учебной дисциплины «Теория графов» для направления 010400. 62 «Прикладная математика и информатика» iconБакалаврской программы 010400. 62 «Прикладная математика и информатика» реализуемой на кафедре №31 «Прикладная математика»
Код и наименование направления подготовки, наименование программы: 010400. 62 «Прикладная математика и информатика»
Учебной дисциплины «Теория графов» для направления 010400. 62 «Прикладная математика и информатика» iconПрограмма дисциплины Компьютерная лингвистика для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров

Учебной дисциплины «Теория графов» для направления 010400. 62 «Прикладная математика и информатика» iconПрограмма дисциплины Распределенные системы для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров

Учебной дисциплины «Теория графов» для направления 010400. 62 «Прикладная математика и информатика» iconПрограмма дисциплины Автоматическая обработка текстов для направления 010400. 68 «Прикладная математика и информатика» подготовки магистров

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org