Дискретная математика

П Дискретная математика . Ф . Предмет в объеме 90 часов является обязательным (федеральный 0 компонент) в разделе дисциплин предметной подготовки. 2 Включает в себя теоретический и практический материал по темам: Рекуррентные соотношения. Способы решения рекуррентных соотношений. Суммы и рекуррентности. Целочисленные функции x, x, mod. Бином Ньютона. Биномиальные коэффициенты. Основные тождества с биномиальными коэффициентами. Полиномиальная формула. Введение в асимптотические методы. Асимптотические решения рекуррентных соотношений. Формула суммирования Эйлера. Основные комбинаторные конфигурации. Метод включения-исключения. Основные понятия теории графов. Связные графы. Изоморфизм графов. Эйлеровы и гамильтоновы графы. Деревья. Паросочетания, независимые множества и клики. Пленарные графы. Теорема Эйлера и ее следствия. Непланарность графов К5 и Кз,з. Раскраска вершин и ребер графа. Двудольные графы. Теорема Кенига. Раскрашиваемость вершин планарного графа пятью красками. Гипотеза четырех красок. Студент должен знать теоретические основы дисциплины в объёме, необходимом для решения типовых задач ; уметь решать типовые задачи изучаемой дисциплины. Связь с другими дисциплинами: Все дисциплины математического цикла. Специальность: Информатика с дополнительной специальностью. Выписка из ГОС ВПО (для дисциплин Федерального компонента).ДПП.Ф.0 2 90 Дискретная математика Рекуррентные соотношения. Способы решения рекуррентных соотношений. Суммы и рекуррентности. Целочисленные функции x, x, mod. Бином Ньютона. Биномиальные коэффициенты. Основные тождества с биномиальными коэффициентами. Полиномиальная формула. Введение в асимптотические методы. Асимптотические решения рекуррентных соотношений. Формула суммирования Эйлера. Основные комбинаторные конфигурации. Метод включения-исключения. Основные понятия теории графов. Связные графы. Изоморфизм графов. Эйлеровы и гамильтоновы графы. Деревья. Паросочетания, независимые множества и клики. Пленарные графы. Теорема Эйлера и ее следствия. Непланарность графов К5 и Кз,з. Раскраска вершин и ребер графа. Двудольные графы. Теорема Кенига. Раскрашиваемость вершин планарного графа пятью красками. Гипотеза четырех красок.