Поиск

Полнотекстовый поиск:
Где искать:
везде
только в названии
только в тексте
Выводить:
описание
слова в тексте
только заголовок

Рекомендуем ознакомиться

'Доклад'
МОУ ДОД ЦДТ «Алые паруса» является муниципальным учреждением дополнительного образования детей, реализующим дополнительные образовательные программы ...полностью>>
'Календарно-тематический план'
Практика по профилю специальности (технологическая) проводится на сельскохозяйственных предприятиях под руководством преподавателей специальных дисци...полностью>>
'Документ'
1. Предметом вивчення дисципліни «Ділова українська мова» є мова ділового спілкування, окремої фахової галузі, представлена двома функціональними сти...полностью>>
'Внеклассное мероприятие'
Вступление. Зал украшен плакатами с высказываниями о русском языке. Ведущий. Язык, на котором мы говорим, красив и богат. Могуч и прекрасен наш родной...полностью>>

Математика и компьютерные науки (2)

Главная > Рабочая программа
Сохрани ссылку в одной из сетей:

РАБОЧАЯ ПРОГРАММА ДИСЦИПЛИНЫ (МОДУЛЯ)

Дискретный анализ

Направление подготовки

МАТЕМАТИКА И КОМПЬЮТЕРНЫЕ НАУКИ

Профиль подготовки

Квалификация (степень) выпускника

магистр

(бакалавр, магистр, дипломированный специалист)

Форма обучения

Очная

(очная, очно-заочная и др.)

г.__________ – 200____ г.

1. Цели освоения дисциплины.

Целями освоения дисциплины (модуля) "Дискретный анализ" являются:

формирование математической культуры студента, фундаментальная подготовка по ряду основных разделов теории дискретной оптимизации, теории интеллектуальных систем, овладение современным математическим аппаратом для дальнейшего использования при решении теоретических и прикладных задач.

2. Место дисциплины в структуре ООП ВПО.

Дискретный анализ относится к вариативной части цикла профессиональных дисциплин. Для её успешного изучения необходимы знания и умения, приобретенные в результате освоения курсов по дискретной математике, и теории дискретных функций и др.

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

3. Компетенции обучающегося, формируемые в результате освоения дисциплины (модуля): ОК-6, ОК-8, ОК-10, ПК-1, ПК-2, ПК-3, ПК-4, ПК-5, ПК-6, ПК-7, ПК-8, ПК-9, ПК-10, ПК-11, ПК-12, ПК-14, ПК-15, ПК-16, ПК-19, ПК-20, ПК-21, ПК-23, ПК-27, ПК-29.

В результате освоения дисциплины обучающийся должен:

1. Знать: основные понятия из рассматриваемых разделов дискретного анализа (таких, как функции алгебры логики, k-значная логика, дизъюнктивные нормальные формы ,кодирование информации и др.), определения и свойства математических объектов, используемых в этих областях, формулировки утверждений, методы их доказательства, возможные сферы их приложений.

2. Уметь: решать задачи теоретического и прикладного характера, относящиеся к разделам рассматриваемой теории, доказывать утверждения, строить модели объектов и понятий.

3. Владеть: математическим аппаратом дискретного анализа, методами доказательства утверждений в этих областях.

4. Структура и содержание дисциплины "Дискретный анализ".

Общая трудоемкость дисциплины составляет 8-9 зачетных единицы.

Раздел
дисциплины

Семестр

Неделя семестра

Виды учебной работы, включая

самостоятельную работу студентов
и трудоемкость (в часах)

Формы текущего контроля успеваемости

(по неделям

семестра)

Форма промежуточной аттестации (по семестрам)

Лек

Сем

Сам

Сумм

Функции алгебры логики

1

Функции алгебры логики. Существенные переменные. Равенства функций. Элементарные функции алгебры логики и их свойства

1

1

2

2

2

6

2

Формулы и суперпозиции. Тождества. Замыкания, замкнутость и полнота систем булевых функций.

1

2

2

2

2

6

3

Дизъюнктивная нормальная форма. Полнота системы {&, V, ~, 0, 1}.

1

3

2

2

2

6

4

Замкнутость классов T0, T1, L,S,M и их отличие от P2 и попарная невложимость друг в друга.

1

4

2

2

2

6

5

Теорема Поста о полноте в P2.

1

5

2

2

2

6

Контрольная

работа

6

Понятие базиса в замкнутом классе булевых функций. Понятие предполного класса в P2. Предполнота классов T0, T1, L, S, M.

1

6

2

2

2

6

7

Большая теорема Поста о структуре замкнутых классов в P2.

1

7

2

2

2

6

K-значная логика

8

Функции k-значной логики. Существенные переменные. Отношение равенства. Элементарные функции. Формулы. Суперпозиции. Замыкание, его свойства. Функциональные системы k-значной логики.

1

8

2

2

2

6

9

Лемма о равенстве U(R) U Pk(x1,x2)=R.

Лемма о неполноте в Pk множества M U {g1(x1, x2), g2(x1, x2)} при неполноте M

1

9

2

2

2

6

10

Полнота и выразимость для функциональных систем. Конечная порожденность Pk. R-множества. Конструктивность их описания. Замкнутость класса сохранения R-множества.

1

10

2

2

2

6

11

Критериальные системы в Pk. Теорема Кузнецова. Теорема о критериальности системы всех предполных классов в Pk.

1

11

2

2

2

6

12

Алгоритм проверки на полноту конечных систем в Pk.

1

12

2

2

2

6

13

Лемма Яблонского.

1

13

2

2

2

6

14

Теорема Слупецкого.

1

14

2

2

2

6

15

Теорема о полноте полиномов в Pk.

1

15

2

2

2

6

Контрольная работа

