Компьютерные науки
Математика и логика

Основы дискретной математики

Учебная программа посвящена дискретной математике для ИТ. В программе рассматривается комбинаторика, булевы функции, теория графов и алгоритмы на деревьях.
Студентов 3762 Выпускников 371 Для специалистов
690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
Темы:
Алгоритмы и сложность, Математика
Объем
36 час.
Длительность
30 дней
Нагрузка в неделю
9 час.
Формат обучения
Дистанционно (самостоятельно)
Описание Учебная программа переводит математические концепции на уровень алгоритмических процедур. Слушатели осваивают законы логики, многочлены Жегалкина, теорему Поста и задачи выводимости. Процесс освоения сопровождается разбором многочисленных примеров и упражнений. Темы включают представления графов, обходы деревьев, работу с Хорновскими формулами и алгоритмы решения задачи о лабиринте. Особое внимание уделено связи дискретных функций с реляционными базами данных, а также классическим алгоритмам на графах. Материал программы формирует теоретическую базу, необходимую для изучения алгоритмов и сложности вычислений в профессиональной ИТ-подготовке.
Цели
  • Дать системное представление о структурах и методах дискретной математики.
  • Раскрыть связь между логикой предикатов и архитектурой баз данных.
  • Познакомить с фундаментальными алгоритмами на графах и деревьях.
Чему я научусь?
  • Использовать булевы функции и нормальные формы для проектирования логических схем.
  • Решать комбинаторные задачи и применять метод математической индукции.
  • Реализовывать алгоритмы поиска на графах и обхода сложных иерархических структур.

Авторы

Дехтярь Михаил Иосифович
Дехтярь Михаил Иосифович
Кандидат физико-математических наук, доцент кафедры информатики Тверского государственного университета.
Чему я научусь?
  • Использовать булевы функции и нормальные формы для проектирования логических схем.
  • Решать комбинаторные задачи и применять метод математической индукции.
  • Реализовывать алгоритмы поиска на графах и обхода сложных иерархических структур.

Учебный план

