Рабочая программа дисциплины «Дискретная математика»



Скачать 399,98 Kb.
Дата19.05.2015
Размер399,98 Kb.
ТипРабочая программа

Министерство образования и науки Российской Федерации

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

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

«Комсомольский-на-Амуре государственный технический университет»

Кафедра информационной безопасности автоматизированных систем

УТВЕРЖДАЮ

Первый проректор ГОУВПО «КнАГТУ»

______________________ А.Р. Куделько

"_____"___________________ 2010 года


РАБОЧАЯ ПРОГРАММА

дисциплины «Дискретная математика»

основной образовательной программы подготовки дипломированных
специалистов по специальности 090105 «Комплексное обеспечение информационной безопасности автоматизированных систем»

Форма обучения очная

Технология обучения традиционная

Объем дисциплины 200 часов, 6 зачетных единиц


Комсомольск-на-Амуре 2010

Рабочая программа обсуждена и одобрена на заседании кафедры "Информационная безопасность автоматизированных систем"
И.о. заведующего кафедрой _________________ И.А. Трещев

(подпись)


"_____" ______________ 2010 года

СОГЛАСОВАНО:

Начальник учебно-методического управления _______________ А.А. Скрипилев

(подпись)

"_____" ______________ 2010 года
Декан ФКТ _________________ В.П. Котляров

(подпись)

"_____" ______________ 2010 года
Рабочая программа рассмотрена, одобрена и рекомендована к использованию методической комиссией факультета компьютерных технологий.

Председатель методической комиссии _________________ В.П. Котляров

(подпись)

"_____" ______________ 2010 года

Автор рабочей программы

___________________ И.А. Трещев

(подпись)

"_____" ______________ 2010 года



СОДЕРЖАНИЕ
Введение 4

1. Пояснительная записка 4

1.1. Требования государственного образовательного стандарта высшего

профессионального образования к структуре и содержанию курса

«Дискретная математика» 4

1.2. Предмет, цели, задачи и принципы построения курса 4

1.3. Роль и место курса в структуре реализуемой образовательной программы 5

1.4. Объемы учебной работы и предусмотренные рабочими учебными планами

реализуемой образовательной программы формы аттестации ее результатов 5

2. Структура и содержание курса 6

3. Календарный график изучения курса 9

3.1. Лекции 9

3.2. Практические занятия (упражнения)..........................................................................11

3.3. Объем, структура и содержание самостоятельной работы студентов, график

ее выполнения 13

4. Технологии и методическое обеспечение контроля результатов учебной

деятельности обучаемых 15

5. Ресурсное обеспечение курса 19

5.1. Список основной учебной и учебно-методической литературы 19

5.2. Список дополнительной учебной и учебно-методической литературы 20

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


Введение

Дисциплина «Дискретная математика» изучается на втором курсе (четвертый) и на третьем курсе (пятый семестр) в рамках цикла естественнонаучных дисциплин (федеральная компонента) учебного плана подготовки по специальности 090105 «Комплексное обеспечение информационной безопасности автоматизированных систем». Основная цель рабочей программы – отражение основной структуры и введение в общее содержание курса.

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

  1. Пояснительная записка

    1. Требования государственного образовательного стандарта высшего профессионального образования к структуре и содержанию курса


Рабочая программа разработана на основании требований государственного образовательного стандарта высшего профессионального образования специальности 090105 «Комплексное обеспечение информационной безопасности автоматизированных систем», утвержденного 05.04.2000 г., рег.№ 284 инф/сп. Данный стандарт содержит следующие требования по содержанию курса ЕН.Ф.07 «Дискретная математика»:


ЕН.Ф.07

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

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

Графы и орграфы; изоморфизмы; деревья; эйлеровы гра­фы; планарные графы; покрытия и независимые множества; сильная связность в орграфах; анализ графа цепи Маркова; алгоритмы поиска кратчайших путей в графах; задача поиска гамильтонова цик­ла в графе; задача о коммивояжере;

Теория формальных языков и автоматов:

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


200



    1. Предмет, цели, задачи и принципы построения курса


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

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

Специалист по защите информации по специальности 090105 «Комплексное обеспечение информационной безопасности автоматизированных систем»


  • должен знать

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

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

  • основы теории языков и методов трансляции

  • основы теории автоматов, формальных грамматик, автоматного программирования.

  • должен уметь

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

  • формально описать основные алгоритмы на графах;

  • применять теорию графов на практике.

  • должен владеть

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

  • применением теории графов и теории детерминированных и недетерминированных автоматов при анализе задач, построении математических моделей;.

Принципы построения курса

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

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

