 |
Распределение часов по видам занятий
|
|
|
|
ДИСКРЕТНАЯ МАТЕМАТИКА
По специальностям
5В070400 «Вычислительная техника и программное обеспечение»,
5В070300 «Информационные системы»,
5В100200 «СИСТЕМЫ ИНФОРМАЦИОННОЙ БЕЗОПАСНОСТИ»
Всего 3 кредита
Лекций – 1.5 кредита
Практические занятия – 1.5 кредита
Расчетно-графические работы (типовые расчеты)-3 в четвертом семестре
Форма отчетности:
Экзамен – 1 в четвертом семестре
Алматы 2012г.
Силлабус разработан на основании рабочей программы дисциплины, утвержденной деканом факультета радиотехнического факультета (протокол № 2 от 20.06.2012 г.)
Разработала: Астраханцева Л.Н., доцент
Силлабус рассмотрен и одобрен на заседании кафедры «Высшая математика» от 18.06.2012 г., протокол
№ 10
Зав. кафедрой _________________________ Байсалова М.Ж.
ВВЕДЕНИЕ
Дисциплина «Дискретная математика» является неотъемлемой частью математического образования будущих инженеров. Аппарат дискретной математики является основным инструментом исследования специалистов, занимающихся созданием и эксплуатацией компьютеров, языков программирования, средств передачи и обработки информации, автоматизированных систем управления и проектирования, а язык дискретной математики – это язык, который используется в научной и технической литературе по данным проблемам.
ЦЕЛИ И ЗАДАЧИ
Дисциплина «Дискретная математика» посвящена той области математики, которая привлекается при решении задач на компьютере в терминах аппаратных средств и программного обеспечения с привлечением организации символов и манипуляции данными.
Цель преподавания дисциплины - вооружение будущих инженеров современным математическим аппаратом, который можно определить как взаимосвязанную совокупность языка, моделей и методов математики, ориентированную на решение прикладных задач, возникающих в области информационных технологий, формирование у студентов знаний и умений, которые образуют теоретический фундамент, необходимый для корректной постановки и решения проблем в области информатики, для осознания целей и ограничений при создании структур, алгоритмов и программ обработки информации.
|
|
|
В результате изучения дисциплины студенты должны овладеть основными методами формализации рассуждений, получить навыки моделирования для использования их в программировании, при решении задач в области искусственного интеллекта, при доказательстве правильности программ, при построении математических моделей.
Пререквизиты -алгебра, геометрия в объеме школьного курса, желательно знакомство со следующими разделами математики: линейной алгеброй, математического анализа и наличие навыков программирования для реализации алгоритмов.
Постреквизиты -общетехнические и специальные дисциплины по информационным технологиям, такие как алгоритмические языки программирования, системное программирование, методы проектирования программ и систем, базы данных и базы знаний, интеллектуальные информационные системы.
| № | Список преподавателей | Должность |
| Астраханцева Людмила Николаевна | Доцент | |
| Байсалова Маншук Жумамуратовна | Доцент | |
| Ким Регина Евгеньевна | Доцент | |
| Жахаев Бекзат Копжасарович | ассистент |
СОДЕРЖАНИЕ ДИСЦИПЛИНЫ «ДИСКРЕТНАЯ МАТЕМАТИКА»
Распределение часов по видам занятий
| № | Название модуля (типового единичного цикла РПС) | Кол. Часов лекций | Кол. Часов прак.зан | Кол. РГР | СРСП | Кол. Час. СРС |
| Множества, отношения | ||||||
| Элементы математической логики | ||||||
| Графы | ||||||
| Итого за 1 семестр |
|
|
|
ПРОГРАММА ЛЕКЦИЙ
| № Лекции | № нед | Тема лекций | № источника |
| МОДУЛЬ 1 Множества и операции над множествами. Способы создания множеств. Булеан множств. Универсум. Диаграмма Эйлера. Прямое произведение множеств. | 15,1,3,10 | ||
| Соответствия, отображения, функции. Взаимооднозначные соответствия и мощности множеств. Счетные множества, теоремы о счетных множествах. Множества мощности континуума, теорема Кантора. | 15,1,3,10 | ||
| Отношения. Унарные, бинарные, тернарные отношения. Способы задания бинарных отношений и их свойства. Специальные бинарные отношения. | 15,1,3,10 | ||
| МОДУЛЬ 2 Логика высказываний. Логические операции. Формулы логики высказываний. Равносильность формул. Нормальные формы формул, приведение к ДНФ и КНФ.. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы. Разрешимость. Булева алгебра. Логические функции одной и двух переменных. Суперпозиции функций и формулы. | 15,1,2,3 | ||
| Полные системы логических функций. Теорема Поста о функциональной полноте. Минимизация в классе дизъюнктивных нормальных форм. Исчисление высказываний. Аксиоматические теории. Выводимость формул исчисление высказываний. Теорема дедукции. Логика и исчисление предикатов. Предикаты, кванторы. Формулы логики предикатов. Равносильность формул, выполнимость, общезначимость. Аксиомы исчисления предикатов. Эффективная вычислимость. Простейшие функции, операторы суперпозиции и примитивной рекурсии, примитивно-рекурсивные функции. Оператор минимизации, частично-рекурсивные функции. Тезис Черча. | 15,1,2,3 | ||
| МОДУЛЬ 3 Группы. Циклические группы. Группы подставонок. Кольца и поля. Элементы теории кодирования. Расстояние Хемминга.. Теоремы о корректирующей способности кодов. Матричное кодирование. Групповые коды. Коды Хемминга. | 15,1,2,3 | ||
| Комбинаторика. Правила суммы, произведения. Размещения и сочетания. Размещения и функциональные отображения. Перестановки и подстановки. Разбиения. Формула включений и исключений. Теория графов. Основные понятия и определения теории графов. Смежность, инцидентность, степени. Способы задания графов. | 15,1,2,3 | ||
| Операции над графами. Части графов. Связность, компоненты связности. Числа графов: цикломатическое, хроматическое, внешней и внутренней устойчивости. | 15,1,2,3 | ||
| Деревья, свойства деревьев. Остовные деревья. Минимальные остовные деревья нагруженных графов.Поиск маршрутов в графе. Задача о минимальном соединении. Задача о кратчайшем пути. | 15,1,2,3 | ||
| Эйлеровы цепи и циклы. Гамильтоновы цепи и циклы. Плоские графы. Теорема Понтрягина-Куратовского. | 15,1,2,3 | ||
| Транспортные сети. Поток в транспортной сети. Разрез, пропускная способность разреза. Алгоритм Форда-Фалкерсона построения максимального потока. | 15,1,2,3 |
Тема практического занятия
|
|
|
| № прак | № нед | Тема практического занятия | № источн |
| МОДУЛЬ 1 Множества, способы задания, операции над множествами. Доказательство тождества алгебры множеств. | 15,1,3,10,4 | ||
| Отношения, области определения и значения отношений. Способы задания, свойства отношений и операции над ними. | 15,1,3,10,4 | ||
| МОДУЛЬ 2 Логика высказываний. Запись составных высказываний в виде формул. Равносильные преобразования формул логики высказываний, доказательство равносильностей. | 15,1,3,10,4 | ||
| Использование логики высказываний в теории электрических цепей. Упрощение контактных систем. Приведение к ДНФ и КНФ. | 15,1,3,10,4 | ||
| Логические функции. Нормальные формы логических функций. Представление логических функций в различных базисах. Исследование систем логических функций на полноту. Формулы исчисления высказываний. Выводимость формулы из совокупности формул. Правила выводимости. | 15,1,3,10,4 | ||
| Логические и кванторные операции над предикатами. Равносильные формулы логики предикатов. Автоматическое доказательство теорем. Метод резолюций Кодирование. Коды с минимальной избыточностью. Алгоритмы Фано, Хаффмена.. | 15,1,3,10,4 | ||
| Помехоустойчивое кодирование. Код Хемминга. Решение различных комбинаторных задач. | |||
| Приведение к ДНФ и КНФ. Совершенные ДНФ и КНФ. Минимизация в классе ДНФ. Карты Карно. Коммутационные схемы. | 15,1,2,3,4 | ||
| Формулы исчисления высказыван. Выводимость. Кодирование. Комбинаторные задачи. | 15,1,2,3,4 | ||
| МОДУЛЬ 3 Способы задания графов. Операции над графами. Представление графов в компьютерах. Алгоритмы обхода вершин графа. Нахождение чисел графа, определение радиуса, диаметра, центра. Нахождение остовного дерева наименьшего веса. Алгоритм Краскала. | 15,1,2,3,4 | ||
| Нахождение кратчайшего пути в графе. Алгоритмы Флойда и Дейкстры. Эйлеровы графы. Гамильтоновы циклы. Задача коммивояжера. | 15,1,2,3,4 | ||
| Нахождение максимального потока в транспортной сети. | 15,1-4 |
|
|
|
|
|
|