№ Занятия
Экзамен экстерном Внимание! Экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите подтвердить свои знания по данному курсу без его изучения или поверить свои знания по нему. Экзамен экстерном можно сдать только один раз. 90 мин
1 Предварительные сведения Множества и операции над ними. Как доказывать равенство множеств? Отношения и функции. Отношения эквивалентности и частичного... Множества и операции над ними. Как доказывать равенство множеств? Отношения и функции. Отношения эквивалентности и частичного порядка. Мощность множеств ещё
Предварительные сведения тест для курса Основы дискретной математики 30 мин
2 Индукция и комбинаторика Метод математической индукции. Индукция по структуре объекта. Комбинаторика: число размещений, перестановок и сочетаний. Принцип включения и... Метод математической индукции. Индукция по структуре объекта. Комбинаторика: число размещений, перестановок и сочетаний. Принцип включения и исключения ещё
Индукция и комбинаторика тест для курса Основы дискретной математики 35 мин
3 Булевы функции и их представления Класс Pnбулевых функций от n переменных. Геометрическое представление булевых функций. Задание булевых функций с помощью таблиц.... Класс Pnбулевых функций от n переменных. Геометрическое представление булевых функций. Задание булевых функций с помощью таблиц. Булевы функции от 1-ой и 2-х переменных. булевы (логические) формулы. Решение задач логики высказываний с помощью булевых формул и функций ещё
Булевы функции и их представления тест для курса Основы дискретной математики 30 мин
4 Эквивалентность формул и нормальные формы Эквивалентность булевых формул. Основные эквивалентности (законы логики). Эквивалентные преобразования формул. Принцип замены эквивалентных. Дизъюнктивные и конъюнктивные... Эквивалентность булевых формул. Основные эквивалентности (законы логики). Эквивалентные преобразования формул. Принцип замены эквивалентных. Дизъюнктивные и конъюнктивные нормальные формы (ДНФ и КНФ). Совершенные ДНФ и КНФ. Сокращенные ДНФ и их построение методом Блейка. Многочлены Жегалкина и их построение с помощью эквивалентных преобразований формул и методом неопределенных коэффициентов по таблицам ещё
Эквивалентность формул и нормальные формы тест для курса Основы дискретной математики 30 мин
5 Полные системы функций и теорема Поста Замкнутые классы функций. Полные системы булевых функций. Замкнутость классов функций, сохраняющих 0, функций, сохраняющих 1, самодвойственных... Замкнутые классы функций. Полные системы булевых функций. Замкнутость классов функций, сохраняющих 0, функций, сохраняющих 1, самодвойственных функций, монотонных функций и линейных функций. Критерий полноты системы булевых функций (теорема Поста) ещё
Полные системы функций и теорема Поста тест для курса Основы дискретной математики 30 мин
6 Хорновские формулы и задача получения продукции Хорновские формулы. Задача получения продукции. Связь между задачей о следствии для Хорновских формул и разрешимостьюзадачи о... Хорновские формулы. Задача получения продукции. Связь между задачей о следствии для Хорновских формул и разрешимостьюзадачи о продукции. Эффективные алгоритмы прямого поиска (поиска от данных) для решения задачи о продукции ещё
Хорновские формулы и задача получения продукции тест для курса Основы дискретной математики 20 мин
7 Язык логики предикатов Объекты, их свойства, отношения между объектами и функции. Утверждения о свойствах объектов и отношениях между ними.... Объекты, их свойства, отношения между объектами и функции. Утверждения о свойствах объектов и отношениях между ними. Предикаты. Синтаксис логики предикатов. Семантика логики предикатов: системы, состояния и значения формул на состояниях ещё
Язык логики предикатов тест для курса Основы дискретной математики 30 мин
8 Логика предикатов и базы данных Реляционные базы данных. Схемы отношений и предикаты. Реляционная алгебра и представление ее выражений формулами логики предикатов.... Реляционные базы данных. Схемы отношений и предикаты. Реляционная алгебра и представление ее выражений формулами логики предикатов. Язык запросов SQL и его связь с логикой предикатов. Ограничения целостности: ограничения на ключи, ограничения на ссылки и ограничения на значения атрибутов ещё
Логика предикатов и базы данных тест для курса Основы дискретной математики 30 мин
9 Графы: представления, достижимость и связность Ориентированные и неориентированные графы. Представление графа с помощью матрицы смежности, матрицы инцидентности и списов смежности. Граф... Ориентированные и неориентированные графы. Представление графа с помощью матрицы смежности, матрицы инцидентности и списов смежности. Граф достижимости (транзитивногозамыкания). Отношение взаимной достижимости, компоненты сильной связности и базы ориентированного графа ещё
Графы: представления, достижимость и связность тест для курса Основы дискретной математики 30 мин
10 Деревья Неориентированные и ориентированные деревья. Эквивалентность разных определений деревьев. Деревья и формулы (выражения). Обходы деревьев
Деревья тест для курса Основы дискретной математики 30 мин
11 Три алгоритма на графах Построение минимального остова графа: алгоритм Крускала. Задача о лабиринте и поиск в глубину на неориентированном графе.... Построение минимального остова графа: алгоритм Крускала. Задача о лабиринте и поиск в глубину на неориентированном графе. Нахождение кратчайших путей из одного источника: алгоритм Дейкстры ещё
Три алгоритма на графах тест для курса Основы дискретной математики 30 мин
Тренировочный экзамен Внимание! Тренировочный экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите проверить свои знания курса перед сдачей экзамена. Тренировочный экзамен можно сдавать сколько угодно один раз. 90 мин
Экзамен 60 мин

Какой документ я получу?

Сертификат

Выдаётся автоматически после успешного завершения программы.

Удостоверение о повышении квалификации

Выдается при наличии среднего специального или высшего образования (необходимые документы).

Стоимость программы

690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
^