Третий принцип – тесная взаимосвязь лекционных занятий и тем практических занятий и расчетно-графических заданий. Последовательность изучения и объем теоретического материала, излагаемый на лекциях, согласованы с темами практических занятий, РГЗ и графиком их выполнения.

    1. Роль и место курса в структуре реализуемой образовательной программы


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

    1. Объемы учебной работы и предусмотренные рабочими учебными планами реализуемой образовательной программы формы аттестации ее результатов


Характеристика трудоемкости курса представлена в таблице 1.
Таблица 1

Характеристика трудоемкости курса (дисциплины)





  1. Структура и содержание курса


Структуру курса можно представить в виде следующих модулей (табл. 2).
Таблица 2

Наименование

Описание

Множества

Множества и операции над ними. Способы задания, диаграммы Эйлера-Венна. Основные тождества алгебры множеств. Доказательство методом включения, с помощью «формы то х», с помощью характеристической функции, используя тождества алгебры множеств. Отношения и функции. Инъекция, сюръекция, биекция. Частично-упорядоченные, линейно-упорядоченные, вполне упорядоченные множества. Диаграммы Хассе частично-упорядоченных множеств. Изоморфизм частично-упорядоченных множеств. Функция Мебиуса. Теорема о произведении. Формула обращения. Метод математической индукции, доказательство от противного.

Отношения

Отношения и функции. Виды отношений (рефлексивное и др.). Классы эквивалентностей. Фактор-множество, отношение частичного порядка, толерантность, квазипорядок.n-арные и бинарные алгебраические операции. Мультипликативные и аддитивные формы. Суперпозиция функций. Решетки, дистрибутивные решетки. Булеан и теорема о числе элементов множества всевозможных подмножеств заданного множества. Диагональный метод Кантора, счетные и несчетные множества. Метод трансфинитной индукции. Малая теорема Ферма (доказательство по индукции, доказательство из теоремы Эйлера).

Комбинаторный анализ

Основной принцип комбинаторики. Теорема о включениях и исключениях. Перестановки, размещения, сочетания. Бином Ньютона, обобщенный бином Ньютона. Полугруппы, группы моноиды, группа подстановок. Свойства биномиальных коэффициентов, треугольник Паскаля. Числа Стирлинга, Белла, производящие функции. Числа Фибоначчи, Каталана.

Алгебраические структуры

Универсальные алгебры, подалгебры. Гомоморфизмы: мономорфизмы, эпиморфизмы, изоморфизмы. Эндоморфизмы, автоморфизмы. Изоморфизм на множестве однотипных алгебр. Алгебры с одной операцией(полугруппы, моноиды, группы, абелевы группы). Алгебры с двумя операциями(кольца, коммутативные кольца, поля, векторные пространства). Базис и линейная комбинация в векторном пространстве. Матроиды. Жадный алгоритм. Переключательные функции и число всевозможных ПФ(булевых) с заданным числом аргументов. Алгебра ПФ. Правило подстановки. Принцип двойственности. СДНФ, СКНФ. Замкнутые классы булевых функций. Полнота, полином Жегалкина. Теорема Поста.

Алгоритмы

Метод разделяй и властвуй, рекурсивное программирование, динамическое программирование, частично-рекурсивные функции, тезис Чёрча, разрешимые и неразрешимые проблемы, NP-полные задачи

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

Определение графа и орграфа. Простые, регулярные, псевдогрфы и мультиграфы. Теорема Эйлера о сумме степеней вершин графа. Представления графов в виде диаграмм. Смежность, инцидентность степени. Изоморфизм и гомеоморфизм графов. Задание графов при помощи матриц. Примеры графов. Алгоритм нахождения наименьшего пути в нагруженном графе. Операции с графами. Двудольные графы. Пустые графы, колесо, полносвязный граф, циклический граф. Дополнение графа. Наибольшее паросочетание. Хроматическое число графа. Хроматическая функция графа, индуктивное определение бинарного дерева, Хроматическая функция дискретного графа, хроматическая функция дерева с n вершинами, Хроматическая функция конечного графа с n вершинами. Теорема Кэли, теорема о числе максимальных поддеревьев связанного графа. Маршруты цепи циклы. Связность и компоненты связности. Разделяющие множества, разрезы, мосты. Расстояние в графе, диаметр, радиус и центр графа. Задача Эйлера о шахматном коне, задача о Кенигсбергских мостах, задача Гаусса о восьми ферзях, задача коммивояжера. Эйлеровы цепи и циклы, Эйлеровы графы. Гамильтоновы цепи и циклы, Гамильтоновы графы. Эйлерова характеристика плоских графов. Графы Куратовского, раскраска плоского графа, Платоновы тела. Критерий Понтрягина-Куратовского. Планарные графы. Теорема о пяти красках. Полные бинарные деревья, теорема о числе листьев полного бинарного дерева и теорема об оценке высоты бинарного дерева. Деревья и лес, минимальное остовное дерево связного и нагруженного графа. Цикломатическое число графа. Коциклический ранг графа. Фундаментальная система циклов. Бинарные деревья и деревья поиска. Алгоритм бинарного поиска. Покрывающие множества вершин и ребер. Независимые множества вершин и ребер. Связи чисел независимости и покрытий. Доминирующие множества вершин. Доминирование и независимость. Задача о наименьшем покрытии.

