Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Негосударственное образовательное учреждение
высшего профессионального образования
«санкт-петербургский гуманитарный университет профсоюзов»
|
Рассмотрено на заседании кафедры информатики и программирования Протокол №11 от 21 июня 2011 г. Зав. кафедрой _______________ Пискунова Т.Г. |
УТВЕРЖДАЮ Проректор по учебной работе ________________ Розова Т.А. «___»________________2011 г. |
Рабочая программа дисциплины
Дискретная математика
Направление подготовки Прикладная информатика
Профиль подготовки «Прикладная информатика в экономике»
Цели и задачи освоения дисциплины
Цель данного курса - овладение студентами знаниями по дисциплине «Дискретная математика», предусмотренными типовыми образовательными программами.
Основная задача курса - развитие студентами навыков использования полученных знаний по дисциплине «Дискретная математика» в дальнейшей профессиональной деятельности.
Дисциплина «Дискретная математика» относится к базовой части математического и естественнонаучного цикла образовательной программы направления «Прикладная информатика».
Дискретная математика – область современной математики, занимающаяся изучением свойств дискретных структур, которые имеют место в многочисленных приложениях. В частности, дискретная математика является базой для изучения компьютерных и информационных технологий (теоретическая информатика, теория алгоритмов, теория кодирования, создание прикладного математического и программного обеспечения), для решения экономических задач (комбинаторный анализ, теория графов, решение многоэкстремальных задач), для дискретного имитационного моделирование и пр.
Требования к результатам освоения дисциплины:
Процесс изучения данной дисциплины направлен на формирование у студентов следующих основных компетенций (ФГОС ВПО по направлению 230700 – Прикладная информатика):
способность при решении профессиональных задач анализировать социально-экономические проблемы и процессы с применением методов системного анализа математического моделирования (ПК-2);
способность ставить и решать прикладные задачи с использованием современных информационно-коммуникационных технологий (ПК-4);
способность использовать современные методы и модели оценки качества и надежности при проектировании, разработке и отладке программных средств (ПК-7);
способность моделировать и проектировать структуры данных, прикладные и информационные процессы (ПК-9);
способность применять к решению прикладных задач базовые алгоритмы обработки информации, выполнять оценку сложности алгоритмов, программировать и тестировать программы (ПК-10);
способность применять методы анализа проблем на концептуальном, логическом, математическом и алгоритмическом уровнях (ПК-17);
аналитическая, научно-исследовательская деятельность.
В результате изучения дисциплины студент должен:
Знать:
основные понятия и результаты теории конечных множеств и отношений,
основные логические операции и формулы логики,
операции над вычетами и их свойства,
основы комбинаторики и теории графов,
сущность и содержание достижений в дискретной математике.
Уметь:
уметь выбирать методы моделирования систем,
структурировать и анализировать цели и функции систем управления,
проводить системный анализ прикладной области,
уметь пользоваться методами дискретной математики
Владеть: навыками моделирования прикладных задач с использованием методов дискретной математики.
Структура и содержание дисциплины (модуля)
Общая трудоемкость дисциплины составляет 4 зачетные единицы 144 часов.
Содержание разделов дисциплины/тем дисциплины
Тема 1. Основы теории множеств
Понятие множества. Конечные и бесконечные множества, пустое множество. Подмножество. Количество подмножеств конечного множества. Теоретико-множественные диаграммы. Операции над множествами (объединение, пересечение, дополнение, теоретико-множественная разность) и их свойства. Декартово произведение множеств. Декартова степень множества.
Тема 2. Основные логические операции. Формулы логики. Таблица истинности. Дизъюнктивная нормальная форма (ДНФ)
Дизъюнктивная нормальная форма {ДНФ}. Понятие высказывания. Основные логические операции (дизъюнкция, конъюнкция, импликация, эквивалентность, отрицание). Формулы логики. Таблица истинности и методика ее построения. Тождественно-истинные формулы. Понятие элементарного произведения. Методика построения таблицы истинности для ДНФ упрощенным методом.
Тема 3. Законы логики. Упрощение формул логики с помощью равносильных преобразований
Равносильные формулы и их свойства. Законы логики. Методика упрощений формул логики с помощью равносильных преобразований. Методика проверки двух формул с помощью их предварительного упрощения.
Тема 4. Проверка теоретико-множественных соответствий с помощью формул логики
Соответствие между теоретико-множественными и логическими операциями. Перевод теоретико-множественного выражения в соответствующую формулу логики. Проверка теоретико-множественных соотношений с помощью формул логики.
Тема 5. Основные понятия комбинаторики
Выборки, размещения, перестановки, сочетания, разбиения; их пересчет. Комбинаторный смысл биномиальных коэффициентов. Комбинаторный смысл полиномиальных коэффициентов и чисел Стирлинга. Метод включения-исключения и его применения. Формулы обращения.
Тема 6. Операции над предикатами и кванторами
Понятие предиката. Область определения и область истинности предиката. Обычные логические операции над предикатами. Кванторные операции над предикатами. Предикатные формулы, свободные и связанные переменные. Построение отрицаний к предикатам, содержащим кванторные операции. Формализация предложений с помощью логики предикатов. Следование одного предиката из другого, равносильность предикатов.
Тема 7. Алгебра вычетов по модулю
Вычет и система вычетов по модулю. Операции над вычетами (сложение, вычитание, умножение) и их свойства. Обратимые вычеты, критерии обратимости вычета; система обратимых вычетов по данному модулю. Решение уравнений типа ах+Ьх=с (где а - обратимый вычет) в алгебре вычетов.
Тема 8. Основы теории графов
Основные определения теории графов. Связные графы и компоненты связности графов. Двудольные графы. Бинарные деревья и их применения для хранения и поиска информации.
Тема 9. Элементы теории кодирования
Понятия кодирования и декодирования. Помехоустойчивое кодирование. Канал связи. Понятие криптологии, алфавитное кодирование. Проблема взаимной однозначности. Достаточный признак однозначности алфавитного кодирования. Алгоритм построения кода Хемминга и обнаружение в нем шибки.
Тема 10. Элементы теории автоматов
Понятие и определение конечного автомата. Способы задания конечного автомата, примеры конечного автомата. Каноническое уравнение автомата.
Тема 11. Элементы теории алгоритмов
Вычислимые функции и алгоритмы. Теория рекурсивных функций. Нормальный алгоритм Маркова. Машины Тьюринга.
Связи разделов с последующими дисциплинами
Все разделы курса «Дискретная математика» связаны в той или иной мере с обеспечивающими курсами линейной алгебры, математического анализа, математической статистики, теории вероятностей и используются в дисциплинах: связанных с компьютерными и информационными технологиями (теоретическая информатика, теория алгоритмов, теория кодирования, создание прикладного математического и программного обеспечения), для решения экономических задач (комбинаторный анализ, теория графов, решение многоэкстремальных задач), для дискретного имитационного моделирования и пр.
Примерные вопросы для подготовки к экзамену (зачету)
Учебно-методическое обеспечение дисциплины (модуля)
Основная литература
Дополнительная литература
Разработчик (автор):кафедра информатики и математики СПбГУП, доцент, к.ф.-м.н., Кучер А.И.
Контрольное задание по дискретной математике
1.Правильно ли рассуждение, имеющее форму: «Все X являются Y и некоторые Y являются Z; значит, все Z не являются X»?
2.Истинны ли высказывания:
3.
4. Преобразовать так, чтобы формула содержала только операции и
5. Двумя способами (равносильные преобразования и таблицы истинности) найти СКН и СДН – формы для
6.
7.
8.
Задать граф матрицами инцидентности и смежности, а также списком ребер.