16

Континуальность множества замкнутых классов в Pk при k>2.

1

16

2

2

2

6

.

Экзамен

Дискретная оптимизация

1

Дизъюнктивные нормальные формы. Постановка задачи минимизации булевских функций. Примеры.

2

1

2

2

2

6

2

Функция Шеннона сложности булевой функции. Теорема об оценке L(n).

2

2

2

2

2

6

3

Геометрическая постановка задачи о минимизации б.ф. Импликант булевой функции. Сокращенная д.н.ф. Теорема о простых импликантах м.д.н.ф

2

3

2

2

2

6

4

Алгоритм Квайна-МакКласки построения сокращенной д.н.ф.

2

4

2

2

2

6

5

Правило Блейка. Теорема о сильных расширениях сокращенной д.н.ф.

2

5

2

2

2

6

6

Теорема о сокращенной м.д.н.ф. монотонной функции.

2

6

2

2

2

6

7

Тупиковые д.н.ф. Теорема о поглощении элементарных конъюнкций.

2

7

2

2

2

6

8

Алгоритм Яблонского построения всех т.д.н.ф. и его обоснование.

2

8

2

2

2

6

9

Регулярная грань. Теорема о д.н.ф. типа "сумма тупиковых".

2

9

2

2

2

6

10

Ядровая грань. Д.н.ф.Квайна. Теорема о д.н.ф. типа «пересечения минимальных»

2

10

2

2

2

6

Контрольная работа

11

Д.н.ф. типа "сумма минимальных". Цепные функции и их свойства.

2

11

2

2

2

6

12

Эвристические алгоритмы минимизации б.ф.

2

12

2

2

2

6

Элементы теории кодирования

13

Алфавитное кодирование. Теорема Маркова об однозначности декодирования.

2

13

2

2

2

6

14

Префиксные коды. Теоремы Крафта и Мак-Миллана-Крафта.

2

14

2

2

2

6

15

Коды, оптимальные по Хаффману. Алгоритм построения оптимального кода и его обоснование.

2

15

2

2

2

6

16

Равномерное кодирование. Код Хемминга, исправляющий одну ошибку.

2

16

2

2

2

6

Контрольная работа

Экзамен

5. Образовательные технологии: активные и интерактивные формы.

6. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины и учебно-методическое обеспечение самостоятельной работы студентов

В течение семестра студенты разбирают и решают задачи, указанные преподавателем к каждому семинару, разбирают и повторяют основные понятия и теоремы, доказанные на лекциях. Предусмотрены 4 контрольные работы.

1. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. М.: Наука, 2007 (второе издание)

7. Учебно-методическое и информационное обеспечение дисциплины.

основная литература:

1. Яблонский С.В. Введение в дискретную математику. М.: Наука, 2006 (второе издание).

2. Кудрявцев В.Б., Гаврилов Г.П., Яблонский С.В., Функции алгебры логики и клас- сы Поста. Наука, М., 1966.

3. Гаврилов Г.П., Сапоженко А.А. Сборник задач по дискретной математике. М.: Наука, 2007 (второе издание).

в) программное обеспечение и Интернет-ресурсы: не требуется.

8. Материально-техническое обеспечение дисциплины:

Аудитории для лекций и практических занятий (с необходимым техническим оснащением). Наличие рекомендованной литературы. Наличие электронных версий методических материалов для самостоятельной работы.

Программа составлена в соответствии с требованиями ФГОС ВПО с учетом рекомендаций и ПрООП ВПО по направлению и профилю подготовки

Авторы: доцент кафедры математической теории интеллектуальных систем механико-математического факультета МГУ имени М. В. Ломоносова к.ф.–м.н. А. С. Строгалов,

доцент кафедры математической теории интеллектуальных систем механико-математического факультета МГУ имени М. В. Ломоносова к.ф.–м.н. А. А. Часовских.

Рецензент: профессор кафедры математической теории интеллектуальных систем механико-математического факультета МГУ имени М. В. Ломоносова д.ф.–м.н. Э. Э. Гасанов

Программа одобрена на заседании

(Наименование уполномоченного органа вуза (УМК, НМС, Ученый совет)

от ___________ года, протокол № ________.



Скачать документ

Похожие документы:

  1. Математика и компьютерные науки (1)

    Рабочая программа
    формирование математической культуры студента, фундаментальная подготовка по ряду основных разделов теории интеллектуальных систем, овладение современным математическим аппаратом для дальнейшего использования при решении теоретических
  2. Математика и компьютерные науки (3)

    Рабочая программа
    формирование математической культуры студента, фундаментальная подготовка по ряду основных разделов теории интеллектуальных систем, овладение современным математическим аппаратом для дальнейшего использования при решении теоретических
  3. Аннотация программы учебной дисциплины «Методика преподавания математики» Направление 010200. 62 «Математика и компьютерные науки»

    Документ
    Целями освоения дисциплины «Методика преподавания математики» являются: формирование критического мышления и развитие у студентов прочного интереса к проблемам теории и методики преподавания математики, понимания неисчерпаемости и
  4. Учебной дисциплины «Численные методы» для направления 010200. 62 «Математика и компьютерные науки»

    Документ
    Изучение численных методов решения задач алгебры, математического анализа и дифференциальных уравнений, а также освоение методологических подходов разработки численных вычислений и изучение основных методов для решения задач исследовательского
  5. Аннотация программы учебной дисциплины «Фундаментальная и компьютерная алгебра» Направление: 010200. 62 «Математика и компьютерные науки»

    Документ
    – привитие общематематической культуры: умение логически мыслить, проводить доказательства основных утверждений, устанавливать логические связи между понятиями, применять полученные знания для решения алгебраических и геометрических

Другие похожие документы..