МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

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

СБОРНИК ИНДИВИДУАЛЬНЫХ ЗАДАНИЙ

ПО ДИСКРЕТНОЙ МАТЕМАТИКЕ

для студентов 2 курса

специальности 230700.62

«Прикладная информатика»

Теория графов

Теория чисел

Теория кодирования

Комбинаторика

Алгебра высказываний

Булевы функции

Брянск 2012

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

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

Рецензенты:

Сорокина М.М. кандидат физико-математических наук,

доцент кафедры алгебры БГУ.

© Корпачева М.А., 2012

Содержание

Введение……………………………………………………………………4

Глава 1. Элементы теории графов………………………………………..5

Глава 2. Элементы теории чисел…………………………….…………..12

Глава 3. Элементы теории кодирования………………………………...19

Глава 4. Элементы комбинаторного анализа…………………………...24

Глава 5. Элементы алгебры высказываний……………………………..32

Глава 6. Булевы функции………………………………………………...42

Вопросы к экзамену……………………………………………………...54

ВВЕДЕНИЕ

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

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

Основным носителем дискретной математики является множество элементов, а структуру дискретной модели формируют отношения между этими элементами.

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

1. Элементы теории графов Основные определения и понятия темы

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