Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Национальный исследовательский университет "Высшая школа экономики"





Скачать 138.27 Kb.
НазваниеПравительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования "Национальный исследовательский университет "Высшая школа экономики"
Дата публикации31.07.2013
Размер138.27 Kb.
ТипПрограмма дисциплины
100-bal.ru > Математика > Программа дисциплины


Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
"Национальный исследовательский университет
"Высшая школа экономики"


Факультет прикладной математики и кибернетики
Программа дисциплины

Математическая логика и теория алгоритмов
Для направления 230400.62 «Информационные системы и технологии» подготовки бакалавра

Автор программы: Лившиц М.И., канд. физ.-мат. наук, доцент, mlivshits@hse.ru

Одобрена на заседании кафедры Высшая математика «___»____________ 2013 г.
Зав. кафедрой Л.И.Кузьмина
Рекомендована учебно-методической комиссией ФПМиК «___»____________ 2013 г.
Председатель
Утверждена учёным советом ФПМиК «___»_____________2013 г.
Ученый секретарь ________________________

Москва, 2013

1Область применения и нормативные ссылки


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

Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 230400.62 «Информационные системы и технологии» подготовки бакалавра, изучающих дисциплину «Математическая логика и теория алгоритмов».

Программа разработана в соответствии с:

Образовательным стандартом ФГОС ВПО по направлению подготовки 230400 Прикладная математика и информатика (квалификация (степень) "бакалавр");

Рабочим учебным планом университета по направлению подготовки 230400.62 «Информационные системы и технологии» подготовки бакалавров, утвержденным в 2012 г.

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


Целями освоения дисциплины «Математическая логика и теория алгоритмов» являются

получение представления об основных понятиях, методах и результатах теории вычислимости;

 получение представления об основных понятиях и методах алгебры логики;

 получение представления об исчислениях высказываний и предикатов

3Компетенции обучающегося, формируемые в результате освоения дисциплины


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

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

 Уметь применять свои знания в указанных областях при решении конкретных задач.

Иметь навыки формализации неформальных рассуждений
В результате освоения дисциплины студент осваивает следующие компетенции:

способность к работе в коллективе, кооперации с коллегами, способностью в качестве руководителя подразделения, лидера группы сотрудников формировать цели команды, принимать организационно-управленческие решения в ситуациях риска и нести за них ответственность, предупреждать и конструктивно разрешать конфликтные ситуации в процессе профессиональной деятельности (ОК-6);

способность логически верно, аргументировано и ясно строить устную и письменную речь на русском языке, готовить и редактировать тексты профессионального назначения, публично представлять собственные и известные научные результаты, вести дискуссии (ОК-7);

способность к логически правильному мышлению, обобщению, анализу, критическому осмыслению информации, систематизации, прогнозированию, постановке исследовательских задач и выбору путей их решения на основании принципов научного познания (ОК-9);

способность самостоятельно применять методы и средства познания, обучения и самоконтроля для приобретения новых знаний и умений, в том числе в новых областях, непосредственно не связанных со сферой деятельности, развития социальных и профессиональных компетенций, изменения вида своей профессиональной деятельности (ОК-10);

способностью выявлять естественнонаучную сущность проблем, возникающих в ходе профессиональной деятельности, и применять соответствующий физико-математический аппарат для их формализации, анализа и выработки решения (ПК-1);

способность применять математический аппарат, в том числе с использованием вычислительной техники, для решения профессиональных задач (ПК-2);

способность готовить научно-технические отчеты, обзоры, публикации по результатам выполненных работ (ПК-17).

4Место дисциплины в структуре образовательной программы


Настоящая дисциплина относится к математическому и блоку дисциплин, обеспечивающих математическую подготовку.

Изучение данной дисциплины базируется на следующих дисциплинах:

математический анализ

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

основные определения и простейшие базисные факты математического анализа,

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

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

  1. Тематический план учебной дисциплины






Название раздела

Всего часов

Аудиторные часы

Самостоятельная работа

Лекции

Семи нары

Практические занятия

1

Множества и мощности множеств

