2010/2011 учебный год

Последнее изменение: 07/01/2013 18:00:00

Дискретная математика

Основной курс дискретной математики для потока математиков 2-го курса.

Краткое содержание курса

  • Квадратичные формы
    • Приведение к диагональному виду методом Лагранжа
    • Закон инерции вещественных квадратичных форм
    • Положительно определенные формы. Критерий Сильвестера
    • Приведение к главным осям. Приведение пары форм
  • Коды, исправляющие ошибки
    • Двоичный симметричный канал без памяти
    • Основные параметры кода. Неравенство Хэмминга
    • Линейные коды. Порождающая матрица. Неравенство Синглтона
    • Проверочная матрица. Коды Хэмминга
    • Минимальное расстояние как антиранг проверочной матрицы. Неравенство Гильберта-Варшамова
    • Циклические коды. Связь с идеалами кольца многочленов
    • Расширение полей с помощью неприводимых многочленов.
    • Неприводимые многочлены над простым конечным полем
    • Конечные поля. Теорема о примитивном элементе конечного поля
    • Построение кодов БЧХ.
    • Декодирование кодов БЧХ
    • Коды Рида-Соломона и их практические применения
  • Конечные автоматы и формальные языки
    • Конечные автоматы и распознаваемые языки
    • Булевы операции над распознаваемыми языками
    • Недетерминированные автоматы. Эквивалентность распознаваемости детерминированными и недетерминированными автоматами
    • Распознаваемость произведения и итерации распознаваемых языков
    • Рациональные языки. Теорема Клини
    • Частные распознаваемых языков. Минимальный автомат языка.
    • Алгоритм минимизации автомата
  • Булевы функции
    • Дизъюнктивная и конъюнктивная нормальная формы
    • Многочлены Жегалкина
    • Теорема Поста (критерий полноты системы булевых функций)
  • Элементы математической логики
    • Метод резолюций для формул логики высказываний. Полнота метода резолюций
    • Формулы логики предикатов
    • Предваренная нормальная форма
    • Сколемизация
    • Алгоритм унификации
    • Метод резолюций для формул логики предикатов
    • Теорема Эрбрана. Полнота метода резолюций
    • Применения метода резолюций

Вопросы к экзамену

Результаты экзаменов (с учетом пересдач)
Группа Отлично Хорошо Удовлетв. Неудовл. Не аттест. Всего
Мт-201 4 8 7   1 20
Мт-202 5 8 9     22
Мт-203 2 4 8 2 2 18
Мт-204 7 2 4   4 17
Поток Мт 18 22 28 2 7 77

Основы научной работы в сфере математики и информатики

Обязательный курс для 1-го курса магистратуры.

Цель этого экспериментального курса - собрать вместе сведения, которые могут пригодиться молодому человеку, рассматривающему научную работу в области математики и информатики как возможную сферу своей будущей деятельности.

Смотрите также: