• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Discrete Mathematics

2021/2022
Academic Year
RUS
Instruction in Russian
4
ECTS credits
Delivered at:
Department of Informatics
Course type:
Compulsory course
When:
2 year, 1-4 module

Instructors

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

Аннотация

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

Цель освоения дисциплины

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

Планируемые результаты обучения

  • Знает основные понятия и факты теории графов, такие, как деревья, циклы, связность в графах, паросочетания, раскраски графов, планарные графы, классические и обобщенные постановки комбинаторных задач, комбинаторный смысл основных операций над производящими функциями.
  • Умеет находить кратчайшие и минимальные пути в графе, медианы и центры графа, остовные деревья, эйлеровы и гамильтоновы циклы, совершенные или максимальные паросочетания, оптимальную раскраску графа, решать линейные рекуррентные соотношения как с помощью производящих функций, так и без них, перечислять основные дискретные объекты (графы, деревья, плоские деревья).
  • Имеет навыки использования методов решения основных комбинаторных задач с помощью производящих функций, использования основных алгоритмов работы с графами.
Содержание учебной дисциплины

Содержание учебной дисциплины

  • Элементарная комбинаторика и теория графов.
  • Остовные деревья, циклы и разрезы. Связность в графах.
  • Паросочетания в графах. Раскраска графов
  • Планарные графы
  • Производящие функции и перечисление дискретных структур.
Элементы контроля

Элементы контроля

  • неблокирующий Домашнее задание №1
  • неблокирующий Домашнее задание №2
  • неблокирующий Контрольная работа
  • блокирующий Письменный экзамен №1
  • неблокирующий Домашнее задание №3
  • неблокирующий Домашнее задание №4
  • блокирующий Письменный экзамен №2
    Экзамен проводится в письменной форме с использованием синхронного прокторинга и состоит из ответов на два теоретических вопроса. Экзамен проводится на платформе Moodle (https://et.hse.ru), прокторинг на платформе Экзамус (hse.student.examus.net). К экзамену необходимо подключиться за 15 минут. На платформе Экзамус доступно тестирование системы. Компьютер студента должен удовлетворять следующим требованиям: https://elearning.hse.ru/data/2020/05/07/1544135594/Технические%20требования%20к%20ПК%20студента.pdf) Для участия в экзамене студент обязан: заранее зайти на платформу прокторинга, провести тест системы, включить камеру и микрофон, подтвердить личность. Время выполнения задания два часа. Время начала экзамена 11:00, завершение в 13:00. Во время выполнения студент записывает свой ответ на чистом листе бумаги, после фотографирует и высылает решение фотографию на электронную почту преподавателя. На отсылку решения дается 5 минут по завершении экзамена. Во время экзамена студентам запрещено: общаться (в социальных сетях, с людьми в комнате), списывать, использовать любые материалы. Во время экзамена студентам разрешено иметь при себе ручку и чистые листы бумаги, во время отправки решений разрешается использовать мобильный телефон или сканер. Кратковременным нарушением связи во время экзамена считается прерывание связи до 5 минут, если после этого студенту удается вернуться в ту же сессию работы с Экзамус. Долговременным нарушением связи во время экзамена считается прерывание связи 5 минут и более. При долговременном нарушении связи студент не может продолжить участие в экзамене. Процедура пересдачи аналогична процедуре сдачи.
  • неблокирующий Домашнее задание №1
  • неблокирующий Домашнее задание №2
  • неблокирующий Контрольная работа
  • неблокирующий Письменный экзамен №1
  • неблокирующий Домашнее задание №3
  • неблокирующий Домашнее задание №4
  • блокирующий Письменный экзамен №2
    Экзамен проводится офлайн.
Промежуточная аттестация

Промежуточная аттестация

  • 2020/2021 учебный год 1 модуль
    0.15 * Домашнее задание №1 + 0.15 * Домашнее задание №2 + 0.2 * Контрольная работа + 0.5 * Письменный экзамен №1
  • 2020/2021 учебный год 4 модуль
    0.25 * Домашнее задание №2 + 0.5 * Контрольная работа + 0.25 * Домашнее задание №1
  • 2021/2022 учебный год 1 модуль
    0.3 * Домашнее задание №1 + 0.7 * Контрольная работа
  • 2021/2022 учебный год 2 модуль
    0.7 * Письменный экзамен №1 + 0.3 * Домашнее задание №2
  • 2021/2022 учебный год 3 модуль
    0.5 * Домашнее задание №3 + 0.5 * Домашнее задание №4
  • 2021/2022 учебный год 4 модуль
    0.25 * Письменный экзамен №2 + 0.25 * 2021/2022 учебный год 2 модуль + 0.25 * 2021/2022 учебный год 3 модуль + 0.25 * 2021/2022 учебный год 1 модуль
Список литературы

Список литературы

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

  • Гисин В. Б. - ДИСКРЕТНАЯ МАТЕМАТИКА. Учебник и практикум для СПО - М.:Издательство Юрайт - 2019 - 383с. - ISBN: 978-5-534-11633-5 - Текст электронный // ЭБС ЮРАЙТ - URL: https://urait.ru/book/diskretnaya-matematika-445774

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

  • Kumar, R., & Pattnaik, P. K. (2018). Graph Theory. Bengaluru: Laxmi Publications Pvt Ltd. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=2228702