9

6




3

10

2

Машина с неограниченными регистрами (МНР), МНР-вычислимость

9

6




3

10

3

Вычислимые функции. Разрешимые и перечислимые множества.

8

5




3

6

4

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

9

6




3

10

5

Замкнутые классы булевых функций

3

2




1

4

6

Исчисление высказываний

9

6




3

10

7

Исчисление предикатов

7

5




2

10




Итого

54

36




18

60

5Формы контроля знаний студентов





Тип контроля

Форма контроля знаний студентов





Параметры

Текущий

(неделя)

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

8

Письменная работа 80 минут

Коллоквиум

10




Домашнее задание

14




Итоговый

Экзамен


*

Устный



5.1Критерии оценки знаний, навыков



На контрольной работе студент должен продемонстрировать умение применять математический аппарат к решению конкретных задач.

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

Оценки по всем формам текущего контроля выставляются по 10-ти балльной шкале.

Порядок формирования оценок по дисциплине
Преподаватель оценивает работу студентов на практических занятиях: активность студентов в дискуссиях, правильность решения задач на семинаре. Оценки за работу на семинарских и практических занятиях преподаватель выставляет в рабочую ведомость. Накопленная оценка по 10-ти балльной шкале за работу на семинарских и практических занятиях определяется перед промежуточным или итоговым контролем - Оаудиторная.


Преподаватель оценивает самостоятельную работу студентов: х. Оценки за самостоятельную работу студента преподаватель выставляет в рабочую ведомость. Накопленная оценка по 10-ти балльной шкале за самостоятельную работу определяется перед промежуточным или итоговым контролем – Осам. работа.

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

Онакопленная= 0,6*Отекущий + 0,2*Оауд + 0,2*Осам.работа .

где Отекущий рассчитывается как взвешенная сумма всех форм текущего контроля, предусмотренных в РУП

Отекущий = 0,5·Ок/р + 0,3·Окол + 0,2·Одз .

Способ округления накопленной оценки текущего контроля: в пользу студента.

Результирующая оценка за дисциплину рассчитывается следующим образом:

Орезульт = 0,6накопл + 0,4экз .

Способ округления накопленной оценки итогового контроля в форме экзамена: в пользу студента.

На экзамене студент может получить дополнительный вопрос (дополнительную практическую задачу, решить к пересдаче домашнее задание), ответ на который оценивается в 1 балл.

6Содержание дисциплины



Раздел 1. Множества и мощности множеств (9 часов)

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

Определение неравенства между мощностями множеств. Теорема Кантора-Бернштейна. Несчетность множества всех бесконечных последовательностей, составленных из 0 и 1.

Самостоятельная работа - 10 часов

Раздел 2. Машина с неограниченными регистрами (МНР). МНР-вычислимость (9 часов)

Машина с неограниченными регистрами (МНР). Система нумерации МНР-команд и МНР-программ. МНР-вычислимые функции. Разрешимые предикаты.

Теорема о вычислимости суперпозиции вычислимых функций.

Самостоятельная работа - 10 часов

Раздел 3. Вычислимые функции. Разрешимые и перечислимые множества (8 часов)

Неформальные алгоритмы. Тезис Черча. Теорема о существовании МНР-невычислимых

функций.

Универсальная функция и условие ее существования. Теоремы об универсальной функции для множества всех МНР-вычислимых функций и для множества всех тотальных МНР-вычислимых функций одного переменного.

Разрешимые и неразрешимые проблемы. Неразрешимость проблемы тотальности функции, проблемы самоприменимости, проблемы остановки.

Разрешимые и перечислимые множества. Теорема о перечислимости любого разрешимого множества. Теорема о существовании перечислимых неразрешимых множеств. Теорема Поста.

Самостоятельная работа - 6 часов

Раздел 4. Функции алгебры логики (9 часов)

Функции алгебры логики (булевы функции). Конъюнкция, дизъюнкция, отрицание, импликация, эквивалентность, таблица истинности.