Основы математического моделирования

Инициальные автоматы, детерминированные и недетерминированные автоматы, машина Тьюринга. Автоматы Мура и Мили. Конечные автоматы, автоматы с магазинной памятью. Транспортные сети, потоки в транспортных сетях, величина потока, полный поток транспортной сети, допустимый поток.

Теория формальных языков и автоматов

Конечные автоматы; автоматные базисы и проблема полноты; эквивалентность в автоматах; автомат­ные языки; понятие формальной грамматики; при­менение грамматик для построения языков высоко­го уровня; тестиро­вание автоматов; вероятностные автоматы.
  1. Календарный график изучения курса


3.1. Лекции

В таблицах 3-4 представлена программа лекционного курса «Дискретная математика».

Программа лекций на четвертый семестр

Таблица 3




Номер темы

Тема

К-во час

1

2

3

1

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

2


2

Теорема Эйлера. Малая теорема Ферма. Основы алгебры и алгебраические структуры.

2

3

Основной принцип комбинаторики. Теорема о включениях и исключениях

2

4

Перестановки, размещения, сочетания. Бином Ньютона, обобщенный бином Ньютона. Полугруппы, группы моноиды, группа подстановок. Свойства биномиальных коэффициентов, треугольник Паскаля. Числа Стирлинга, Белла, производящие функции. Числа Фибоначчи, Каталана.

2

5

Наибольшее паросочетание. Хроматическое число графа.

Хроматическая функция графа, индуктивное определение бинарного дерева, Хроматическая функция дискретного графа, хроматическая функция дерева с n вершинами, Хроматическая функция конечного графа с n вершинами. Теорема Кэли, теорема о числе максимальных поддеревьев связанного графа. Маршруты цепи циклы. Связность и компоненты связности. Разделяющие множества, разрезы, мосты. Расстояние в графе, диаметр, радиус и центр графа. Задача Эйлера о шахматном коне, задача о Кенигсбергских мостах, задача Гаусса о восьми ферзях, задача коммивояжера. Эйлеровы цепи и циклы, Эйлеровы графы. Гамильтоновы цепи и циклы, Гамильтоновы графы. Эйлерова характеристика плоских графов. Графы Куратовского, раскраска плоского графа, Платоновы тела. Критерий Понтрягина-Куратовского.



2

6

Определение графа и орграфа. Простые, регулярные, псевдогрфы и мультиграфы. Теорема Эйлера о сумме степеней вершин графа. Представления графов в виде диаграмм. Смежность, инцидентность степени. Изоморфизм и гомеоморфизм графов. Задание графов при помощи матриц. Примеры графов. Алгоритм нахождения наименьшего пути в нагруженном графе. Операции с графами. Двудольные графы. Пустые графы, колесо, полносвязный граф, циклический граф. Дополнение графа. Анализ графа цепи Маркова.

2

7

Универсальные алгебры, подалгебры. Гомоморфизмы: мономорфизмы, эпиморфизмы, изоморфизмы. Эндоморфизмы, автоморфизмы. Изоморфизм на множестве однотипных алгебр.

2

8

Планарные графы. Теорема о пяти красках. Полные бинарные деревья, теорема о числе листьев полного бинарного дерева и теорема об оценке высоты бинарного дерева. Деревья и лес, минимальное остовное дерево связного и нагруженного графа. Цикломатическое число графа. Коциклический ранг графа. Фундаментальная система циклов. Бинарные деревья и деревья поиска. Алгоритм бинарного поиска. Покрывающие множества вершин и ребер. Независимые множества вершин и ребер. Связи чисел независимости и покрытий. Доминирующие множества вершин. Доминирование и независимость. Задача о наименьшем покрытии.

3




Итого за четвертый семестр:

18

Программа лекций на пятый семестр

Таблица 4



Номер

п/п


Тематика лекций

Кол-во часов

1

2

3

1

Инициальные автоматы, детерминированные и недетерминированные автоматы, машина Тьюринга. Автоматы Мура и Мили. Конечные автоматы, автоматы с магазинной памятью. Транспортные сети, потоки в транспортных сетях, величина потока, полный поток транспортной сети, допустимый поток.


6

2

Описание синтаксиса входного языка. Нормальная форма Бэкуса.

Формальное определение языков программирования. Формальные языки и грамматики Порождающая грамматика. Классификация грамматик по Хомскому



