Определение принадлежности булевых функций к пяти классам Поста. Применение аксиом алгебры логики, алгебры Жегалкина БХВ-Петербург, 2007.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте файл и откройте на своем компьютере.
ЮЖНО - УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ УТВЕРЖДАЮ: Директор института Высшая школа электроники и компьютерных наук ___________Г. И. Радченко 23.06.2017 РАБОЧАЯ ПРОГРАММА к ОП ВО от 17.10.2017 №007 - 03 - 0187 дисциплины В.1.06 Дискретная математика для направления 09.03.01 Информатика и вычислительная техника уровень бакалавр тип программы Академический бакалавриат профиль подготовки Автоматизированное управление бизнес - процессами и финансами форма обучения очная кафедра - разработчик Электронные вычислительные машины Рабочая программа составлена в соответствии с ФГОС ВО по направлению подготовки 09.03.01 Информатика и вычислительная техника, утверждённым приказом Минобрнауки от 12.01.2016 № 5 Зав.кафедрой разработчика, к.техн.н. (ученая степень, ученое звание) _____ 14.05.2017 ____ (подпись) К. А. Домбровский Разработчик программы, к.пед.н., доцент (ученая степень, ученое звание, должность) _____ 14.05.2017 ____ (подпись) Ю. Г. Плаксина СОГЛАСОВАНО Зав.выпускающей кафедрой Информационно - аналитическое обеспечение управления в социальных и экономических системах д.техн.н., проф. (ученая степень, ученое звание) _____ 14.05.2017 ____ (подпись) О. В. Логиновский Челябинск 1. Цели и задачи дисциплины Цель дисциплины "Дискретная математика" – изучение основных дискретных математических структур; развитие у студентов математической культуры, включающей в себя ясное понимание необходимости математической составляющей в общей профессиональной подготовке. Для достижения поставленной цели необходимо решить следующие задачи: - формирование первоначальных знаний, умений и навыков использования основных понятий теории множества, графов, теории дискретных функций; - обучение рациональному и эффективному использованию полученных знаний при решении типовых задач по дискретной математике; - формирование у студентов представление о дискретной математике как о способе изучения широкого круга объектов и процессов, характеризующихся отсутствием свойств непрерывности. Краткое содержание дисциплины Дискретная математика базируется на основных понятиях теории множеств, развивает их и является отправным пунктом для изучения методов и средств вычислительной техники, языков программирования, математического моделирования. Математический аппарат дисциплины можно определить как взаимосвязанную совокупность языка, моделей и методов математики, ориентированную на решение различных инженерных задач. В настоящее время знание дискретной математики необходимо специалистам в области IT - технологий. В процессе освоения дисциплины студенты изучают: роль и место дискретной математики в системе фундаментальных наук; способы задания множеств, основные операции над ними, отношения между элементами множеств, их свойства и виды отношений; отображения и функции, виды отображений, основные операции над отображениями; основные понятия переключательных функций; способы задания переключательных функций; основные понятия теории графов, связные графы, изоморфизм графов; методы решения экстремальных задач на графах, алгоритмы раскраски вершин и ребер графа. 2. Компетенции обучающегося, формируемые в результате освоения дисциплины Планируемые результаты освоения ОП ВО (компетенции) Планируемые результаты обучения по дисциплине (ЗУНы) ОК - 7 способностью к самоорганизации и самообразованию Знать:современные информационные ресурсы (в том числе интернет - источники) по предметной области. Уметь:представлять самостоятельно полученные результаты формализации информационных представлений и преобразований; формулировать полученные результаты. Владеть:навыками самостоятельной работы с научной и учебной литературой по предметной области; навыками оценивания результатов формальных преобразований. ПК - 1 способностью разрабатывать модели компонентов информационных систем, включая модели баз данных и модели интерфейсов Знать:методы формального представления информационных объектов и процессов; и способы их параметризации. О значении "человек - электронно - вычислительная машина" дискретной математики, ее место в системе фундаментальных наук и роли в решении практических задач; об истории развития и современных исследованиях дискретной математики; способы задания множеств, основные операции над ними, отношения между элементами множеств, их свойства и виды отношений; отображения и функции, виды отображений, основные операции над отображениями; основные понятия переключательных функций; способы задания переключательных функций; основные понятия теории графов, связные графы, изоморфизм графов; методы решения экстремальных задач на графах, алгоритмы раскраски вершин и ребер графа. Уметь:адекватно использовать и обосновывать применяемые методы формального представления информационных объектов и процессов; и способы их параметризации. Применять положения и методы дискретной математики для решения задач, относящимся к темам дисциплины; • находить различные формы булевых функций; применять булевы функций для построения схем из функциональных элементов и контактных схем; находить минимальные деревья, гамильтоновы и эйлеровы циклы, кратчайшие пути на графах. Владеть:навыками формального описания информационных объектов. Методами доказательства равенства множеств, свойств бинарных отношений; навыками минимизации булевых функций; различными способами задания графов и навыками вычисления их основных характеристик. ПК - 4 способностью готовить конспекты и проводить занятия по обучению работников применению программно - методических комплексов, используемых на предприятии Знать:методику подготовки конспекта; основные типы конспектов (опорные, плановые, текстуальные, свободные, тематические). Уметь:подготавливать конспекты разных типов; выбирать тип конспекта для изложения необходимого учебного материала . Владеть:навыками подготовки конспектов разных типов. 3. Место дисциплины в структуре ОП ВО Перечень предшествующих дисциплин, видов работ учебного плана Перечень последующих дисциплин, видов работ Нет В.1.13 Сети ЭВМ и телекоммуникации, ДВ.1.06.02 Элементы математической логики и теории множеств, ДВ.1.06.01 Математическая логика и теория алгоритмов, Б.1.17.01 Базы и хранилища данных, Б.1.13.03 Электроника и схемотехника, Б.1.17.02 Базы данных, В.1.09 Теория автоматов Требования к «входным» знаниям, умениям, навыкам студента, необходимым при освоении данной дисциплины и приобретенным в результате освоения предшествующих дисциплин: Нет 4. Объём и виды учебной работы Общая трудоемкость дисциплины составляет 4 з.е., 144 ч. Вид учебной работы Всего часов Распределение по семестрам в часах Номер семестра 2 Общая трудоёмкость дисциплины 144 144 Аудиторные занятия 72 72 Лекции (Л) 45 45 Практические занятия, семинары и (или) другие виды аудиторных занятий (ПЗ) 27 27 Лабораторные работы (ЛР) 0 0 Самостоятельная работа (СРС) 72 72 Работа с конспектами лекций. Подготовка к тестированию 8 8 Подготовка к практическим занятиям. Выполнение домашнего задания 12 12 Подготовка к экзамену 36 36 Подготовка конспекта лекций по темам вынесенным на самостоятельное изучение 16 16 Вид итогового контроля (зачет, диф.зачет, экзамен) - экзамен 5. Содержание дисциплины № раздела Наименование разделов дисциплины Объем аудиторных занятий по видам в часах Всего Л ПЗ ЛР 1 Элементы алгебры множеств 18 12 6 0 2 Элементы теории графов 26 18 8 0 3 Элементы алгебры логики 28 15 13 0 5.1. Лекции № лекции № раздела Наименование или краткое содержание лекционного занятия Кол - во часов 1 1 Введение. Структура раздела. Литература. Определение понятия формализация. Определение понятия множество, элементы множества. Способы задания множеств. Свойства множества. Примеры формального представления множеств. 2 2 1 Применение алгебры множеств для преобразования в формальных системах. Элементарные операции над множествами их практическая значимость и применение. Свойства элементарных операций над множествами. Отношения между множествами. Применение алгебры множеств при решении инженерных задач. 2 3 1 Понятие соответствия. Понятие отображения. Сюръективное, инъективное, биективное отображение. Понятие отношения. N – местное отношение. Бинарное отношение. 2 4 1 Тождественное отношение. Область определения и область значений бинарного отношения. Обратное отношение. Свойства отношений: рефлексивность, симметричность, транзитивность, антисимметричность. 2 5 1 Операции над отношениями: композиция отношений, замыкание отношений (рефлексивное, симметричное, транзитивное), разбиение множества. Отношение эквивалентности (свойства). Покрытие множества. Класс эквивалентности. 2 6 1 Отношение порядка. Частичный порядок. Транзитивность как наиболее важное свойство отношения порядка. Связь отношений < и <= . Полное отношение порядка. Частично упорядоченное множество. 2 7 2 Введение. Структура раздела. Литература. Графы как способ представления взаимосвязей объектов. Основные понятия и определения. Граф как нерефлексивное, симметричное отношение на конечном множестве. Понятие ребра, вершины. Понятие ориентированного графа. Виды графов (полный граф, мультиграф, псевдограф). 2 8 2 Степень вершины графа. Сумма степеней всех вершин. Четность количества вершин нечетной степени. Лемма о рукопожатии. Подграф. Остовный подграф. Суграф. 2 9 2 Операции над графами: объединения, пересечения, дополнения, удаления ребра, удаление вершины, добавления ребра, добавление вершины, стягивание, произведение графов. Понятие куба. 2 10 2 Свойства и характеристики графа: маршрут, путь (цепь), замкнутый путь (цикл), простой цикл. Ациклический граф. Достижимость вершин. Связный граф. Теорема о количестве маршрутов. Матрица связности. Число связности графа. Компоненты связности. 2 11 2 Полный граф. Двудольный граф. Полный двудольный граф. Определение планарного графа. Свойства планарного графа. Доказательство непланарности графов К(5) и К(3,3). Элементарное стягивание. Стягиваемый граф. Теорема Куратовского. 2 12 2 Раскраска графов. Хроматическое число графа. Теорема о хроматическом числе планарного графа (о четырех красках). Определение орграфа. Отличие от обыкновенного графа (наличие петель, дуги вместо ребер). Связность орграфа: слабая, односторонняя, сильная. Отношение эквивалентности и разбиение орграфа. Сильносвязные компоненты. 2 13 2 Актуальность задачи обхода графа. Обход графа по глубине. Обход графа по ширине. Эйлеровы, полуэйлеровы и неэйлеровы графы. Необходимое и достаточное условие эйлеровости графа. Задача о семи кенигсбергских мостах. Гамильтоновы, полугамильтоновы и негамильтоновы графы. 2 16 2 Задание логических функций в виде канонического полинома. Теоремы о суперпозиции и подстановке. Теорема о функциональной полноте; примеры функционально - полных базисов. Пять классов Поста. Разложения Шеннона. Декомпозиция булевых функций. 2 17 2 Минимизация логических функций. Этапы минимизации логических функций. Понятие простой импликанты. Методы получения сокращенной дизъюнктивной нормальной формы переключательной функции 2 14 3 Введение. Структура раздела. Литература. Алгебра логики (булева алгебра) 2 и ее разновидности. Общие сведения о логических функциях. Двоичная переменная логической функции. Способы задания функций алгебры логики. Элементарные логические функции. Число логических функций для n аргументов. Фиктивная переменная, вырожденная функция. 15 3 Аксиомы алгебры логики. Алгебра Жегалкина. Объединенная алгебра. Нормальные формы логических функций. Совершенные нормальные формы логических функций. Приведение нормальных форм логических функций к совершенному виду. 2 18 - 19 3 Метод простых импликант, метод Квайна, метод Блейка - Порецкого. 4 20 - 21 3 Методы получения тупиковой дизъюнктивной нормальной формы логической функции, минимальной дизъюнктивной нормальной формы переключательной функции (метод перебора, метод импликантных матриц, метод Петрика). 4 22 3 Минимизация переключательных функций с помощью карт Карно (диаграмм Вейча). 2 23 3 Минимизация переключательных функций с помощью карт Карно (диаграмм Вейча). 1 5.2. Практические занятия, семинары № занятия № раздела Наименование или краткое содержание практического занятия, семинара Кол - во часов 1 1 Парадоксы теории множеств.. 2 2 1 Операции на множествах и их свойства. Мощность и счетность множеств. Решение учебных примеров. 2 3 1 Свойства отношений: рефлексивность, симметричность, транзитивность. Построение отношений с заданными свойствами. Решение учебных примеров. Тест по разделу. 2 4 2 Операции над графами. Решение учебных примеров. 2 5 2 Построение подграфов. Компоненты связности. Решение учебных примеров. 2 6 2 Способы задания графов. Построение матриц смежности и инцидентности. Построение графов по матицам и наоборот. Решение учебных примеров. 2 7 2 Алгоритм Дейкстры, Флойда - Уоршала, Прима. Решение учебных примеров.Тест по разделу. 2 8 3 Правила записи двоичных наборов. Число переключательных функций для n аргументов. Построение таблиц истинности переключательных функций одного и двух переменных, определение фиктивной переменной, вырожденной функции. Правила записи конституент единицы (нуля). Правила записи ДНФ. Правила приведения ДНФ (КНФ) к совершенному виду. Решение учебных примеров. 2 9 3 Запись СДНФ в виде канонического полинома. Теорема о функциональной полноте. Определение принадлежности булевых функций к пяти классам Поста. Применение аксиом алгебры логики, алгебры Жегалкина, объединенной алгебры. Решение учебных примеров. 2 10 3 Этапы минимизации переключательных функций. Понятие простой импликанты. Методы получения сокращенной дизъюнктивной нормальной формы переключательной функции метод простых импликант, метод Квайна, метод Блейка - Порецкого. Решение учебных примеров. 2 11 - 12 3 Этапы минимизации переключательных функций. Методы получения тупиковой дизъюнктивной нормальной формы переключательной функции, минимальной дизъюнктивной нормальной формы 4 переключательной функции ( метод импликантных матриц, метод Петрика). Решение учебных примеров. 13 3 Этапы минимизации переключательных функций. Карты Карно (диаграммы Вейча). Решение учебных примеров.Тест по разделу. 3 5.3. Лабораторные работы Не предусмотрены 5.4. Самостоятельная работа студента Выполнение СРС Вид работы и содержание задания Список литературы (с указанием разделов, глав, страниц) Кол - во часов Изучение и конспектирование темы "Матрицы смежности и инцидентности графа/ографа" по второму разделу вынесенной для самостоятельного изучения Кузнецов, О.П. Дискретная математика для инженера. [Электронный ресурс] — Электрон. дан. — СПб. : Лань, 2009. — 400 с. — Режим доступа: http://e.lanbook.com/book/220 — Загл. с экрана 2 Изучение и конспектирование темы "Методы оптимизации на графах. Алгоритм Дейкстры, Флойда - Уоршала, Прима" по второму вынесенной для самостоятельного изучения Основная литература 1 - 6, дополнительная литература 1 - 10 6 Изучение и конспектирование темы "Методы получения сокращенной дизъюнктивной нормальной формы переключательной функции метод Мак - Класски" по второму разделу вынесенной для самостоятельного изучения Основная литература 1 - 6, дополнительная литература 1 - 10 3 Изучение и конспектирование темы "Проектирование одноразрядного сумматора" по третьему разделу вынесенной для самостоятельного изучения Основная литература 1 - 6, дополнительная литература 1 - 10 5 Подготовка к практическим занятиям. Выполнение домашнего задания Основная литература 1 - 6, дополнительная литература 1 - 10 12 Подготовка к экзамену Основная литература 1 - 6, дополнительная литература 1 - 10 36 Работа с конспектами лекций. Подготовка к тестированию Основная литература 1 - 6, дополнительная литература 1 - 10 8 6. Инновационные образовательные технологии, используемые в учебном процессе Инновационные формы учебных занятий Вид работы (Л, ПЗ, ЛР) Краткое описание Кол - во ауд. часов Проблемная лекция Лекции Проблемная лекция начинается с вопросов, с постановки проблемы, которую в ходе изложения материала необходимо решить. При этом выдвигаемая проблема требует не однотипного решения, готовой 6 схемы которого нет. Данный тип лекции строится таким образом, что деятельность студента по ее усвоению приближается к поисковой, исследовательской. На подобных лекциях обязателен диалог преподавателя и студентов. Проблемное обучение Практические занятия и семинары Преподаватель организует самостоятельную поисковую деятельности студентов по решению учебных проблем, вследствие чего формируются новые знания, умения и навыки, развиваются познавательные способности, любознательность, эрудиция, творческое мышление. Преподаватель не сообщает знания в готовом виде, а выдвигает перед студентами задачу (создает проблемную ситуацию) и побуждает к ее разрешению. 12 Собственные инновационные способы и методы, используемые в образовательном процессе Не предусмотрены Использование результатов научных исследований, проводимых университетом, в рамках данной дисциплины: нет 7. Фонд оценочных средств (ФОС) для проведения текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины 7.1. Паспорт фонда оценочных средств Наименование разделов дисциплины Контролируемая компетенция ЗУНы Вид контроля (включая текущий) №№ заданий Все разделы ПК - 1 способностью разрабатывать модели компонентов информационных систем, включая модели баз данных и модели интерфейсов "человек - электронно - вычислительная машина" Текущий (Тестирование обучающихся по пройденному разделу) Тесты по всем разделам Все разделы ОК - 7 способностью к самоорганизации и самообразованию Текущий (Проверка домашнего задания) Домашние задания по всем разделам Все разделы ПК - 4 способностью готовить конспекты и проводить занятия по обучению работников применению программно - методических комплексов, используемых на предприятии Текущий( Проверка конспектов) Темы для самостоятельного изучения по всем разделам Все разделы ПК - 1 способностью разрабатывать модели компонентов информационных систем, включая модели баз данных и модели интерфейсов "человек - электронно - вычислительная машина" Текущий (Выполнение практических заданий) Практические задания по всем разделам Все разделы ПК - 1 способностью разрабатывать модели компонентов информационных систем, включая модели баз данных и модели интерфейсов "человек - электронно - вычислительная машина" Текущий (Проверка домашнего задания) Домашнее задание по всем разделам Все разделы ПК - 1 способностью разрабатывать модели компонентов информационных систем, включая модели баз данных и модели интерфейсов "человек - электронно - вычислительная машина" Промежуточный (экзамен) Вопросы для подготовки к экзамену 7.2. Виды контроля, процедуры проведения, критерии оценивания Вид контроля Процедуры проведения и оценивания Критерии оценивания Текущий (Тестирование обучающихся по пройденному разделу) Процедура тестирования проводится по окончании изучения раздела дисциплины в письменной форме, на практических занятиях. На выполнение теста студенту отводится 20 минут в конце практического занятия. За семестр тестирование проводится три раза. Студенты предупреждаются о времени проведения, теме и процедуре тестирования (оценивания) за семь дней. Тест содержит три теоретических и три практических вопроса. Тест содержит: - открытые вопросы, когда нет вариантов ответа (требуется указать свой вариант); - закрытые вопросы, когда выбирать нужно строго из предложенных вариантов ответов не внося никаких изменений (причем правильных ответов может быть несколько). Тест оценивается как зачтенный и не зачтенный. При оценивание учитываются все правильные ответы. Зачтено: Оценка «зачтено» выставляется за тест, если дано 70% правильных ответов. Не зачтено: Оценка «не зачтено» выставляется за тест, если дано менее 70% правильных ответов. Текущий (Проверка домашнего задания) Домашнее задание выдается в конце каждого практического занятия. Всего за семестр выдается 11 домашних заданий. В задании не более пяти практических упражнений. Домашние задания выполняются в отдельной тетради и сдаются преподавателю за три дня (для проверки) до начала следующего практического занятия. Оформление домашнего задания допускается только в рукописной форме. Студент должен представить правильное (не менее 70%), полное, аргументированное решение. Работы, в которых есть только ответы, без обоснования решения не рассматриваются и считаются не зачтенными. Домашнее задание должно быть аккуратно оформлено, допускается зачеркивание неверного решения и использование корректоров различного типа. Домашнее задание оценивается как зачтенное и не зачтенное. В начале семестра студентам в электронной форме выдаются методические указания по освоению дисциплины (см. файл в перечне литературы). Зачтено: Оценка «зачтено» выставляется за домашнее задание, если правильно решено 70% упражнений, причем дано полное, аргументированное решение (есть ссылки на определения, свойства, законы, аксиомы). Не зачтено: Оценка «не зачтено» выставляется за домашнее задание, если: - правильно решено менее 70% упражнений, дано неполное, аргументированное решение, нет ссылок на определения, свойства, законы, аксиомы; - правильно решено 70% упражнений, но отсутствует обоснования решения, а есть только ответы. Текущий( Проверка конспектов) Проверяются конспекты по темам, вынесенным на самостоятельное изучение (четыре темы). Конспекты оформляются в рукописной форме в отдельной тетради для Зачтено: Оценка «зачтено» выставляется за конспект темы, если представленный материал достаточно полно раскрывает конспектирования и проверяются в конце семестра. Методические указания по написанию конспекта выдаются студентам в электронной форме в начале семестра (см. файл в перечне электронной литературы). Конспект по теме оценивается как зачтенный и не зачтенный. ответы на поставленные вопросы (не менее 75%). Есть рисунки, таблицы, схемы, диаграммы, ссылки на использованную литературу. Приведены примеры. Текст оформлен аккуратно, без помарок, четко структурирован. Не зачтено: Оценка «не зачтено» выставляется за конспект темы, если представленный материал не достаточно полно раскрывает ответы на поставленные вопросы (менее 75%). Отсутствуют рисунки, таблицы, схемы, диаграммы, ссылки на использованную литературу. Не приведены примеры. Текст оформлен неаккуратно, с помарками, неструктурирован. Текущий (Выполнение практических заданий) Практические задания выполняются на практических занятиях. Задания выдаются преподавателем в начале занятия (см. файлы с заданиями). В ходе практического занятия студент может быть вызван к доске для самостоятельного решения одного из выданных заданий. В не зависимости от формы оценивания каждому студенту может быть задано не менее 3 - х вопросов на тему практического задания. Представленное решение и ответы, на поставленные вопросы, оцениваются как отлично, хорошо, удовлетворительно, неудовлетворительно. Отказ от представления решения у доски без уважительной причины оценивается как неудовлетворительный ответ. Все студенты обязаны не менее двух раз представить решение практических заданий у доски. Отлично: Оценка «Отлично» выставляется за самостоятельное, правильное, аргументированное, четко обоснованное решение и правильные ответы на все вопросы (100% правильных ответов). Студент ориентируется в предметной области, использует корректно терминологию. Хорошо: Оценка «Хорошо» выставляется за самостоятельное, правильное, аргументированное, четко обоснованное решение и правильные ответы на вопросы (не менее 85% правильных ответов). Студент ориентируется в предметной области, использует корректно терминологию. Однако в решении и ответах на вопросы были незначительные ошибки. Удовлетворительно: Оценка «Удовлетворительно» выставляется за несамостоятельное (с помощью преподавателя и/или других студентов), правильное, не достаточно аргументированное, необоснованное решение и правильные ответы на 50% вопросов. Студент плохо ориентируется в предметной области, не владеет терминологией. Неудовлетворительно: Оценка «Неудовлетворительно» выставляется за несамостоятельное (с помощью преподавателя и/или других студентов), неправильное, не достаточно аргументированное, необоснованное решение и неправильные ответы на вопросы (менее 30% правильных ответов). Студент не ориентируется в предметной области, не владеет терминологией. Промежуточный (экзамен) Экзамен проводится во 2 семестре. К экзамену допускаются студенты, выполнившие на «зачтено» все домашние работы и конспекты по всем четырем темам, вынесенным на самостоятельную работу. Имеющие: не более двух пропусков лекционных и практических занятий (пропущенные занятия могут быть отработаны в индивидуальном порядке до начала экзамена); не мене двух оценок не ниже «удовлетворительно» за практические занятия. Вопросы для подготовки к экзамену выдаются студентам в начале семестра (см. файл с экзаменационными вопросами). Экзамен проводится в форме устного опроса. Каждому студенту выдается билет, в котором присутствует по два теоретических вопроса и один практический вопрос из любого раздела дисциплины, за который проводится промежуточная аттестация. На подготовку по экзаменационному билету студенту отводится 90 минут и 20 минут на ответы. Одновременно в аудитории при проведении экзамена должно находиться не более 15 человек. При неправильном ответе студенту могут быть заданы уточняющие или новые вопросы по той же теме. Тема считается освоенной, если студент смог ответить на 60% вопроса, заданного по данной теме. Отлично: Оценка «Отлично» выставляется, если студент, при ответе на теоретические вопросы экзаменационного билета (не менее 90% правильных ответов), показывает глубокое знание вопросов темы, свободно оперирует терминами, легко отвечает на дополнительно заданные вопросы. В процессе ответа приводит примеры. Правильно решил практическое задание экзаменационного билета. Решение аргументировано, четко обосновано, приведены примеры. Хорошо: Оценка «Хорошо» выставляется, если студент, при ответе на теоретические вопросы экзаменационного билета (не менее 75% правильных ответов), показывает хорошее знание вопросов темы, свободно оперирует терминами, легко отвечает на дополнительно заданные вопросы. В процессе ответа приводит примеры. Правильно решил практическое задание экзаменационного билета. Решение аргументировано, четко обосновано, приведены примеры. Однако есть незначительные ошибки. Удовлетворительно: Оценка «Удовлетворительно» выставляется, если студент, при ответе на теоретические вопросы экзаменационного билета, показывает поверхностное знание вопросов темы, с трудом оперирует терминами, отвечает не на все на дополнительно заданные вопросы. В процессе ответа не приводит примеры. Правильно решил практическое задание экзаменационного билета. Решение не аргументировано, четко не обосновано, не приведены примеры. Неудовлетворительно: Оценка «Неудовлетворительно» выставляется, если студент, при ответе на теоретические вопросы экзаменационного билета (менее 30% правильных ответов), показывает не знание вопросов темы, не оперирует терминами, не отвечает на дополнительно заданные вопросы. В процессе ответа не приводит примеры. Неправильно решил практическое задание экзаменационного билета. Решение не аргументировано, не обосновано, не приведены примеры. 7.3. Типовые контрольные задания Вид контроля Типовые контрольные задания Текущий (Тестирование обучающихся по пройденному разделу) Тесты_ДМ_по всем разделам.docx Текущий (Проверка домашнего задания) Домашние работы по всем разделам.docx Текущий( Проверка конспектов) По теме темы "Матрицы смежности и инцидентности графа/ографа". 1. В чем различие матриц смежности и инцидентности? 2. Как строятся матрицы смежности и инцидентности простого и ориентированного графов? 3. Как формализовать направление ребра. 4. Как формализовать наличие петли в графе в матрицах? По теме темы " Методы оптимизации на графах. Алгоритм Дейкстры, Флойда - Уоршала, Прима ". 1. Алгоритм Дейкстры определяет: а) кратчайший остов графа; б) построение дерева кратчайших путей; в) построение оптимального дерева бинарного поиска; г) эйлеровы циклы графа. 2. В алгоритме Дейкстры текущие числовые метки а) неубывают; б) невозрастают; в) равны нулю; г) отрицательные. 3. В алгоритме Дейкстры текущая числовая метка определяется а) сложением двух предыдущих; б) вычитанием двух предыдущих; в) по минимуму из двух предыдущих; г) сложением с постоянной меткой и сравнением с предыдущей. 4. Постоянные метки в алгоритме Дейкстры а) убывают; б) возрастают; в) неубывают. 5. Постоянно помеченные вершины а) повторяются; б) не повторяются. 6. Определение постоянно помеченной вершины включает: а) вычисление текущих меток для всех вершин и нахождение минимума среди них; б) вычисление текущих меток для всех вершин и нахождение максимума среди них; в) вычисление текущих меток для всех вершин и нахождение их среднего арифметического. 7. В чем состоит задача поиска всех кратчайших путей? 8. Приведите общую схему алгоритма Флойда - Уоршалла. 9. Какова трудоемкость алгоритма? 10. При решении каких задач применяется алгоритм Дейкстры и Флойда - Уршалла? 11. Чем отличается полусумматор от одноразрядного сумматора? Текущий (Выполнение практических заданий) Практические задания по всем разделам.docx Промежуточный (экзамен) Экзаменационные вопросы по дисциплине.docx 8. Учебно - методическое и информационное обеспечение дисциплины Печатная учебно - методическая документация а) основная литература: Не предусмотрена б) дополнительная литература: 1. Судоплатов, С. В. Элементы дискретной математики Учеб. для втузов С. В. Судоплатов, Е. В. Овчинникова; Новосиб гос. техн. ун - т; Новосиб. гос. техн. ун - т. - М.; Новосибирск: ИНФРА - М: НГТУ, 2002. - 279,[1] с. 2. Хаггарти, Р. Дискретная математика для программистов Учеб. пособие для вузов Р. Хаггарти; Пер. с англ. и под ред. С. А. Кулешова и др. - 2 - е, доп. изд. - М.: Техносфера, 2005. - 399 с. 3. Новиков, Ф. А. Дискретная математика для программистов Учеб. - СПб.: Питер, 2000. - 301 с. ил. 4. Шапорев, С. Д. Дискретная математика. Курс лекций и практических занятий Текст учеб. пособие для вузов по специальностям 220200 "Автоматизир. системы обраб. информации и упр.", 071900 "Информ. системы в технике и технологиях" С. Д. Шапорев. - СПб.: БХВ - Петербург, 2007. - 396 с. ил. 5. Марченков, С. С. Булевы функции С. С. Марченков. - М.: Физматлит, 2002. - 68,[1] с. 6. Архангельский, А. В. Канторовская теория множеств Текст А. В. Архангельский. - М.: Издательство МГУ, 1988. - 110 с. 7. Хаусдорф, Ф. Теория множеств Текст Ф. Хаусдорф ; пер. с нем. Н. Б. Веденисова ; под ред., с предисл. и доп. П. С. Александрова, А. Н. Колмогорова. - Изд. стер. - М.: URSS : ЛИБРОКОМ, 2013. - 302, [1] с. ил. в) отечественные и зарубежные журналы по дисциплине, имеющиеся в библиотеке: г) методические указания для студентов по освоению дисциплины: 1. Методические указания для студентов по освоению дисциплины "Дискретная математика" (располагается в локальной сети кафедры) 2. Методические указания по освоению дисциплины "Дискретная математика" (располагается в локальной сети кафедры) из них: учебно - методическое обеспечение самостоятельной работы студента: 3. Методические указания для студентов по освоению дисциплины "Дискретная математика" (располагается в локальной сети кафедры) Электронная учебно - методическая документация № Вид литературы Наименование разработки Наименование ресурса в электронной форме Доступность (сеть Интернет / локальная сеть; авторизованный / свободный до - ступ) 1 Основная литература Микони, С.В. Дискретная математика для бакалавра: множества, отношения, функции, графы. [Электронный ресурс] — Электрон. дан. — СПб. : Лань, 2012. — 192 с. — Режим доступа: http://e.lanbook.com/book/4316 — Загл. с экрана. Электронно - библиотечная система Издательства Лань Интернет / Авторизованный 2 Основная литература Иванов, Б.Н. Дискретная математика. Алгоритмы и программы. Полный курс. [Электронный ресурс] — Электрон. дан. — М. : Физматлит, 2007. — 408 с. — Режим доступа: http://e.lanbook.com/book/59461 — Загл. с экрана. Электронно - библиотечная система Издательства Лань Интернет / Авторизованный 3 Основная литература Кузнецов, О.П. Дискретная математика для инженера. [Электронный ресурс] — Электрон. дан. — СПб. : Лань, 2009. — 400 с. — Режим доступа: Электронно - библиотечная система Издательства Лань Интернет / Авторизованный http://e.lanbook.com/book/220 — Загл. с экрана. 4 Основная литература Тюрин, С.Ф. Дискретная математика: Практическая дискретная математика и математическая логика. [Электронный ресурс] / С.Ф. Тюрин, Ю.А. Аляев. — Электрон. дан. — М. : Финансы и статистика, 2012. — 384 с. — Режим доступа: http://e.lanbook.com/book/28369 — Загл. с экрана. Электронно - библиотечная система Издательства Лань Интернет / Авторизованный 5 Основная литература Николаева, Е.А. Функции алгебры логики. [Электронный ресурс] / Е.А. Николаева, С.А. Останин, А.Ю. Матросова. — Электрон. дан. — Томск : ТГУ, 2013. — 48 с. — Режим доступа: http://e.lanbook.com/book/44917 — Загл. с экрана. Электронно - библиотечная система Издательства Лань Интернет / Авторизованный 6 Дополнительная литература Марченков, С.С. Булевы функции. [Электронный ресурс] — Электрон. дан. — М. : Физматлит, 2002. — 68 с. — Режим доступа: http://e.lanbook.com/book/2259 — Загл. с экрана. Электронно - библиотечная система Издательства Лань Интернет / Авторизованный 7 Дополнительная литература Гусева, А.И. Дискретная математика для информатиков и экономистов: учебное пособие для вузов. [Электронный ресурс] / А.И. Гусева, А.Н. Тихомирова. — Электрон. дан. — М. : НИЯУ МИФИ, 2010. — 280 с. — Режим доступа: http://e.lanbook.com/book/75860 — Загл. с экрана. Электронно - библиотечная система Издательства Лань Интернет / Авторизованный 8 Дополнительная литература Зайцева, О.Н. Математические методы в приложениях. Дискретная математика: учебное пособие. [Электронный ресурс] / О.Н. Зайцева, А.Н. Нуриев, П.В. Малов. — Электрон. дан. — Казань : КНИТУ, 2014. — 173 с. — Режим доступа: http://e.lanbook.com/book/73295 — Загл. с экрана. Электронно - библиотечная система Издательства Лань Интернет / Авторизованный 9 Методические пособия для преподавателя Годунова, Е.К. Введение в теорию графов. Индивидуальные задания. [Электронный ресурс] — Электрон. дан. — Бишкек : Издательство "Прометей", 2012. — 44 с. — Режим доступа: http://e.lanbook.com/book/64218 Электронно - библиотечная система Издательства Лань Интернет / Авторизованный — Загл. с экрана. 10 Методические пособия для преподавателя Бабичева, И.В. Дискретная математика. Контролирующие материалы к тестированию. [Электронный ресурс] — Электрон. дан. — СПб. : Лань, 2013. — 160 с. — Режим доступа: http://e.lanbook.com/book/30193 — Загл. с экрана. Электронно - библиотечная система Издательства Лань Интернет / Авторизованный 11 Методические пособия для преподавателя Шевелев, Ю.П. Сборник задач по дискретной математике (для практических занятий в группах). [Электронный ресурс] / Ю.П. Шевелев, Л.А. Писаренко, М.Ю. Шевелев. — Электрон. дан. — СПб. : Лань, 2013. — 528 с. — Режим доступа: http://e.lanbook.com/book/5251 — Загл. с экрана. Электронно - библиотечная система Издательства Лань Интернет / Авторизованный 12 Методические пособия для самостоятельной работы студента Бояринцева, Т.И. Теория графов: метод. указания. [Электронный ресурс] / Т.И. Бояринцева, А.А. Мастихина. — Электрон. дан. — М. : МГТУ им. Н.Э. Баумана, 2014. — 37 с. — Режим доступа: http://e.lanbook.com/book/58426 — Загл. с экрана. Электронно - библиотечная система Издательства Лань Интернет / Авторизованный 13 Методические пособия для самостоятельной работы студента Кирсанов, М.Н. Графы в Maple. Задачи, алгоритмы, программы. [Электронный ресурс] — Электрон. дан. — М. : Физматлит, 2006. — 168 с. — Режим доступа: http://e.lanbook.com/book/2738 — Загл. с экрана. Электронно - библиотечная система Издательства Лань Интернет / Авторизованный 14 Методические пособия для самостоятельной работы студента Методические указания для написания конспекта Учебно - методические материалы кафедры ЛокальнаяСеть / Авторизованный 9. Информационные технологии, используемые при осуществлении образовательного процесса Перечень используемого программного обеспечения: Нет Перечень используемых информационных справочных систем: Нет 10. Материально - техническое обеспечение дисциплины Вид занятий № ауд. Основное оборудование, стенды, макеты, компьютерная техника, предустановленное программное обеспечение, используемое для различных видов занятий Лекции 240 (3б) Компьютер, проектор Практические занятия и семинары 801 (3б) Учебный класс.

Приложенные файлы

  • pdf 1397253
    Размер файла: 194 kB Загрузок: 0

Добавить комментарий