Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Примерная программа'
Примерная программа дисциплины “Менеджмент» федерального компонента цикла ОПД составлена в соответствии с государственным образовательным стандартом ...полностью>>
'Документ'
«Без стремления к методической работе учитель неизбежно попадает во власть трех демонов: механистичности, рутинности, банальности. Он деревенеет, кам...полностью>>
'Автореферат'
Защита диссертации состоится 27 декабря 2006 года в 10.30 на заседании диссертационного совета К 212.174.03 при Новосибирском государственном универс...полностью>>
'Решение'
Положение о порядке вcтупления юридических лиц и индивидуальных предпринимателей в члены некоммерческого партнерства «Первая Национальная Организация...полностью>>

Программа дисциплины «Дискретная математика» Индекс дисциплины по учебному плану ен. Ф. 01. 2 Направление 230200 Информационные системы

Главная > Программа дисциплины
Сохрани ссылку в одной из сетей:

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

Самарский государственный архитектурно-строительный университет

Факультет информационных систем и технологий

Утверждаю

Декан факультета ИСТ

Пиявский С.А.

ПРОГРАММА ДИСЦИПЛИНЫ

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

Индекс дисциплины по учебному плану ЕН.Ф.01.2

Направление 230200 Информационные системы

Специальность 230201 Информационные системы и технологии

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

Всего часов на дисциплину: 156

В том числе

Аудиторных часов – 86

Самостоятельная работа студента – 71 час

Форма итогового контроля: экзамен

Курс(ы) обучения – 2

Семестр(ы) обучения – 3

Разработана: к.ф.-м.н., доц. каф. ПМ и ВТ ________________________ Трусова А.Ю.

Рассмотрена и одобрена на заседании кафедры ПМ и ВТ

от “ 30 “ ___09_____2009 г., протокол №____2________

Зав. кафедрой ____________ ________________________ Пиявский С.А.

Рассмотрена и одобрена на заседании методической комиссии

по специальности № 230201

от “ 30 “ ____09____2009 г., протокол №____2________

Председатель методической комиссии _________________ _____________ Пиявский С.А.

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

Курс дискретной математики – это сравнительно молодой раздел математики. Бурное развитие дискретной математики в последнее время связано с развитием вычислительной техники.

Преподавание дисциплины имеет следующие цели:

  • формирование у студентов представлений о законах дискретной математики и применении этих законов при решении задач,

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

После изучения курса студенты должны:

  • иметь представление о строении дискретной математики, как науки

  • знать основные понятия дискретной математики,

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

  • уметь определять свойства заданного отношения

  • иметь представление об изоморфизме алгебр

  • уметь решать задачи методом математической индукции

  • знать основные принципы организации перебора вариантов и уметь применять их на практике

  • уметь решать «ключевые» задачи теории множеств и теории графов.

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

2. Содержание дисциплины

2.1. Объем дисциплины и виды учебной работы (час.)

ОЧНАЯ ФОРМА ОБУЧЕНИЯ, 3-й семестр –экзамен

Вид учебных занятий

Количество часов

Всего часов аудиторных занятий

86

Лекции

52

Практические занятия (семинары)

34

Лабораторные занятия

-

Всего часов самостоятельной работы

71

Подготовка к лекционным и практическим занятиям

Подготовка к экзамену

Всего часов по дисциплине

2.2. Разделы дисциплины и виды занятий

N П/п

Раздел дисциплины

Лекции

Практ. занятия

1

Множества. Отношения

8

8

2

Элементы комбинаторного анализа.

10

8

3

Отображение.

8

4

4

Основные понятия общей алгебры

8

4

5

Элементы теории графов.

10

6

6

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

8

4

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

1. Множества. Способы задания множеств. Операции над множествами. Декартово произведение множеств. Отношения. Способы задания отношений. Операции над отношениями. Примеры отношений. Операции из теории множеств, удовлетворяющие отношению эквивалентности. Замыкание отношений. Графическое представление отношений. Отношение порядка. Аксиоматика Цермеля-Френкеля.

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

3. Отображение. Способы задания отображений. Инъекция. Сюръекция. Биекция. Принцип биекции. Разложение целых чисел. Мультимножества и действия над ними. Числа Стирлинга. Числа Белла. Естественная факторизация отображений. Прообразы и образы. Естественная факторизация. Число сюръекций. Числа Стирлинга первого рода. Оценки и асимптотики для комбинаторных чисел.

4. Основные понятия общей алгебры. Универсальные алгебры. Общие сведения. Гомоморфизмы универсальных алгебр. Язык (алгебра) термов. Произвольные операции и конечные алгебры. Свободные алгебры: а) абсолютно свободные алгебры; б) свободный группоид; в) свободные полугруппы; г) свободная коммутативная полугруппа; д) свободные группы; е) свободные абелевы группы; ж) свободное кольцо. Векторные пространства. Булева алгебра. Законы булевой алгебры. Приведение к конъюнктивно нормальной форме. Принцип двойственности. Принцип двойственности в булевой алгебре. Алгебра Жегалкина.