4

4

Регулярная грамматика. Конечный автомат (КА). Распознаватели и преобразователи. КА и лексический анализ. Детерминированный и недетерминированный КА. План построения лексического анализатора

4

5

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

4

6

Автоматы и преобразователи с магазинной памятью; связь между КС - грамматиками и автоматами.

4

7

Нисходящий синтаксический анализ: общая характеристика и проблемы нисходящего анализа. Детерминированный нисходящий синтаксический анализ LL(K)-грамматики. Алгоритмы синтаксического анализа для S–грамматик и LL(K)-грамматик.

6

8

Простейшие автоматные базисы. Задача реализации. Автоматные базисы и проблема полноты

Последовательное соединение двух автоматов. Последовательное соединение с выходной функцией. Соединение автоматов с обратной связью. Компонентный автомат сети. Сеть автоматов. Тестирование автоматов.

Определение вероятностного автомата. Способы задания вероятностного автомата. Инициальная эквивалентность вероятностных автоматов.





9

Детерминированный восходящий синтаксический анализ: общие принципы синтаксического анализа снизу вверх. Алгоритмы синтаксического анализа для грамматик предшествования, LR(K)-грамматик.

6




Итого за пятый семестр:

34

ИТОГО в 4 – 5 семестрах – 52 час


3.2. Темы практических занятий
График проведения практических занятий по курсу представлен в таблице 5 для четвертого семестра и таблице 6 для пятого.

Таблица 5.



Номер темы

Тема

Кол-во часов

1

Множества

4

2

Отношения, теория графов

2

3

Комбинаторика сочетаний

6

4

Комбинаторика размещений

2

5

Комбинаторика разбиений

2

6

Доказательство от противного, методом математической индукции, трансфинитная индукция.

4

7

Комбинаторные задачи с ограничениями

4

8

Функция Мебиуса и диаграммы Хассе

4

9

Виды графов, теорема Эйлера, планарные графы, изоморфизм

4

10

Цикломатическое число графа, хроматическая функция графа, коды Прюфера

4




Итого в четвертом семестре:

36

Таблица 6



Номер п/п

Тема

Кол-во часов

11

Конечные автоматы Мили и Мура.

2

12

Преобразования конечных автоматов.

2

13

Эквивалентность в автоматах. Структурный анализ.

2

14

Эквивалентность в автоматах. Структурный синтез.

2

15

Регулярные выражения.

4

16

Использование регулярных выражений для анализа и синтеза.

2

17

Реализация конечных автоматов в простейших базисах. Вероятностные автоматы.

3




Итого в пятом семестре:

17



    1. Объем, структура и содержание самостоятельной работы студентов, график ее выполнения

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

Для самостоятельного изучения предлагаются следующие темы:





  1. Элементы криптоанализа и криптографии.

  2. Элементы нечеткой логики.

  3. Аксиоматика Цермело-Франкеля.

  4. Алгоритмы шифрования, сжатия изображений, вейвлет-анализа.

  5. Алгоритмы Флойда-Фалкерсона.



      1. Примерные требования к оформлению и сдаче отчетов по расчетно-графическим заданиям

По каждому РГЗ должен быть составлен отчет в виде документа MS Word содержащий следующие разделы:



  • титульный лист;

  • задание;

  • теоретический материал, содержащий описание методики выполнения расчетно-графического задания;

  • решение задач;

  • список использованной литературы.



      1. Расчетно-графическое задание

В ходе изучения дисциплины «Дискретная математика» студенты в каждом из семестров выполняют по одному расчетно-графическому заданию, темы которых представлены в таблицах 7,8.


Таблица 7



Тема

Объём само-

стоятельной

работы

1

Множества и отношения, теория графов, комбинаторный анализ

13

Итого в четвертом семестре:

13

Таблица 8





Тема

Объём само-

стоятельной

работы

1

Формальные грамматики и теория автоматов

15

Итого в пятом семестре:

15

3.3.4. Примерная структура самостоятельной работы студентов
Примерная структура и график выполнения самостоятельной работы студентов представлены в таблице 9-10.

Таблица 9

График выполнения самостоятельной работы студентов в четвертом семестре

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

Число часов в неделю

Итого

по видам


работ

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

Подготовка к лекциям

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

3,6

Изучение теоретических разделов курса

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2

0,2




3,4

Подготовка и выполнение контрольных мероприятий



















КР
0,5

0,5


0,5




























1,5

Выполнение и защита РГЗ











РГЗ1


0,5


0,5


0,5

0,5

0,5

0,5


0,5


0,5

0,5
















4,5


Итого

0,4

0,4

0,4

0,4

0,9

0,9

1,4

1,4

1,4

0,9

0,9

0,9

0,9