Таблица истинности. n-мерный единичный куб, его грани и вершины. Определение формулы. Задание булевых функций с помощью формул, вопрос о его единственности. Равносильность формул. Основные соотношения с равносильными формулами.

Элементарная конъюнкция. Дизъюнктивная нормальная форма (ДНФ) булевой функции, совершенная дизъюнктивная нормальная форма (СДНФ). Существование единственной СДНФ для любой ненулевой булевой функции.

Сокращенная дизъюнктивную нормальную форму. Правила склеивания и поглощения. Тупикования ДНФ

Полином Жегалкина булевой функции. Теорема о его существовании и единственности.

Самостоятельная работа - 10 часов

Раздел 5. Замкнутые классы булевых функций (3 часа)

Двойственные и самодвойственные булевы функции. Монотонные булевы функции. Функциональное замыкание совокупности булевых функций. Функционально замкнутые совокупности. Полные совокупности. Классы S, L, M, T0, T1, их функциональная замкнутость и полнота. Теорема Поста о полноте.

Самостоятельная работа - 4 часа

Раздел 6. Исчисление высказываний (9 часов)

Язык, аксиомы и правила вывода исчисления высказываний. Формальный вывод из гипотез в ИВ. Теорема дедукции. Определение интерпретации исчисления высказываний. Тавтологии и критерий выводимости в исчислении высказываний.

Формулы в исчислении высказываний, являющиеся тавтологией. Критерий выводимости формулы в исчислении высказываний

Самостоятельная работа - 10 часов

Раздел 7. Исчисление предикатов (7 часов)

Язык исчисления предикатов (ИП). Интерпретация ИП. Общезначимые формулы ИП.

Самостоятельная работа - 10 часов

7Образовательные технологии


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

8Оценочные средства для текущего контроля и аттестации студента

8.1Тематика заданий текущего контроля



Задание 1 по теме “Мощности множеств и теория вычислимости”.
1. а) Найти мощность бесконечного множества непересекающихся кругов, принадлежащих данной плоскости.

б) Что можно сказать о мощности бесконечного множества окружностей данной плоскости, имеющих общий центр?

2. Привести пример взаимно однозначного соответствия между интервалом (0,1) и отрезком [0,1].

3. Выписать явно МНР-программу с номером 8.

Чему равно значение функции от двух переменных, вычислямой по этой программе, в точке (1,2)?

4. Написать программу, вычисляющую функцию f(x,y) = xy+x+1.

Задание 2 по теме “Алгебра логики” и “Исчисление высказываний”.


  1. Для функции f (x1, x2, x3) = (1,1,0,0,1,0,1,0) найти совершенную ДНФ, сокращённую ДНФ, одну из кратчайших, тупиковых и минимальных ДНФ. Найти многочлен Жегалкина для данной функции. Выяснить, является ли полным класс функций f (x1, x2, x3) и g(x1, x2, x3) = (1,1,0,0).

2. Полна ли система функций {(01101001), (10001101), (00011100)}?

3. Построить вывод формулы (AA).

4.Показать, что .

8.2Вопросы для оценки качества освоения дисциплины


