Дискретная математика (1-й поток) — различия между версиями
(→Лекции) |
|||
| Строка 8: | Строка 8: | ||
==Лекции== | ==Лекции== | ||
| + | |||
| + | '''Алгебра логики''' | ||
| + | |||
| + | Лекция 1. Единичный n-мерный куб. Наборы, вес набора. Слой n-мерного куба. Частичный порядок на n-мерном кубе. Соседние и противоположные наборы, расстояние между наборами. Лексико-графический порядок на n-мерном кубе. | ||
| + | |||
| + | Лекция 2. Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Формулы. Тождества. Двойственность. | ||
| + | |||
| + | Лекция 3. Расщепление функций по переменным. Теорема о совершенной ДНФ. Теорема о совершенной КНФ. Полиномы Жегалкина. Теорема Жегалкина. Быстрый способ построения полинома Жегалкина. | ||
| + | |||
| + | Лекция 4. Полные системы. Полнота некоторых систем. Оператор замыкания. Замкнутые классы. Замкнутость классов T_0, T_1, L, S, M. Леммы о несамодвойственной, немонотонной и нелинейной функциях. | ||
| + | |||
| + | Лекция 5. Полные системы. Теорема Поста о полноте. Базис в P_2. Теореме о числе функций в базисе P_2. Предполные классы. Теорема о предполных классах в P_2. | ||
| + | |||
| + | Лекция 6. Функции k-значной логики. Таблицы значений. Представление функций k-значной логики в 1-й и 2-й формах. Представление функций k-значной логики полиномами по модулю~$k$. | ||
| + | |||
| + | '''Графы''' | ||
| + | |||
| + | '''Алгоритмы''' | ||
| + | |||
| + | '''Коды''' | ||
| + | |||
| + | '''Автоматы''' | ||
[[Media: dm1-l-selezn.pdf | Лекция]]: Конечные автоматы-преобразователи (автоматы с выходом). Способы их представления. Отличимость состояний в конечных автоматах. Упрощение автоматов. | [[Media: dm1-l-selezn.pdf | Лекция]]: Конечные автоматы-преобразователи (автоматы с выходом). Способы их представления. Отличимость состояний в конечных автоматах. Упрощение автоматов. | ||
Версия 17:28, 15 января 2020
Основной курс для студентов 1-го курса, читается во 2-м семестре. Лекции - 3 ч в неделю, семинары - 2 ч в неделю, отчетность - экзамен.
Дополнительная страница по курсу Дискретная математика (1й курс).
Лектор - Селезнева Светлана Николаевна
Лекции
Алгебра логики
Лекция 1. Единичный n-мерный куб. Наборы, вес набора. Слой n-мерного куба. Частичный порядок на n-мерном кубе. Соседние и противоположные наборы, расстояние между наборами. Лексико-графический порядок на n-мерном кубе.
Лекция 2. Функции алгебры логики. Таблицы истинности. Существенные и несущественные переменные. Формулы. Тождества. Двойственность.
Лекция 3. Расщепление функций по переменным. Теорема о совершенной ДНФ. Теорема о совершенной КНФ. Полиномы Жегалкина. Теорема Жегалкина. Быстрый способ построения полинома Жегалкина.
Лекция 4. Полные системы. Полнота некоторых систем. Оператор замыкания. Замкнутые классы. Замкнутость классов T_0, T_1, L, S, M. Леммы о несамодвойственной, немонотонной и нелинейной функциях.
Лекция 5. Полные системы. Теорема Поста о полноте. Базис в P_2. Теореме о числе функций в базисе P_2. Предполные классы. Теорема о предполных классах в P_2.
Лекция 6. Функции k-значной логики. Таблицы значений. Представление функций k-значной логики в 1-й и 2-й формах. Представление функций k-значной логики полиномами по модулю~$k$.
Графы
Алгоритмы
Коды
Автоматы
Лекция: Конечные автоматы-преобразователи (автоматы с выходом). Способы их представления. Отличимость состояний в конечных автоматах. Упрощение автоматов.