0,4

0,4

0,4

0,4

0,4

13

Таблица 10

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

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

Число часов в неделю

Итого

по видам


работ

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

Подготовка к лекциям

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

2

34

Изучение теоретических разделов курса

2

2

2

1

1

1

1

1

1

1

1

1

1

2

2

2

2

24

Подготовка и выполнение контрольных мероприятий



















КР
3

3


3

























9

Выполнение и защита РГЗ











РГЗ1

1


1


2


2

2

2

2


1


1

1














15


Итого

4

4

4

5

5

6

9

9

9

6

5

5

5

4

4

4

4

82

  1. Технологии и методическое обеспечение контроля результатов учебной деятельности обучаемых


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

              1. Сколько существует автомобильных номеров состоящих из 7 букв и 6 цифр если используется 20 букв и 7 цифр.

              2. Сколько существует способов выбрать из группы в 20 человек старосту, заместителя старосты, профорга и помощника заместителя старосты.

              3. Из колоды содержащей 52 карты вынимают 5 карт. Какова вероятность, что среди них ровно один король.

              4. Найти хроматическую функцию полного графа Kn .

              5. Доказать теорему Эйлера о сумме степеней вершин графа.

              6. Построить диаграмму Хассе частично упорядоченного множества делителей числа 360 упорядоченных отношением делимости.


Пример билета на контрольную работу пятый семестр

  1. Сколько подмножеств множества {1…1000} не содержат чисел кратных 6, содержат, по крайней мере, одно кратное 7 и не содержат чисел кратных 2.

  2. Найти коэффициент при x7y7 в разложении (x+y)10.

  3. Найти число разложений заданного числа в сумму слагаемых. Разложения, отличающиеся перестановкой слагаемых, считаются различными. Слагаемые состоят из чисел 4 и 5, сумма 40.

  4. Доказать, что данное тождество неверно A (B C) = (A \ B) (A \ C).

  5. Доказать тождество

  6. Распаковать и проверить упаковкой следующий код Прюфера 987654321.

  7. Построить конечный автомат для распознавания идентификаторов в языке программирования С++.

Студент, не выполнивший к концу изучения дисциплины две контрольных работы и два расчетно-графических задания, не допускается до экзамена. Зачет по дисциплине «Дискретная математика» выставляется в случае успешного выполнения студентом расчётно-графического задания в четвертом семестре. Экзамен проводится в письменной форме, время проведения экзамена – 2 академических часа. На экзамен каждому студенту предлагается четыре задания (1 билет). Пример экзаменационного билета приводится ниже.


Пример экзаменационного билета


  1. Кодовый замок имеет 5 одинаковых ячеек, каждая ячейка может быть установлена в одно из 6 устойчивых положений. Сколько различных комбинаций нужно перебрать (максимальное количество), чтобы не зная кода, открыть кодовый замок?

  2. Теорема о включениях и исключениях.

  3. Фактор-множество, отношение частичного порядка, толерантность, квазипорядок.n-арные и бинарные алгебраические операции.

  4. Эйлеровы циклы. Эйлеровы графы.


