Главная страница новости/обновления о создании страницы О кафедре общая информация история кафедры сотрудники Для студентов учебный план виды дисциплин рабочие программы расписания занятий задания для сам-х. работ конспекты лекций электронные учебники методические материалы Для абитуриентов методические пособия направления обучения о специальности Научная работа научные направления научные труды научные проекты диссертации научные связи	... дискретная математика	Фото галерея общие фото личные фото Сервис... сделать домашней в избранное гостевая Ссылки Статистика посещений
	Примерная программа дисциплины ДИСКРЕТНАЯ МАТЕМАТИКА Рекомендуется Минобразованием России для специальности (направления) подготовки 010200 Прикладная математика и информатика (510200 Прикладная математика и информатика) ЦЕЛЬ И ЗАДАЧИ КУРСА Дисциплина "Дискретная математика" ставит своей целью ознакомление студентов с важнейшими разделами дискретной математики и ее применением в математической кибернетике. В процессе обучения прививаются навыки свободного обращения с такими дискретными объектами как функции алгебры логики, автоматные функции, машины Тьюринга, рекурсивные функции, графы и вырабатывается представление о проблематике теории кодирования, синтеза управляющих систем. Во всех разделах дисциплины большое внимание следует уделять построению алгоритмов для решения задач дискретной математики. Это способствует более глубокому пониманию проблематики теории алгоритмов, ее возможностей и трудностей, помогает строить алгоритмы для решения дискретных задач. ВВЕДЕНИЕ Место дискретной математики в системе математического образования. Дискретная математика и математическая кибернетика. Соотношение между непрерывным и дискретным подходами к изучению различных явлений. Элементы комбинаторики. Перестановки, размещения, сочетания, сочетания с повторениями, их число. Бином Ньютона. ФУНКЦИОНАЛЬНЫЕ СИСТЕМЫ С ОПЕРАЦИЯМИ Алгебра логики. Функции алгебры логики. Формулы. Реализация функций формулами, эквивалентность формул. Свойства элементарных функций. Принцип двойственности. Разложение функций алгебры логики по переменным. Совершенная дизъюнктивная нормальная форма. Полнота и замкнутость, примеры полных систем. Важнейшие замкнутые классы, теорема о полноте. Представление о результатах Поста. Ограниченно-детерминированные (автоматные) функции. Диаграммы переходов. Канонические уравнения. Операции над ограниченно-детерминированными функциями. Примеры полных систем. Пример универсальной ограниченно-детерминированной функции. Проблема распознавания полноты систем ограниченно-детерминированных функций. Вычислимые функции. Машины Тьюринга. Операции над машинами Тьюринга. Вычислимые функции. Операции суперпозиции, примитивной рекурсии и минимизации. Рекурсивные функции, их связь с классом вычислимых функций. Тезис Тьюринга. НЕКОТОРЫЕ ВАЖНЫЕ ДИСКРЕТНЫЕ СТРУКТУРЫ Графы. Основные понятия теории графов. Типы и способы задания для сам-х. работ графов. Изоморфизм, связность. Деревья и их свойства. Корневые деревья и оценка их числа. Геометрическая реализация графов. Формула Эйлера. Понятие о теореме Понтрягина-Куратовского. Оценки числа графов. Коды. Проблематика теории кодирования. Алфавитное кодирование. Критерий однозначности декодирования. Помехоустойчивое кодирование. Коды Хэмминга. Представление о кодах с минимальной избыточностью. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К МАТЕМАТИЧЕСКОЙ КИБЕРНЕТИКЕ Проблема построения минимальных дизъюнктивных нормальных форм и подходы к ее решению. Схемы из функциональных элементов в базисе: конъюнкция, дизъюнкция, отрицание. Примеры построения схем из функциональных элементов. Двоичный сумматор. Задача построения минимальных схем из функциональных элементов и подходы к ее решению. Функция Шеннона. Порядок функции Шеннона. ПРИМЕРНЫЙ ПЕРЕЧЕНЬ ПРАКТИЧЕСКИХ ЗАНЯТИЙ Задание функций алгебры логики таблицами и формулами. Замкнутые классы. Теорема о полноте. Способы задания для сам-х. работ ограниченно-детерминированных функций, операции над ними. Машины Тьюринга и вычислимые функции. Рекурсивные функции. Графы, их свойства. Коды. Распознавание однозначности декодирования. Построение кодов с минимальной избыточностью. Коды Хэмминга. И другие. РАСПРЕДЕЛЕНИЕ ЧАСОВ КУРСА ПО ТЕМАМ И ВИДАМ РАБОТ № Наименование тем и разделов Всего (часов) Аудиторные занятия (часов) Самостоятельная работа (часов) 1 Введение 6 4 2 2 Алгебра логики 24 14 10 3 Ограничено-детерминированные (автоматные) функции 18 12 6 4 Вычислимые функции 18 12 6 5 Графы 18 12 6 6 Коды 18 12 6 7 Дизъюнктивные-нормальные формы 18 12 6 8 Схемы из функциональных элементов 18 12 6 = ИТОГО 138 90 48 Примечание:Во всех разделах таблицы указано минимальное число часов, необходимое для усвоения соответствующего раздела. Оставшиеся часы используются в рабочей программе для более глубокого изложения отдельных разделов курса. Форма итогового контроля - экзамен. ЛИТЕРАТУРА Основная Яблонский С.В. Введение в дискретную математику: Учеб. пособие. М.: Наука, 1986. 384 с. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики: Учеб. пособие. М.: Наука, 1992. 408 с. Дискретная математика и математические вопросы кибернетики. /Под ред. Яблонского С.В., Лупанова О.Б. Т. 1. М.: Наука, 1974. 312 с. Список дополнительной литературы устанавливается кафедрой. Программа составлена чл.-корр. РАН О.Б.Лупановым, проф. В.Б.Алексеевым (Московский университет). Рецензенты: профессор В.Н.Шевченко, профессор В.Е.Алексеев (Нижегородский университет).
Используйте Internet Explorer 5 Flash Player 5 WebMaster | PageMaker