Примерный перечень вопросов к экзамену по всему курсу:


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

  2. Определить равномощные множества. Доказать, что множество всех бесконечных последовательностей чисел 0 и 1 равномощно множеству всех подмножеств множества натурального ряда чисел {1, 2, 3,…}.

  3. Определить счетные множества. Доказать счётность любого бесконечного подмножество счетного множества. Доказать, что всякое бесконечное множество содержит счетное подмножество.

  4. Доказать, что объединение счетного множества конечных или счетных множеств есть счетное множество.

  5. Доказать, что если A – бесконечное множество и B – конечное или счетное множество, то A равномощно объединению A с B.

  6. Несчетность множества всех бесконечных последовательностей, составленных из 0 и 1.

  7. Доказать, что отрезок [0,1] равномощен множеству всех бесконечных последовательностей, составленных из 0 и 1. Вывести отсюда, что квадрат равномощен отрезку.

  8. Доказать теорему Кантора. Вывести из нее, что множество всех бесконечных последовательностей, составленных из 0 и 1 несчетно.

  9. Сравнение мощностей двух множеств. Теорема Кантора--Бернштейна.

  10. Описать машину с неограниченными регистрами (МНР). Команды, программа, начальная конфигурация и результат для МНР.

  11. Определить МНР-вычислимую функцию.

  12. Определить предикат и разрешимый предикат.

  13. Неформальный алгоритм. Сформулировать тезис Черча.

  14. Нумерация МНР-команд и МНР-программ.

  15. Доказать существование МНР-невычислимых функций.

  16. Определить универсальную функцию для заданного множества заданных функций.

  17. Доказать существование универсальной функции для множества всех МНР-вычислимых функций одного переменного.

  18. Доказать, что для множества тотальных МНР-вычислимых функций одного пременного не существует универсальной функции.

  19. Дать определение разрешимой и неразрешимой проблемы.

  20. Неразрешимость проблемы тотальности функции.

  21. Неразрешимость проблемы самоприменимости.

  22. Неразрешимость проблемы остановки.

  23. Определить разрешимые и перечислимые множества в Ns. Перечислимость разрешимого множества.

  24. Описать дополнение к перечислимому множеству. Доказать теорему Поста о разрешимости множества.

  25. Определить функцию алгебры логики от n переменных. Определить конъюнкцию, дизъюнкцию, импликацию, отрицание и эквивалентность.

  26. Таблица истинности булевой функции. Мощность множества булевых функций от n переменных. Определить n-мерный единичный куб, его вершины и грани. Множество истинности булевой функции.

  27. Определить элементарную конъюнкцию. Элементарная конъюнкция и грань n-мерного куба.

  28. Определить дизъюнктивную нормальную форму булевой функции и совершенную дизъюнктивную нормальную форму (СДНФ). Доказать единственность СДНФ для ненулевой булевой функции.

  29. Определить сокращенную дизъюнктивную нормальную форму булевой функции. Сформулировать и обосновать правила обобщенного склеивания и поглощения. Определить тупиковую дизъюнктивную нормальную форму. Определить минимальную и кратчайшую дизъюнктивную нормальную форму.

  30. Определить полином Жегалкина. Получить количество различных полиномов Жегалкина от n переменных и доказать, что каждая булева функция может быть представлена единственным полиномом Жегалкина.

  31. Определить двойственные и что такое самодвойственные булевы функции. Определить монотонную булеву функцию.

  32. Определить функционально замкнутую совокупность булевых функций. Определить полную совокупность булевых функций. Описать классы S, L, M, T0, T1 и доказать, что они функционально замкнуты и неполны.

  33. Сформулировать теорему Поста о полноте.

  34. Определить язык исчисления высказываний (ИВ). Описать алфавит и формулы в ИВ.

  35. Аксиомы и правила вывода исчисления высказываний. Выводимые формулы.

  36. Дать определение формального вывода из гипотез в ИВ. Сформулировать теорему дедукции.

  37. Дать определение интерпретации исчисления высказываний. Определить тавтологию и сформулировать критерий выводимости в исчислении высказываний.

  38. Определить понятие квантора. Определить свободные и связанные переменные.

  39. Определить язык исчисления предикатов (ИП).

  40. Определить интерпретацию ИП. Общезначимые формулы ИП.



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


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

Н. К. Верещагин, А. Шень, Начала теории множеств, МЦНМО, М., 1999

Н. К. Верещагин, А. Шень, Лекции по математической логике и теории алгоритмов. Вычилимые функции, МЦНМО, М., 1999

Н. Катленд, Вычислимость. Введение в теорию рекурсивных функций, Мир, М., 1983

И. А. Лавров, Л. Л. Максимова, Задачи по теории множеств, математической логике и теории алгоритмов, Наука, М., 1984

Дополнительная литература

В. А. Успенский, Н. К. Верещагин, В. Е. Плиско. Вводный курс математической логики. М.,

«Физматлит», 2004.

Н. К. Верещагин, А. Шень, Языки и исчисления, МЦНМО, М., 2000