Перечень вопросов по дисциплине «Дискретная математика»


  1. Множества и операции над ними. Способы задания, диаграммы Эйлера-Венна.

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

  3. Отношения и функции. Инъекция, сюръекция, биекция. Частично-упорядоченные, линейно-упорядоченные, вполне упорядоченные множества.

  4. Диаграммы Хассе частично-упорядоченных множеств. Изоморфизм частично-упорядоченных множеств.

  5. Формула обращения. Метод математической индукции, доказательство от противного.

  6. Отношения и функции. Виды отношений (рефлексивное и др.). Классы эквивалентностей.

  7. Фактор-множество, отношение частичного порядка, толерантность, квазипорядок.n-арные и бинарные алгебраические операции.

  8. Мультипликативные и аддитивные формы. Суперпозиция функций.

  9. Решетки, дистрибутивные решетки. Булеан и теорема о числе элементов множества всевозможных подмножеств заданного множества.

  10. Диагональный метод Кантора, счетные и несчетные множества.

  11. Метод трансфинитной индукции. Малая теорема Ферма (доказательство по индукции, доказательство из теоремы Эйлера).

  12. Парадокс Рассела. Основной принцип комбинаторики. Число элементов декартового произведения множеств.

  13. Основная теорема комбинаторики. Число всевозможных функций.

  14. Теорема о числе элементов объединения пары непересекающихся множеств, пары пересекающихся множеств.

  15. Теорема о включениях и исключениях.

  16. Размещения без повторений, с повторениями. Сочетания без повторений.

  17. Сочетания с повторениями. Перестановки без повторений с повторениями.

  18. Метод математической индукции. Бином Ньютона.

  19. Группа подстановок. Графическое представление подстановок.

  20. Геометрическая интерпретация биномиальных коэффициентов.

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

  22. Разбиения заданного множества. Числа Стирлинга первого.

  23. Числа Стирлинга второго рода, Числа Белла.

  24. Формула Эйлера для числа взаимнопростных с заданным n.

  25. Обобщенный бином Ньютона.

  26. Производящие функции. Свойства производящих функций.

  27. Числа Фибоначчи и золотое сечение. Рекуррентные соотношения.

  28. Основные тождества для производящих функций, производящие функции элементарных последовательностей,

  29. Дифференцирование и интегрирование бесконечных рядов. Числа Каталана.

  30. Универсальные алгебры, подалгебры. Гомоморфизмы: мономорфизмы, эпиморфизмы, изоморфизмы.

  31. Эндоморфизмы, автоморфизмы. Изоморфизм на множестве однотипных алгебр.

  32. Матроиды. Жадный алгоритм.

  33. Определение графа и орграфа. Простые, регулярные, псевдогрфы и мультиграфы. Теорема Эйлера о сумме степеней вершин графа. Представления графов в виде диаграмм.

  34. Смежность, инцидентность степени. Изоморфизм и гомеоморфизм графов. Задание графов при помощи матриц. Примеры графов.

  35. Алгоритм нахождения наименьшего пути в нагруженном графе.

  36. Операции с графами. Двудольные графы. Пустые графы, колесо, полносвязный граф, циклический граф. Дополнение графа.

  37. Наибольшее паросочетание. Хроматическое число графа.

  38. Хроматическая функция графа, индуктивное определение бинарного дерева, Хроматическая функция дискретного графа, хроматическая функция дерева с n вершинами, Хроматическая функция конечного графа с n вершинами. Теорема Кэли, теорема о числе максимальных поддеревьев связанного графа.

  39. Маршруты цепи циклы. Связность и компоненты связности. Разделяющие множества, разрезы, мосты. Расстояние в графе, диаметр, радиус и центр графа.

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

  41. Гамильтоновы цепи и циклы, Гамильтоновы графы. Эйлерова характеристика плоских графов. Графы Куратовского, раскраска плоского графа, Платоновы тела. Критерий Понтрягина-Куратовского.

  42. Планарные графы. Теорема о пяти красках.

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

  44. Деревья и лес, минимальное остовное дерево связного и нагруженного графа. Цикломатическое число графа. Коциклический ранг графа. Фундаментальная система циклов. Бинарные деревья и деревья поиска. Алгоритм бинарного поиска.

  45. Алгоритм Дейкстры поиска кратчайшего пути между двумя вершинами графа.

  46. Инициальные автоматы, детерминированные и недетерминированные автоматы, машина Тьюринга.

  47. Автоматы Мура и Мили. Конечные автоматы, автоматы с магазинной памятью.

  48. Транспортные сети, потоки в транспортных сетях, величина потока, полный поток транспортной сети, допустимый поток.

  49. Автоматные базисы и проблема полноты, эквивалентность в автоматах, автомат­ные языки.

  50. Понятие формальной грамматики, при­менение грамматик для построения языков высоко­го уровня.

  51. Тестиро­вание автоматов, вероятностные автоматы.

  52. Нормальная форма Бэкуса. Формальное определение языков программирования.

  53. Формальные языки и грамматики Порождающая грамматика. Классификация грамматик по Хомскому

  54. Контекстно-свободные грамматики и их свойства: Основные понятия, приведение КС-грамматик

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



