Учебная программа дисциплины ен. Р. 06. Дискретная математика Специальность: 080801 Прикладная информатика (в образовании) Квалификация: Информатик в образовании

Вид материала

Программа дисциплины

Содержание Специальность: 080801 Прикладная информатика (в образовании) Квалификация: Информатик в образовании I. организационно-методический раздел 2. Цель дисциплины 3. Задачи дисциплины 4. Принципы отбора содержания и организации учебного материала 5. Требования к освоению содержания дисциплины 6. Виды контроля 7. Планирование содержания дисциплины Ii. содержание дисциплины Модуль №4. Элементы математической логики Основные понятия Iii. организация самостоятельной работы Iv. контроль качества освоения дисциплины 2. Рубежный контроль. V. учебно-методическое обеспечение дисциплины 2. Электронно-программные средства.

Подобный материал:

• Специальность 080801. 65 (351400) – Прикладная информатика в экономике квалификация, 85.63kb.
• Программа итогового экзамена по информатике для специальности «080801 Прикладная информатика, 350.58kb.
• Учебная программа дисциплины сд. Ф. 03. Мировые информационные ресурсы Специальность:, 87.85kb.
• Программа по курсу "Математика. Алгебра и геометрия" для специальности 080801 (351400), 143.45kb.
• Программа дисциплины ен. Математика для студентов специальности 080801 «Прикладная, 247.77kb.
• Рабочая программа по дисциплине «логика» для специальности 351400 Прикладная информатика, 292.77kb.
• Рабочая программа по дисциплине «теория алгоритмов и сложности» для специальности 351400, 390.46kb.
• Рабочая программа учебной дисциплины «Математика» Специальность «Прикладная информатика, 322.42kb.
• Рабочая программа по дисциплине "алгоритмизация и программирование" для специальности, 136.39kb.
• Программа дисциплины ф дифференциальные уравнения для студентов специальности 010501, 101.63kb.

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

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

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

«Иркутский государственный педагогический университет»

Факультет математики, физики и информатики


Утверждено

на заседании совета факультета

математики, физики и информатики

протокол №­­­­­­_____от __________2006 г.

Председатель совета________________

(Кузьмина Н.Д.)

УЧЕБНАЯ ПРОГРАММА ДИСЦИПЛИНЫ

ЕН. Р.06. Дискретная математика

^ Специальность: 080801 Прикладная информатика (в образовании) Квалификация: Информатик в образовании


Курс: 1

Семестр: 1,2

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


Количество часов на дисциплину: 140 час.

Количество аудиторных часов: 88 час.; из них:

Лекций: 52 час.

Практических занятий: 36 час.

Самостоятельная работа: 52 час.


Итоговый контроль: зачет


^ I. ОРГАНИЗАЦИОННО-МЕТОДИЧЕСКИЙ РАЗДЕЛ

I. Место дисциплины

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

^ 2. Цель дисциплины

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

^ 3. Задачи дисциплины

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


^ 4. Принципы отбора содержания и организации учебного материала

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


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

Студент должен знать:

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

­ – определение булевых функций; существенные функции; представление булевых функций термами; суперпозиция функций, принцип двойственности; специальные представления булевых функций (дизъюнктивные преставления булевых функций, конъюнктивные представления булевых функций, полиномиальные представления булевых функций); понятия замкнутости и полноты множества булевых функций; предполные классы булевых функций, критерий полноты;

– способы задания графов; маршруты, цепи, циклы в графе; связные графы, эйлеровы цепи и циклы; плоские графы; раскраска графов; деревья, помеченные и непомеченные деревья, код Прюфера, деревья двоичного кода;

– блоковые коды; коды, обнаруживающие и исправляющие ошибки; минимальное расстояние кода; линейные коды, порождающая и проверочная матрицы; принцип максимума правдоподобия; декодирование линейного кода; коды Хэмминга и Рида-Маллера; мажоритарное декодирование;

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

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

– доказывать теоретические результаты;

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

– определять истинностное значения логических формул.

Студент должен владеть:

– навыками чтения учебной литературы;

– комбинаторными методами решения задач;

– техникой дискретных преобразований.


^ 6. Виды контроля

Текущий – проводится по каждой учебной единице в форме проверки домашнего задания.

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

Промежуточный – проводится в форме экзамена.

Итоговый – проводится в форме зачета.


^ 7. Планирование содержания дисциплины

№	Название модуля	Часы аудиторных занятий		Часы самостоятельной работы	Всего часов
		Лекции	Практ. Занятия
1	Элементы комбинаторики	12	8	14	34
2	Основы теории булевых функций	14	10	12	36
3	Основы теории графов и теории кодирования	12	8	14	34
4	Элементы математической логики.	14	10	12	36
	Итого	52	36	52	140

^ II. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ


Модуль №1. Элементы комбинаторики

1. Основные комбинаторные конфигурации.

Выборки: упорядоченные и неупорядоченные, с повторениями и без повторений, сочетания, размещения, перестановки. Правила суммы и произведения. Правило объединения.

2. Бином Ньютона.

Биномиальные коэффициенты. Основные тождества с биномиальными коэффициентами. Треугольник Паскаля. Полином. Полиномиальная формула. Полиномиальные коэффициенты. Простые тождества.

3. Принцип включения и исключения.

Приложения к теории множеств и теории чисел.

4. Производящие функции.

Получение n-го члена последовательности Фибоначчи с помощью производящих функций.


Модуль №2. Основы теории булевых функций

1. Определение и методы представления булевых функций.

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

2. Представление булевых функций термами.

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

3. Канонические формы булевых функций.

Понятие канонической формы для множества булевых функций. Совершенная дизъюнктивная нормальная форма, совершенная конъюнктивная нормальная форма, совершенная полиномиальная конъюнктивная форма, полином Жегалкина. Теоремы существования и единственности.


4. Замкнутые классы и полнота системы булевых функций.

Понятие замкнутого класса булевых функций. Замкнутые классы функций: линейные, самодвойственные, монотонные, сохраняющие константу 0 и сохраняющие константу 1. Понятие полноты системы булевых функций. Полнота одной системы булевых функций относительно другой. Свойства несамодвойственных, нелинейных, немонотонных функций. Критерий полноты.


Модуль №3. Основы теории графов и теории кодирования


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

Способы представления графов. Связные графы. Изоморфизм графов. Эйлеровы и гамильтоновы графы. Деревья. Планарные графы. Теорема Эйлера и ее следствия. Непланарность графов К₅ и К_3,3. Раскраска вершин и ребер графа. Двудольные графы.


2. Основы теории кодирования.

Линейные самокорректирующиеся коды. Блоковые линейные коды. Проверочная и порождающая матрицы кода. Параметры кода. Обнаружение и исправление ошибок. Декодирование. Принцип максимального правдоподобия. Код Хэмминга. Коды Рида-Маллера. Методы декодирования. Декодирование по синдрому. Алгоритм декодирования Рида.


^ Модуль №4. Элементы математической логики

1. Логика высказываний.

Язык высказываний. Семантика языка высказываний. Логическое следование. Равносильность. Основные эквивалентности. Исчисление высказываний. Доказательства. Нормальные формы.

2. Полнота и непротиворечивость исчисления высказываний (4 часа).

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


3, Логика предикатов.

Сигнатура. Алгебраические системы. Язык предикатов и его семантика. Интерпретации. Истинность на алгебраических системах. Исчисление предикатов. Кванторы. Доказательства. Равносильность. Основные эквивалентности.

.

4 Основы теории моделей и теории доказательств.

Теорнема Эрбрана. Теорема Левейгейма-Скулема. Теорема компактности. Элементарная эквивалентность. Примеры логико-математических теорий. Формальная арифметика. Теоремы Геделя, Черча, Тарского.


^ Основные понятия

Булево n-мерное пространство; булева функция; терм; суперпозиция; термальное представление функции; канонические формы; замкнутость; полнота; линейный блочный код; порождающая и проверочная матрицы кода; синдром кода; декодирование по синдрому; мажоритарное декодирование кодов; язык высказываний и язык предикатов; семантика языков; исчисление высказываний и предикатов; квантор.

^ III. ОРГАНИЗАЦИЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

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

А. Выборки: упорядоченные и неупорядоченные, с повторением и без повторений. Комбинаторные уравнения. Бином Ньютона. Полиномиальная формула.

В. Производящие функции

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

1). Изучить теоретический материал по литературе из основного списка [1, 2] и из дополнительного списка [7-9].

2). Выполнить задания, 50 задач по пункту А и 10 по пункту В.

Контроль. Решенные задачи сдаются на проверку преподавателю.

2. Основы теории булевых функций.
   

А. Задачи на представления булевых функций: построение n-мерного куба, n=2,3,4,5, код Грея, карта Карно, векторное задание функции.

В. Термальные представления. Основные термальные эквивалентности.

Нормальные формы. Канонические представления.

С. Пять замкнутых классов. Полнота системы функций.

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

1). Изучить теоретический материал по литературе из основного списка [1, 6,8] и из дополнительного списка [1,2].

2). Выполнить задания, всего 70 задач.

Контроль. Решенные задачи сдаются на проверку преподавателю.

2. Основы теории кодирования.
   

А. Линейный блоковый код как подпространство линейного векторного пространства над конечным полем. Строки порождающей матрицы — базисные вектора подпространства, ортогональное подпространство, проверочная матрица. Фактор-пространство. Синдром смежного класса. Декодирование по синдрому. Декодирование Рида.

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