5. Элементы теории графов. Определение графов и их разновидности. Лемма о рукопожатии. Разновидности графов. Изоморфизм графов. Подграфы. Операции над графами. Свойства графов. Эйлеровы графы. Задача Эйлера для кёнигсбергских мостах. Теорема Флери. Гамильтоновы графы. Некоторые свойства гамильтоновых графов. Матрицы графов. Деревья и лес. Покрывающее дерево связного графа. Планарность и укладка графов. Жорданова кривая на плоскости. Теорема Жордана. Гомеоморфность графа. Теорема Понтрягина-Куратовского. Грани плоского графа. Формула Эйлера. Раскраска графов. Хроматическое число. Правильная раскраска. Хроматические числа некоторых графов. Деревья и сети. Укладка корневого дерева. Код дерева. Двухполюсные сети (основные понятия). Разложение сетей.

6. Теория кодирования. Понятие сообщения. Способы описания источника сообщения. Алфавитное кодирование и декодирование. Критерий однозначности декодирования. Инверсный подход. Теорема Маркова. Алгоритм распознавания однозначного декодирования. Неравенство МакМилана. Коды с минимальной избыточностью (Коды Хоффмана). Алгоритм Хоффмана. Самокорректирующиеся коды. Типы ошибок. Помехоустойчивое кодирование. Сжатие данных. Методы аддитивного сжатия.

Перечень практических занятий

Наименование темы занятия

Номер темы программы

№ неде-ли

1

Множества. Способы задания множеств.

1

2

Операции над множествами.

Декартово произведение множеств.

1

3

Отношения. Способы задания отношений. Операции над отношениями.

1

4

Отношение эквивалентности. Замыкание отношений.

1

5

Основное правило комбинаторики. Правило суммы. Число различных к-элементных подмножеств n-элементного множества.

2

6

Геометрическая интерпретация. Формула симметрии. Формула сложения. Свойство числа сочетаний. Число подмножеств данного множества. Перестановки и размещение упорядоченных множеств.

2

7

Перестановки с повторениями. Размещение элементов множества.

Комбинации элементов с повторениями.

2

8

Бином Ньютона. Полиномиальная теорема. Свойства биномиальных коэффициентов. Свойства биномиальных коэффициентов. Метод включений и исключений.

2

9

Способы задания отображений. Инъекция. Сюръекция.

Биекция. Разложение целых чисел. Мультимножества и действия над ними.

3

10

Числа Стирлинга. Числа Белла. Число сюръекций. Числа Стирлинга первого рода.

3

11

Булева алгебра. Законы булевой алгебры. Приведение к конъюнктивно нормальной форме. Принцип двойственности.

4

12

Алгебра Жегалкина.

4

13

Лемма о рукопожатии. Разновидности графов. Изоморфизм графов. Подграфы. Операции над графами. Свойства графов. Эйлеровы графы. Задача Эйлера о кёнигсбергских мостах. Теорема Флери. Гамильтоновы графы. Матрицы графов.

5

14

Деревья и лес. Покрывающее дерево связного графа. Планарность и укладка графов. Гомеоморфность графа. Грани плоского графа. Формула Эйлера. Раскраска графов. Хроматическое число. Правильная раскраска. Хроматические числа некоторых графов.

5

15

Деревья и сети. Укладка корневого дерева. Код дерева. Двухполюсные сети (основные понятия). Разложение сетей.

5

16

Алфавитное кодирование и декодирование. Критерий однозначности декодирования. Инверсный подход. Теорема Маркова. Алгоритм распознавания однозначного декодирования.

6

17

Неравенство МакМилана. Коды с минимальной избыточностью (Коды Хоффмана). Алгоритм Хоффмана. Самокорректирующиеся коды. Типы ошибок. Помехоустойчивое кодирование. Сжатие данных. Методы аддитивного сжатия.

6



Скачать документ

Похожие документы:

  1. Программа дисциплины «вычислительная математика» Индекс дисциплины по учебному плану: ен. Ф. 01. 4 Направление 230200 Информационные системы

    Программа дисциплины
    Программа курса разработана в соответствии с Государственным образовательным стан­дар­том выс­­шего профессионального образования по направлению 230200 «Информационные системы», по специальности 23201 «Информационные системы и технологии»,
  2. Рабочая программа дисциплины «Математическая логика и теория алгоритмов»

    Рабочая программа
    Цель дисциплины – ознакомление с основными понятиями и методами математической логики и теории алгоритмов с ориентацией на их использование в практической информатике и вычислительной технике.
  3. Основная образовательная программа высшего профессионального образования Направление подготовки 230200 Информационные системы

    Основная образовательная программа
    Инженер по направлению подготовки 230200 - Информационные системы в соответствии с требованиями «Квалификационного справочника должностей руководителей, специалистов и других служащих», утвержденного Постановлением Минтруда России от 21.
  4. Образовательной программы по направлению подготовки 230200 Информационные системы

    Документ
    Специфика артикуляции звуков, интонации, акцентуации и ритма нейтральной речи в изучаемом языке; основные особенности полного стиля произношения, характерные для сферы профессиональной коммуникации; чтение транскрипции.
  5. Государственный образовательный стандарт высшего профессионального образования направление подготовки (1)

    Образовательный стандарт
    1.1. Направление подготовки 230200 - Информационные системы утверждено приказом Министерства образования Российской Федерации от 12 января 2005 г. № 4.

Другие похожие документы..