Примерный перечень экзаменационных задач по дисциплине «Дискретная математика»


  1. Сколько 5-ти разрядных чисел можно составить из 10 цифр.

  2. Кодовый замок имеет 5 одинаковых ячеек, каждая ячейка может быть установлена в одно из 6 устойчивых положений. Сколько различных комбинаций нужно перебрать (максимальное количество), чтобы не зная кода, открыть кодовый замок?

  3. В эстафете 100+200+400+800 метров на первую позицию тренер может выставить одного из 3 бегунов, на вторую – одного из 5, на третью – одного из 6, на четвертую – единственного бегуна (на каждую позицию выставляются разные бегуны). Сколько вариантов расстановки участников эстафетного забега может составить тренер?

  4. На дискотеку пришло 13 девушек и 15 юношей. Объявлен “белый” танец. Все девушки выбрали для танцев юношей (и никто из них не отказался). Сколько могло образоваться танцующих пар?

  5. В заезде на ипподроме участвуют 12 рысаков. Играющие в тотализатор заполняют карточки, в которых указывают порядок, в котором, по их мнению, рысаки прийут к финишу. Будем считать, что к финишу одновременно не могут придти два и более рысаков. Сколько вариантов заполнения карточек существует?

  6. Рыбаки поймали 5 подлещиков, 4 красноперки и 2 уклейки, посолили и вывесили на солнце сушиться. Сколько вариантов развешивания рыбы на нитке?

  7. Пароль состоит из двух букв, за которыми следуют 4 цифры или из 4 букв, за которыми следуют 2 цифры. Сколько можно составить разных паролей, если из 33 букв русского алфавита используются только буквы: а, б, в, г, д, е, ж, и, к, л, м, н, п, р, c, т и все десять цифр? А сколько можно получить разных паролей, если из множества букв исключить дополнительно буквы а, е и с, а к 10 цифрам добавить символ *?

  8. Найти количество чисел, не делящихся на 3, 5, 7, в диапазоне от 200 до 500?

  9. Требуется купить 7 пирожных. В магазине имеются пирожные следующих видов: эклеры, песочные, слоеные и наполеоны. Сколько вариантов выбора?

  10. В середине 60-х годов в России появились две лотереи, которые по недоразумению были названы “Спортлото”: лотерея 5/36 и 6/49. Рассмотрим одну из них, например, 6/49. Играющий покупает билет, на котором имеется 49 клеточек. Каждая клеточка соответствует какому-либо виду спорта. Нужно выделить (зачеркнуть) 6 из этих клеточек и отправить организаторам лотереи. После розыгрыша лотереи объявляются шесть выигравших номеров. Награждается угадавший все шесть номеров, пять номеров, четыре номера и даже угадавший три номера. Соответственно, чем меньше угадано номеров (видов спорта), тем меньше выигрыш. Подсчитайте, сколько существует разных способов заполнения карточек “Спортлото” при условии, что используется лотерея 6/49.

  11. Задача о львах и тиграх. Имеется m львов и n тигров. Необходимо их расставить в ряд, но при этом известно, что тигр не может идти спокойно за тигром. Сколько существует вариантов расстановки, если тигры обезличенные?

  12. Задача о книжной полке. Из m книг, стоящих на полке, нужно выбрать k таких, которые не стояли рядом на книжной полке. Сколько вариантов выбора?

  13. 9 верблюдов идут гуськом. Сколько существует комбинаций перестановки верблюдов, при которых ни один верблюд не идет за тем, за кем шел ранее.

  14. Имеются марки достоинством в 4, 6, 10 копеек. На конверт нужно наклеить марки так, чтобы сумма составляла 18 копеек. Будем считать, что порядок наклеиваемых марок важен, т. е. способы наклейкимарок достоинством в 4, 10, 4 копейки и 10, 4, 4 разные способы.

  15. Имеется n участников шахматного турнира. Сколько партий должно быть сыграно, чтобы каждый участник сыграл со всеми остальными?

  16. Доказать что A \ (B C) = (A \ B) (A \ C);

  17. Пусть A и B – конечные множества, m = |A|, n = |B|. Сколько существует бинарных отношений между A и B? Сколько имеется функций из A в B? Сколько имеется инъекций из A в B при m n?

  18. Доказать, что (A B) (C D) (A C) (B D)). При каких A, B, C и D получается равенство?

  19. Доказать, что пересечение отношений порядка является отношением порядка. Всегда ли объединение отношений порядка является отношением порядка.

  20. Сколько подмножеств множества A={1,2,∙∙∙,300} состоят из чисел кратных 4 и, сверх того, содержат по крайней мере одно число кратное 6 ?

  21. Скольким способами можно раскрасить 4 полосы флага в 7 цветов, так, чтобы рядом находящиеся полосы имели различные цвета?

  22. Сколько семизначных чисел (не начинающихся с 0) состоят из различных цифр?

  23. Доказать, что если R – отношение порядка, то R-1 – отношение порядка.

  24. Сколько существует последовательностей, состоящих из p знаков плюс и q знаков минус, в которых нигде рядом не окажутся два знака минус .

  25. Найти коэффициент при в разложении степени в сумму однородных одночленов.

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

  27. Доказать, что среди 6 человек найдется тройка знакомых, или тройка незнакомых людей.

  28. Найти хроматическую функцию полного графа Kn .

  29. Докажите, что дерево является двудольным графом.

  30. Нарисовать диаграмму Хассе множества делителей числа 360, упорядоченного отношением делимости.

  31. Распаковать код Прюфера 12579213 и проверить полученное дерево упаковкой.



  1. Ресурсное обеспечение курса

    1. Список основной учебно-методической литературы


1 Новиков, Ф.А. Дискретная математика для программистов / Ф.А. Новиков. - СПб: Питер, 2007. – 304с.

2 Давыдова Е.М., Леденева Т.М., Мещеряков Р.В., Подвальный С.Л. Дискретная математика. Учебник. Гриф СибРОУМО. Издание 2-ое переработанное и дополненное. - Томск: Изд-во "В-Спектр", 2006.-288с.