Г. П. Гаврилов, А. А. Сапоженко, Сборник задач по дискретной математике, Наука, М., 1977 В. А. Душский, Исчисление высказываний и его свойства, МИЭМ, М., 2007


Добавить документ в свой блог или на сайт

Похожие:

Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования \"Национальный исследовательский университет \"Высшая школа экономики\" iconПравительство Российской Федерации Государственное образовательное...
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования \"Национальный исследовательский университет \"Высшая школа экономики\" iconПравительство Российской Федерации Федеральное государственное автономное...
Нормативные документы, использованные при разработке основной образовательной программы 5
Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования \"Национальный исследовательский университет \"Высшая школа экономики\" iconПравительство Российской Федерации Федеральное государственное автономное...
Баскаков Владимир Анатольевич, старший преподаватель кафедры Маркетинга и Рекламы
Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования \"Национальный исследовательский университет \"Высшая школа экономики\" iconПравительство Российской Федерации Федеральное государственное автономное...
Искать учебные ресурсы лучше на соответствующих страницах крупных образовательных порталов
Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования \"Национальный исследовательский университет \"Высшая школа экономики\" iconПравительство Российской Федерации Федеральное государственное автономное...
Фгбоу впо «поволжская государственная академия физической культуры, спорта и туризма»
Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования \"Национальный исследовательский университет \"Высшая школа экономики\" iconПравительство Российской Федерации Федеральное государственное автономное...
Устав образовательного учреждения. (Наличие и правильность оформления раздела по охране труда)
Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования \"Национальный исследовательский университет \"Высшая школа экономики\" iconПравительство Российской Федерации Федеральное государственное автономное...
Тема Дискретная случайная величина, способы ее задания. Числовые характеристики. Функция распределения и ее свойства. 19
Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования \"Национальный исследовательский университет \"Высшая школа экономики\" iconПравительство Российской Федерации Федеральное государственное автономное...
Гос впо по специальности подготовки 080507. 65 Менеджмент организации, утвержденный Министерством образования РФ «17» марта 2000...
Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования \"Национальный исследовательский университет \"Высшая школа экономики\" iconПравительство Российской Федерации Федеральное государственное автономное...
В соответствии с Законом Челябинской области "О стимулировании туристско-рекреационной деятельности в Челябинской области" Правительство...
Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования \"Национальный исследовательский университет \"Высшая школа экономики\" iconПравительство Российской Федерации Федеральное государственное автономное...
Рабочая программа составлена на основании рабочего учебного плана по фгос, переутвержденного ученым советом юргту (нпи) протоколом...
Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования \"Национальный исследовательский университет \"Высшая школа экономики\" iconПравительство Российской Федерации Федеральное государственное автономное...
...
Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования \"Национальный исследовательский университет \"Высшая школа экономики\" iconПравительство Российской Федерации Федеральное государственное автономное...
П18 Паремические жанры русского фольклора [Текст]: методические рекомендации по изучению курса / З. Ж. Кудаева – Нальчик: Каб. Балк...
Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования \"Национальный исследовательский университет \"Высшая школа экономики\" iconПравительство Российской Федерации Федеральное государственное автономное...
О порядке аттестации лиц, претендующих на замещение вакантной должности руководителя краевого государственного образовательного учреждения,...
Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования \"Национальный исследовательский университет \"Высшая школа экономики\" iconПравительство Российской Федерации Федеральное государственное автономное...
Форма обучения – очная, заочная, заочная (сокращенная) на базе впо, очно-заочная (вечерняя) на базе спо
Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования \"Национальный исследовательский университет \"Высшая школа экономики\" icon«Национальный исследовательский университет «Высшая школа экономики»
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
Правительство Российской Федерации Федеральное государственное автономное образовательное учреждение высшего профессионального образования \"Национальный исследовательский университет \"Высшая школа экономики\" iconНациональный исследовательский университет высшая школа экономики
Федеральное государственное автономное образовательное учреждение высшего профессионального образования


Школьные материалы


При копировании материала укажите ссылку © 2013
контакты
100-bal.ru
Поиск