НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
ФАКУЛЬТЕТ ПРИКЛАДНОЙ МАТЕМАТИКИ И ИНФОРМАТИКИ
КАФЕДРА ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛИТЕЛЬНЫХ ТЕХНОЛОГИЙ
“УТВЕРЖДАЮ”
Декан
факультета прикладной математики
и информатики
«___ »______________2009 г.
РАБОЧАЯ ПРОГРАММА УЧЕБНОЙ ДИСЦИПЛИНЫ
СПЕЦИАЛЬНЫЕ ГЛАВЫ ДИСКРЕТНОЙ МАТЕМАТИКИ
ООП: 010503 – Математическое обеспечение и администрирование информационных систем; квалификация – математик-программист
Факультет Прикладной математики и информатики
Курс 2
Семестр 3
Лекции 18 час
Практические занятия 18 час
Самостоятельная работа 64 час
Экзамен 3 семестр
Всего 100 час
Новосибирск
2006
Рабочая программа составлена на основании государственного образовательного стандарта по специальности 351500 «Математическое обеспечение и администрирование информационных систем», утвержденный приказом Министерства образования Российской федерации от 01.01.2001г. № 72 мжд/сп.
Шифр дисциплины в ГОС ДС. Ф.03, федеральный компонент
Рабочая программа обсуждена на заседании кафедры Параллельных вычислительных технологий «25» апреля 2006 г. (протокол № 26)
Программу составил:
проф., д. т.н. _____________
Заведующий кафедрой ПВТ
проф., д. т.н. _____________
Ответственный за основную
образовательную программу
заведующий кафедрой ПСиБД _____________
1. Внешние требования
Требования к обязательному минимуму содержания учебной дисциплины
Таблица 1
Шифр дисциплины | Содержание учебной дисциплины | Часы |
ЕН. В.01 | «Специальные главы дискретной математики»: Теория множеств: понятие множества, алгебра множеств, теорема Бернштейна, понятие отношения, эквивалентность, упорядочивание; Математическая логика: теория предикатов первого порядка, интерпретация и вычисление формул, аксиоматические теории (непротиворечивость, полнота, | 100 |
1.3. Квалификационные требования
Математик-программист по специальности 351500 «Математическое обеспечение и администрирование информационных систем» подготовлен преимущественно к выполнению исследовательской деятельности в областях, использующих методы прикладной математики и компьютерные технологии; к разработке и применению современных математических методов и программного обеспечения для решения задач науки, техники, экономики и управления; к использованию информационных технологий в проектно-конструкторской, управленческой и финансовой деятельности.
7.1. Требования к профессиональной подготовленности специалиста
Математик-программист по специальности 351500 «Математическое обеспечение и администрирование информационных систем»:
должен обладать:
- теоретическими знаниями и практическими навыками, соответствующими основной образовательной программе подготовки настоящего государственного образовательного стандарта..
должен знать и уметь использовать:
основные понятия и методы дискретной математики основы теории алгоритмов и ее применения, основные структуры данных, архитектурные особенности современных ЭВМ; синтаксис, семантику и формальные способы описания языков программирования, способы и механизмы управления данными;иметь опыт:
- работы на различных типах ЭВМ, применения стандартных алгоритмических языков, использования приближенных методов и стандартного программного обеспечения для решения прикладных задач.
должен:
- обладать знаниями и умениями, позволяющими применять современные математические методы и программное обеспечение для решения задач науки, техники, экономики и управления и использования информационных технологий в проектно-конструкторской, управленческой и финансовой деятельности. быть способен к совершенствованию своей профессиональной деятельности в области прикладной математики и информатики.
2. Особенности (принципы) построения дисциплины
Курс входит в число дисциплин по выбору.
Таблица 2
Особенность (принцип) | Содержание |
Основание для введения дисциплины в учебный план направления | Стандарт специальности, федеральный компонент. |
Адресат дисциплины | Студенты специальности: 010503 – Математическое обеспечение и администрирование информационных систем |
Главная цель дисциплины | Расширение знаний дискретной математики и формирование практических навыков применения математических методов в проектировании и реализации прикладных систем |
Ядро дисциплины | Лекции, посвященные компьютерным приложениям классических результатов математической логики (например, теорема полноты Гёделя, тезис Черча), лекции, посвященные аксиоматическому построению теории алгоритмов и теории последовательных взаимодействующих процессов, комбинаторным подходам к решению задач и оптимизации их решений, систематически излагаются актуальные основы современных математических теорий, широко используемых в информатике и особенно в программировании. Курс обеспечивает углубленное изучение той части материала, который не вошел в основной курс дискретной математики. |
Требования к начальной подготовке, необходимые для успешного освоения дисциплины | Желательно знакомство с университетскими курсами по
|
Уровень требований по сравнению со Стандартом | Соответствует требованиям Стандарта |
Объем дисциплины в часах | 18 часа лекций, 18 часов практических занятий, 84 часа самостоятельных занятий |
Основные понятия дисциплины | Теория множеств, математическая логика, аксиоматические теории, теория алгоритмов как аксиоматическая теория, теория последовательных взаимодействующих процессов. |
Обеспечение последующих дисциплин образовательной программы | Основы параллельного программирования, Параллельные вычислительные методы, Формальные модели параллельных вычислений, дипломное проектирование |
Практическая часть дисциплины | Состоит из практических занятий - решаются задачи из упражнений к лекционным разделам |
Направленность дисциплины на развитие общепредметных, общеинтеллектуальных умений, обладающих свойством переноса, направленность на саморазвитие | Обобщение, анализ, синтез, классификация, абстрагирование, моделирование, выделение главного. |
Дисциплина и современные информационные технологии | Современные информационные технологии являются предметом исследования и освоения, а так же используются как средство для чтения лекций, проведения практических занятий. |
3. Цели учебной дисциплины
После изучения дисциплины студент будет
Таблица 3
Номер цели | Содержание цели |
Студент будет знать: | |
1 | Об избранных понятиях логики высказываний и логик первого порядка |
2 | Об основных принципах построения аксиоматических теорий |
3 | Примеры конструирования аксиоматических теорий |
4 | Аксиоматическую теорию алгоритмов и ее приложения в конструировании языков программирования |
5 | Аксиоматическую теорию взаимодействующих процессов и ее приложения в программировании. |
Студент будет уметь: | |
6 | Разрабатывать формальную спецификацию задачи, конструировать алгоритмы решения и проверять правильность решения задач. |
4.Содержание и структура учебной дисциплины
Структура учебной дисциплины
Таблица 4
Ссылки на цели курса | Часы | Темы лекционных занятий |
1 | 2 | Избранные вопросы теории множеств и теории формальных языков. Наивная теория множеств, отношения и функции: основные понятия, определения, свойства и теоремы. |
1, 2 | 4 | Аксиоматические теории (непротиворечивость, полнота, независимость). Аксиоматические теории высказываний и предикатов 1-го порядка. Интерпретации и модели, реализация в программе. |
2, 3 | 4 | Понятия вычисления в математической логике и теории алгоритмов. Теория алгоритмов как аксиоматическая теория. Формализация Клини понятия вычислимой функции, Операторы суперпозиции, примитивной рекурсии и минимизации и их термальное представление. Понятие детерминанта вычислимой функции |
1, 3, 4 | 4 | Понятие представления алгоритма и программы, непроцедурность представлений. Сложность и реализуемость алгоритмов. Параллельные алгоритмы и программы. |
1, 2, 5 | 4 | Теория последовательных взаимодействующих процессов. Формализация понятия процесс, протоколы, поведение, состояние процесса. Способы записи процессов, Спецификация процесса, взаимодействующие процессы. Сети Петри, функционирование и поведение. |
Таблица 5
Ссылки на цели курса | Часы | Темы практических занятий | Учебная деятельность |
1 | 4 | Избранные понятия теории множеств, отношения эквивалентности и порядка. | Решение задач на доказательство равенства и вложенности множеств, задачи на доказательства свойств бинарных отношений, решение задач с использованием теоремы об отношении эквивалентности, решение задач на нахождение максимального, наибольшего, минимального, наименьшего значений множества. |
1 | 4 | Использование комбинаторных схем в практических задачах, подстановки, комбинаторные конфигурации, урновые схемы. Полные переборные алгоритмы в практических задачах. | Использование комбинаторных конфигураций (сочетания, размещения, перестановки) в практических задачах. Применение урновых схем. Оценка количества операций для задач полного перебора. |
2, 3 | 2 | Избранные понятия исчисления высказываний, теории предикатов первого порядка. Интерпретации и модели, реализация в программе. | Доказательство общезначимости, выполнимости формул. Применение понятия интерпретации в практических задачах. |
1, 2 | 2 | Полные переборные алгоритмы и оценка их сложности. Динамическое программирование. | Оценка количества операций для задач полного перебора, решение оптимизационной задачи методом динамического программирования. |
2, 3, 4 | 4 | Формализация Клини понятия вычислимой функции, Использование операторов суперпозиции, примитивной рекурсии и минимизации для построения функций. | Построение основных примитивно рекурсивных функций (сумма, произведение, функция знака, …). Построение некоторых частично рекурсивных функций. |
2, 3, 5 | 2 | Системы последовательных взаимодействующих процессов, протоколы, спецификация процессов. | Построение спецификации процессов. Построение простейших процессов, построение процессов с использованием операторов выбора. Построение протокола процесса. Построение взаимодействующих процессов. |
5. Учебная деятельность
Самостоятельная работа в течение семестра состоит в подготовке к практическим занятиям и лекциям по каждой теме курса. Те темы, которые не прорабатываются на практических занятиях: интерпретации и модели, реализация в программе, понятие детерминанта вычислимой функции, непроцедурность представлений алгоритма студенты осваивают самостоятельно. При этом уровень усвоения материала должен обеспечивать применение этих понятий в практических задачах (например, использование комбинаторных конфигураций и урновых схем, построение сложных примитивно рекурсивных и частично рекурсивных функций, построение сложных взаимодействующих процессов).
6. Правила аттестации студентов по учебной дисциплине
Оценка знаний и умений студентов проводится с помощью устного экзамена, на котором каждому студенту предлагается ответить на два теоретических вопроса и решить 2 задачи по основным темам курса. Оценку «удовлетворительно» получает студент, решивший одну практическую задачу и ответивший на один теоретический вопрос. Оценку «хорошо» получает студент, решивший две практические задачи и ответивший на один теоретический вопрос. Оценку «отлично» получает студент, решивший две практические задачи и ответивший на оба теоретических вопроса.
7. Литература
Основная литература
, . Элементы теории функций и функционального анализа. Наука, М., 1972. . Прикладная логика. Новосибирск, Изд-во НГУ, 2000 И. Лавров, Л. Максимова. Задачи по теории множеств, математической логике и теории алгоритмов. Наука, 1984 . Алгоритмы и рекурсивные функции. - М. Наука. 1986. , Параллельное программирование мультикомпьютеров. Изд-во НГТУ, 2006 г. Э. Рейнгольд, Ю. Нивергельт, Н. Део. Комбинаторные алгоритмы: теория и практика. Мир, 1980. Евстигнеев, Касьянов. Теория графов. Новосибирск, Наука, 1998, 385с. заимодействующие последовательные процессы. М., Мир, 1989. аука программирования. М., Мир, 1984. лгоритмы: построение и анализ. МЦНМО, 2000 г. , , Дискретная математика. Изд-во АСТ, Астрель. 2003 г. Андерсон Дж. Дискретная математика и комбинаторика. Изд-во Вильямс, 2003 г.Дополнительная литература
8. Контролирующие материалы для аттестации
студентов по учебной дисциплине
Экзаменационные вопросы
Понятие множества. Конечные и бесконечные множества. Операции над множествами. Примеры. Понятие отношения. Примеры. Отношение эквивалентности. Основная теорема. Фактор-множества. Обобщенное равенство. Абстракция. Примеры Понятие функции. График функции. Суперпозиция функций. Примеры. Отношение порядка. Частичный порядок. Изоморфизм частично упорядоченных множеств. Примеры Аксиоматические теории. Непротиворечивость, полнота и независимость системы аксиом. Интерпретация исчисления высказываний и предикатов. Истинностные значения формулы. Неформальные свойства понятия алгоритма, понятия алфавита, слова, терма. Простейшие вычислимые функции. Оператор суперпозиции. Оператор примитивной рекурсии, алгоритм его вычисления, его термальная форма. Определение класса примитивно-рекурсивных функций. Примитивная рекурсивность функций сложения и умножения Доказательство существования вычислимых не примитивно рекурсивных функций (не использовать контрпример). Оператор минимизации. Определение класса частично-рекурсивных функций. Понятие алгоритма. Абстракция понятия процесса. Примеры процессов. Описание процессов. Префиксная запись. Примеры. Рекурсивное описание процессов. Примеры. Предваренная форма. Оператор выбора. Примеры. Начальное меню процесса. Графическое представление процесса. Состояние процесса. Понятие протокола. Поведение процесса. Примеры. Взаимодействие процессов. Параллельные процессы Спецификация процесса. Классы задач: P и NP; NP-полные задачи. Представление и реализация алгоритма. Непроцедурность представления алгоритма. Сравнительная непроцедурность языков программирования. Сложность алгоритма. Полиномиальная и экспоненциальная сложности. Понятие сети Петри. Задание частичного порядка с использованием сети Петри. Определение взаимного исключения. Необходимые условия дедлока. Методы борьбы с дедлоком. Алгоритм банкира.
Дополнения и изменения к рабочей программе на 20 /20 учебный год
В рабочую программу вносятся следующие изменения: |
Рабочая программа пересмотрена и одобрена на заседании кафедры «___» ______ 200 г.
Заведующий кафедрой
«___»__________20 г.