5.2. Список дополнительной учебно-методической литературы


1 Яблонский, С.В. Введение в дискретную математику / С.В. Яблонский. - М.: Наука, 1986. – 384с.

2 Кнут Д. Искусство программирования для ЭВМ. Т. 1: Основные алгоритмы. – М.: Издательский дом «Вильямс», 2000. – 720 с.

3 Кнут Д. Искусство программирования для ЭВМ. Т. 2: Структуры данных. – М.: Издательский дом «Вильямс», 2000. – 832 с.

4 Кнут Д. Искусство программирования для ЭВМ. Т. 3: Поиск и сортировка. – М.: Издательский дом «Вильямс», 2000. – 832 с.

5 Лавров И. А. Задачи по теории множеств, математической логике и теории алгоритмов / И. А. Лавров, Л. Л. Максимова – М.: Наука, 1995. – 268с.

6 Стенли Р.П. Перечислительная комбинаторика / Р.П. Стенли – М.: Наука, 2000. – 400с.

7 Риордан Дж. Введение в комбинаторный анализ / Дж. Риордан – М.:ИИЛ. 1958. – 287с.

8 Иванов Б.Н. Дискретная математика. Алгоритмы и программы: Учеб. пособие / Б.Н. Иванов – М.: ЛБЗ, 2003. - 288с.

9 Зелковец М и др. Принципы разработки программного обеспечения: Пер. с англ./М.Зелковиц, А.Шоу, Дж.Гэннон. – М.:Мир, 1982. – 368с.

10 Вирт Н. Систематическое программирование. Введение: Пер. с англ./Под ред. Ю.М.Баяновского. – М.:Мир, 1977. – 180с.

11 Петрова А.Н. Теория языков программирования и методы трансляции. Ч I – Теория: Учеб. пособие. – Комсомольск-на-Амуре: ГОУВПО «КнАГТУ», 2004 – 110с.

12 Петрова А.Н. Теория языков программирования и методы трансляции. Ч II – Руководство к курсовой работе: Учеб. пособие. – Комсомольск-на-Амуре: ГОУВПО «КнАГТУ», 2004 – 75с.



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

дисциплины

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


  1. Операционная системы: Windows (XP/2000/2003).

  2. Текстовый редактор MS Word 2000.

  3. Офисный пакет Microsoft Office 2003

Похожие:

Рабочая программа дисциплины «Дискретная математика» iconУчебная программа Дисциплины б4 «Дискретная математика» по специальности 090302 «Информационная безопасность телекоммуникационных систем»
Целью преподавания дисциплины «Дискретная математика» является подготовка специалистов к деятельности в сфере разработки, исследования...
Рабочая программа дисциплины «Дискретная математика» iconРабочая программа учебной дисциплины оп. 08 Дискретная математика

Рабочая программа дисциплины «Дискретная математика» iconРабочая программа учебной дисциплины (модуля) дискретная математика для направления
Компетенции студента, формируемые в результате освоения учебной дисциплины
Рабочая программа дисциплины «Дискретная математика» iconПрограммы учебной дисциплины «Дискретная математика и математическая логика и их приложения в информатике и компьютерных науках»
«Дискретная математика и математическая логика и их приложения в информатике и компьютерных науках»
Рабочая программа дисциплины «Дискретная математика» iconДискретная математика
Общая трудоемкость дисциплины составляет 5 зачетных единиц, 180/ 72 общих/ аудиторных часов
Рабочая программа дисциплины «Дискретная математика» iconПрограмма дисциплины «Дискретная математика»
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 230100. 62 «Информатика...
Рабочая программа дисциплины «Дискретная математика» iconРабочая программа дисциплины Дискретная математика для подготовки специалиста по специальности 030100 «Информатика»
Целью курса является выделение некоторых дискретных задач и изучение общих методов решения дискретных задач на примерах выделенных...
Рабочая программа дисциплины «Дискретная математика» iconПрограмма дисциплины «Дискретная математика»
Курс дискретной математики – это сравнительно молодой раздел математики. Бурное развитие дискретной математики в последнее время...
Рабочая программа дисциплины «Дискретная математика» iconПрограмма государственного экзамена по математике по направлению подготовки 01. 03. 02. Прикладная математика и информатика саранск 2014 раздел «дискретная математика»
Оценки сложности днф. Сокращенные, тупиковые, минимальные дизъюктивные нормальные формы, и алгоритмы их построения
Рабочая программа дисциплины «Дискретная математика» iconДискретная математика

Разместите кнопку на своём сайте:
docs.likenul.com


База данных защищена авторским правом ©docs.likenul.com 2015
обратиться к администрации
docs.likenul.com