1). Изучить теоретический материал по литературе из основного списка [4, 10, 11] и из дополнительного списка [3].

2). Выполнить задания, всего 30 задач.

Контроль. Решенные задачи сдаются на проверку преподавателю.

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

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

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

1). Изучить теоретический материал по литературе из основного списка [14- 16] и из дополнительного списка [10,11].

2). Выполнить задания, всего 30 задач.

Контроль. Решенные задачи сдаются на проверку преподавателю.


^ IV. КОНТРОЛЬ КАЧЕСТВА ОСВОЕНИЯ ДИСЦИПЛИНЫ


1. Текущий контроль.

Проводится по каждой учебной единице в форме проверки домашнего задания.

^ 2. Рубежный контроль.

Проводится по каждому из четырех модулей в форме контрольных работ с рейтинговой оценкой от 0 до 50 баллов. Темы контрольных работ «Комбинаторные задачи», «Булевы функции: представления, замкнутость, полнота», «Кодирование и декодирование, исправление ошибок», «Логические исчисления».

3. Итоговый контроль.

Проводится в форме экзамена и зачета.


^ V. УЧЕБНО-МЕТОДИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ


Рекомендуемая литература

Основная литература.

1. Пантелеев В.И. Лекции по дискретной математике. Учебное пособие. – Иркутск. Издательство Иркутского государственного педагогического университета, 2006.
   
2. Ежов И.И., Скороход А.В., Ядренко М.И. Элементы комбинаторики. М.: Наука, 1977.
   
3. Липский В. Комбинаторика для программистов. М.: Мир, 1970.
   
4. Яблонский С.В. Введение в дискретную математику. М.: Наука, 2001.
   
5. Новиков Ф.А. Дискретная математика для программистов. СПб: Питер, 2000.
   
6. Перязев Н.А. Основы теории булевых функций. М.: Физматлит, 1999.
   
7. Белоусов А.И., Ткачев С.Б. Дискретная математика. М.: Из-во МГТУ им. Баумана, 2002.
   
8. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004.
   
9. Зыков А.А. Основы теории графов. М.: Наука, 1987.
   
10. Мак-Вильямс Ф., Слоэн Н. Теория кодов, исправляющих ошибки. М.: Связь, 1979.
    
11. Пантелеев В.И. Помехоустойчивое кодирование – Иркутск. Издательство Иркутского государственного университета, 2001.
    
12. Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.: Физматлит, 1999.
    
13. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физматлит, 1995.
    
14. Непейвода Н.Н. Прикладная логика. – Новосибирск: Изд-во Новосибирского ун-та, 2000.
    
15. Гладкий А.В. Математическая логика. – М.: РГГУ, 1998.
    
16. Лавров И.А. Математическая логика. – М.: Академия, 2006.
    

Дополнительная литература.

1. Кузнецов О.П. Дискретная математика для инженера. – СПб.: Лань, 2004.
   
2. Бохман Д., Постхоф Х. Двоичные динамические системы. М.: Энергоатомиздат, 1986.
   
3. Лидл Р., Пильц Г. Прикладная абстрактная алгебра. Екатеринбург: Изд-во УГУ, 1996.
   
4. Мендельсон Э. Введение в математическую логику.
   
5. Новиков Ф.А. Дискретная математика для программистов. СПб: Питер, 2000.
   
6. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. – М.: Энергоатомиздат, 1988.
   
7. Райзер Г.Дж. Комбинаторная математика. М.: Мир, 1966.
   
8. Холл. М. Комбинаторика. М.: Мир, 1970.
   
9. Грэхем Р., Кнут. Д., Паташник О. Конкретная математика. Основание информатики.— М.: Мир, 1998.
   
10. Верещагин Н.К., Шень А. Языки и исчисления. – М.: МЦНМО, 2000.
    
11. Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс математической логики. – М.: Физматлит, 2002.
    

^ 2. Электронно-программные средства.


1. Компьютерное учебно-методическое пособие по основам теории булевых функций.

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

2. Библиотека книг по дискретной математике на электронном носителе

(имеется на кафедре математической информатики).

Составитель: профессор кафедры математической информатики, профессор, доктор физ.-мат. наук С.Ф.Винокуров; заведующий кафедрой математической информатики, профессор, доктор физ.-мат. наук Перязев Николай Алексеевич.

Утверждено

на заседании кафедры

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

(протокол № ___ от __________ 200_ г.)


Зав. кафедрой ______________________

Н.А.Перязев


Утверждено

на заседании УМС факультета

математики, физики и информатики

(протокол № ___ от ___________ 200_ г.)


Председатель УМС___________________

Н.Д. Кузьмина