Программа дисциплины [Введите название дисциплины] для направления/ специальности - страница №1/1
|
Национальный исследовательский университет «Высшая школа экономики»
Программа дисциплины [Введите название дисциплины] для направления/ специальности
[код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста
|
Правительство Российской Федерации
Федеральное государственное автономное образовательное учреждение высшего профессионального образования
"Национальный исследовательский университет
"Высшая школа экономики"
Факультет Информационных технологий и вычислительной техники
Программа дисциплины Математическая логика и теория алгоритмов
для направления 230100 “Информатика и вычислительная техника” подготовки бакалавра
Автор программы:
Афонина Л.М.
E-mail: lafonina@hse.ru
Одобрена на заседании кафедры Вычислительные системы и сети «___»____________ 20 г
Зав. кафедрой А.В. Вишнеков
Рекомендована секцией УМС [Введите название секции УМС] «___»____________ 20 г
Председатель [Введите И.О. Фамилия]
Утверждена УС факультета Информационных технологий и вычислительной техники «___»_____________20 г.
Ученый секретарь [Введите И.О. Фамилия] ________________________ [подпись]
Москва, 2012
1Область применения и нормативные ссылки
Настоящая программа учебной дисциплины устанавливает минимальные требования к знаниям и умениям студента и определяет содержание и виды учебных занятий и отчетности.
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки 230100 “Информатика и вычислительная техника”, изучающих дисциплину “Математическая логика и теория алгоритмов”.
-
Программа разработана в соответствии с: Федеральным государственным образовательным стандартом высшего профессионального образования по направлению 230100 "Информатика и вычислительная техника" (квалификация "бакалавр"); Образовательной программой по направлению 230100.62 "Информатика и вычислительная техника" подготовки бакалавра по специализации "Вычислительные машины, комплексы, системы и сети"; Рабочим учебным планом университета по направлению 230100.62 "Информатика и вычислительная техника" подготовки бакалавра по специализации "Вычислительные машины, комплексы, системы и сети".
2Цели освоения дисциплины
Целью освоения дисциплины “Математическая логика и теория алгоритмов” является изучение понятий и практическое освоение методов математической логики и теории алгоритмов с ориентацией на их использование в задачах практической информатики.
3Компетенции обучающегося, формируемые в результате освоения дисциплины
В результате освоения дисциплины студент должен:
-
основные понятия математической логики и теории алгоритмов,
-
канонические формы представления, методы преобразования и минимизации булевых функций,
-
формальный язык логики,
-
методы логического вывода и оценки сложности алгоритмов.
-
использовать язык математической логики для представления знаний о предметных областях,
-
доказывать логическое следование формул,
-
определять временную и емкостную сложность алгоритмов.
-
Иметь навыки (приобрести опыт):
-
владения методами формального доказательства логического следования и оценки сложности алгоритмов,
-
владения способами использования аппарата математической логики в задачах практической информатики.
В результате освоения дисциплины студент осваивает следующие компетенции:
|
|
|
|
Компетенция
|
Код по ФГОС/ НИУ
|
Дескрипторы – основные признаки освоения (показатели достижения результата)
|
Формы и методы обучения, способствующие формированию и развитию компетенции
|
Компетенции по ФГОС ВПО по направлению 230100
|
Владение культурой мышления, способность к обобщению, анализу, восприятию информации, постановке цели и выбору путей ее достижения.
|
ОК-1
|
Владеет логическим мышлением, способен к обобщениям, анализу, восприятию информации, способен ставить цели и выбирать пути ее достижения.
|
Изложение материала на лекциях, закрепление в на практических занятиях, а также в ходе выполнения домашних заданий и контрольных работ.
Использование методических материалов в печатном и электронном виде (методические указания).
|
Использование основных законов естественно - научных дисциплин в профессиональной деятельности, применение методов математического анализа и моделирования, теоретического и экспериментального исследования.
|
ОК-10
|
Использует законы естественно – научных дисциплин в профессиональной деятельности, способен применять методы математического анализа, а также моделирования в процессе теоретических и экспериментальных исследований.
|
Изложение материала на лекциях, закрепление в на практических занятиях, а также в ходе выполнения домашних заданий и контрольных работ.
Использование методических материалов в печатном и электронном виде (методические указания).
|
|
|
|
|
4Место дисциплины в структуре образовательной программы
Настоящая дисциплина относится к циклу профессиональных дисциплин ОПД и блоку дисциплин, обеспечивающих базовую подготовку.
Изучение данной дисциплины базируется на следующих дисциплинах:
-
Дискретная математика;
-
Информатика;
-
Программирование;
-
Теория автоматов.
Для освоения учебной дисциплины, студенты должны владеть следующими знаниями и компетенциями:
-
должен владеть основами теории множеств (понятие множества, теоретико-множественные операции); основами теории алгоритмов (понятие и свойства алгоритма); основами программирования (типы и структуры данных, процедуры, функции).
Основные положения дисциплины должны быть использованы в дальнейшем при изучении следующих дисциплин:
-
Информационные технологии;
-
Информационные системы;
-
Математическое и имитационное моделирование
-
Сети и телекоммуникации
-
Схемотехника
5Тематический план учебной дисциплины
№
|
Название раздела
|
Всего часов
|
Аудиторные часы
|
Самостоятельная работа
|
Лекции
|
Семинары
|
Практические занятия
|
1
|
Логика высказываний.
|
7
|
1
|
|
2
|
4
|
2
|
Нормальные формы формул.
|
11
|
1
|
|
2
|
8
|
3
|
Полные системы булевых функций.
|
9
|
1
|
|
2
|
6
|
4
|
Минимизация в классе ДНФ и КНФ.
Контактные схемы. Схемы из функциональных элементов.
|
21
|
2
|
|
4
|
15
|
5
|
Исчисление высказываний.
|
13
|
1
|
|
2
|
10
|
6
|
Логика предикатов.
|
18
|
1
|
|
2
|
15
|
7
|
Исчисление предикатов.
|
18
|
1
|
|
2
|
15
|
8
|
Элементы теории алгоритмов.
|
11
|
1
|
|
2
|
8
|
|
Итого:
|
108
|
9
|
|
18
|
81
|
6Формы контроля знаний студентов
Тип контроля
|
Форма контроля
|
1 год
|
Параметры **
|
1
|
2
|
3
|
4
|
Текущий
(неделя)
|
Контрольная работа
|
|
|
5
|
|
Письменная работа 60 минут
|
Итоговый
|
Зачет
|
|
|
*
|
|
Устный зачет проводится в форме ответов на вопросы билетов. Время подготовки первого студента 40 мин.
|
6.1Критерии оценки знаний, навыков
В процессе текущего контроля студент должен продемонстрировать:
-
владение культурой мышления, способность к обобщению, анализу, восприятию информации (ОК-1);
-
способность к постановке цели и выбору путей ее достижения (ОК-1).
На итоговом контроле студент должен продемонстрировать:
-
способность использования основных законов естественно - научных дисциплин в профессиональной деятельности, применение методов математического анализа и моделирования, теоретического и экспериментального исследования (ОК-10).
Оценки по всем формам контроля выставляются по 10-ти балльной шкале.
6.2Порядок формирования оценок по дисциплине
Преподаватель оценивает работу студентов на практических занятиях: наличие подготовленных дома заданий по вариантам согласно варианту задания (Оподг), качество ответов в процессе практической работы в аудитории (Окач). Оценки за работу на практических занятиях преподаватель ставит в рабочую ведомость. Накопленная оценка по 10-ти балльной шкале определяется перед промежуточным контролем – Оаудиторная.
Оаудиторная = 0.01* Окач.
Способ округления накопленной оценки текущего контроля: арифметический.
Преподаватель оценивает контрольную работу в аудитории контр., самостоятельную работу студентов: правильность выполнения домашних работ, задания для которых выдаются по вариантам согласно методическим указаниям. Оценки за контрольные работы и самостоятельную работу студента преподаватель выставляет в рабочую ведомость. Накопленная оценка по 10-ти балльной шкале определяется перед итоговым контролем – Осам. работа.
Накопленная итоговая оценка перед зачетом рассчитывается следующим образом:
Онакопл = 0.8* Оконтр. + 0.2*Осам.работа
Способ округления накопленной оценки итогового контроля: арифметический.
Оценка Оаудиторная учитывается в качестве бонуса и добавляется к Онакопл.
Результирующая оценка за дисциплину рассчитывается следующим образом:
Орезульт = 0.8* Онакопл + 0.2*·Озач
, где Озач - это оценка за ответ.
На зачете студент может получить дополнительный вопрос (дополнительную практическую задачу, решить к пересдаче домашнее задание), ответ на который оценивается в 1 балл.
На пересдаче зачета студенту не предоставляется возможность получить дополнительный балл для компенсации оценки за текущий контроль.
Способ округления оценки итогового контроля в форме зачета: арифметический.
В диплом выставляет результирующая оценка по учебной дисциплине Орезульт.
7Содержание дисциплины
Модуль 3 (1-й курс)
№ п/п
|
Наименование раздела и темы
|
Часы
|
лекц.
|
прак.
|
сам.р.
|
1
|
2
|
3
|
4
|
5
|
-
|
Логика высказываний
|
1
|
2
|
4
|
-
Язык логики высказываний.
-
Формулы логики высказываний.
-
Равносильность формул.
-
Интерпретация формул.
-
Общезначимость, выполнимость, противоречивость.
-
Методы анализа выполнимости и общезначимости формул.
|
0.1
0.2
0.1
0.1
0.1
0.4
|
0.5
0.5
1
|
1
1
1
1
|
Литература:
[1] – глава 1."Введение в математическую логику" параграфы 6,7,8
http://zaharova-le10.narod.ru
Формы проведения занятий:
изложение лекционного материала ,
проведение практических занятий.
|
-
|
Нормальные формы формул.
|
1
|
2
|
8
|
-
Тавтологии.
-
Правильные рассуждения.
-
Двойственность.
-
Закон двойственности.
-
Алгоритмы приведения формул в КНФ и ДНФ.
-
Базовый алгоритм проверки общезначимости КНФ.
-
Разрешимость.
-
Алгоритмы получения СДНФ и СКНФ формул.
|
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.3
|
0.5
1
0.5
|
1
2
1
2
2
|
Литература:
[1] – глава 2."Введение в математическую логику" параграфы 5,6
http://zaharova-le10.narod.ru
Формы проведения занятий:
изложение лекционного материала ,
проведение практических занятий.
|
-
|
Полные системы булевых функций.
|
1
|
2
|
6
|
-
Булевы функции.
-
Суперпозиция функций.
-
Функционально замкнутые классы.
-
Теорема Поста.
-
Таблица Поста.
-
Независимые системы функций.
-
Базис функционально замкнутого класса. k-значные логики.
|
0.2
0.1
0.1
0.1
0.2
0.2
0.1
|
0.5
0.5
0.5
0.5
|
2
1
1
1
1
|
Литература:
[1] – глава 1."Введение в математическую логику" параграф 6
http://zaharova-le10.narod.ru
Формы проведения занятий:
изложение лекционного материала ,
проведение практических занятий.
|
-
|
Минимизация в классе ДНФ и КНФ. Контактные схемы. Схемы из функциональных элементов.
|
2
|
4
|
15
|
-
Определение минимальной ДНФ (КНФ).
-
Метод минимизирующих карт для получения минимальной ДНФ.
-
Применение логики высказываний к контактным схемам и к схемам из функциональных элементов.
|
0.5
1
0.5
|
1
2
1
|
2
10
3
|
Литература:
[1] – глава 1."Введение в математическую логику" параграфы 5,6
http://zaharova-le10.narod.ru
Формы проведения занятий:
изложение лекционного материала ,
проведение практических занятий.
|
-
|
Исчисление высказываний.
|
1
|
2
|
10
|
-
Аксиоматические теории.
-
Определения и свойства исчисления высказываний.
-
Две системы аксиом.
-
Правило вывода m.p.
-
Логическое следование, проблема дедукции.
-
Принцип дедукции.
-
Теорема о дедукции.
-
Следствия из теоремы о дедукции.
-
Полнота и непротиворечивость исчисления высказываний.
-
Независимость аксиом.
|
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
0.1
|
1
0.5
0.5
|
3
2
3
2
|
Литература:
[1] – глава 3."Введение в математическую логику" параграф 2,3
http://zaharova-le10.narod.ru
Формы проведения занятий:
изложение лекционного материала ,
проведение практических занятий.
|
6
|
Логика предикатов.
|
1
|
2
|
15
|
-
Предикаты.
-
Формулы логики предикатов.
-
Равносильность формул логики предикатов.
-
Синтаксис и семантика языка логики предикатов.
-
Приведенные и нормальные формы формул логики предикатов.
-
Теорема Черча.
-
Выполнимость и общезначимость формул логики предикатов.
|
0.1
0.3
0.1
0.1
0.2
0.1
0.1
|
0.5
0.5
1
|
5
2
4
4
|
Литература:
[1] – глава 1."Введение в математическую логику" параграф 9
[1] – глава 3."Введение в математическую логику" параграф 1
[1] – "Математическая логика. Дополнительные главы" глава 2 параграф 2
http://zaharova-le10.narod.ru
Формы проведения занятий:
изложение лекционного материала ,
проведение практических занятий.
|
7
|
Исчисление предикатов.
|
1
|
2
|
15
|
-
Аксиомы и правила вывода исчисления предикатов.
-
Ослабленная теорема о дедукции.
-
Общезначимость выводимых в исчислении предикатов формул.
-
Полнота и непротиворечивость исчисления предикатов.
-
Теорема Геделя.
|
0.2
0.1
0.1
0.4
0.2
|
1
1
|
7
2
6
|
Литература:
[1] – "Математическая логика. Дополнительные главы" глава 3 параграф 2
http://zaharova-le10.narod.ru
Формы проведения занятий:
изложение лекционного материала ,
проведение практических занятий.
|
8
|
Элементы теории алгоритмов.
|
1
|
2
|
8
|
-
Определение и примеры машины Тьюринга.
-
Тезис Тьюринга.
-
Рекурсивные функции.
-
Тезис Черча.
-
Нормальные алгоритмы Маркова.
|
0.5
0.1
0.2
0.1
0.3
|
1
1
|
4
4
|
Литература:
[1] – "Математическая логика. Дополнительные главы" глава 2 параграфы 1,2,3
http://zaharova-le10.narod.ru
Формы проведения занятий:
изложение лекционного материала ,
проведение практических занятий.
|
Итого:
|
9
|
18
|
81
|
8Образовательные технологии
Лекционный материал излагается под презентации, которые размещены в интернете на странице www.zaharova-le10.narod.ru. Занятия на практических работах ведутся в аудитории. Лабораторные занятия не предусмотрены.
8.1Методические указания студентам
-
Вести рабочую тетрадь с проработкой и заметками по изучаемым вопросам.
-
Готовиться дома к выполнению практических работ и приходить на занятия с подготовленным файлом с текстами запросов.
-
Для лучшего усвоения материала перед каждой лекцией знакомиться с лекционным материалом, который доступен в электронном виде на сайте www.zaharova-le2010.narod.ru.
-
По всем возникающим вопросам можно проконсультироваться лично у преподавателя в часы консультаций или по электронной почте.
9Оценочные средства для текущего контроля и аттестации студента
9.1Тематика заданий текущего контроля
Примерные вопросы заданий для контрольных и домашних работ на сайте www.zaharova-le10.narod.ru.
9.2Вопросы для оценки качества освоения дисциплины
-
Примерный перечень вопросов к зачету по всему курсу или к каждому промежуточному и итоговому контролю для самопроверки студентов на сайте www.zaharova-le10.narod.ru.
.
.
10Учебно-методическое и информационное обеспечение дисциплины
10.1Основная литература
-
Колмогоров А.Н., Драгалин А.Г. Математическая логика.
Москва: Издание 2-е, стереотипное: Едиториал УРСС (Классический университетский учебник), 2005
2. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и
теории алгоритмов.
Москва: Издание 5-е, исправленное, ФИЗМАТЛИТ, 2004
10.2Дополнительная литература
-
Андерсон Джеймс А. Дискретная математика и комбинаторика./ Пер. М.М. Беловой/ .Москва:
Издательский дом “Вильямс”, 2002.
-
Вирт Никлаус. Алгоритмы и структуры данных. Санкт-Петербург:
Невский диалект, 2001.
-
Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. Москва:
Энергоатомиздат, 1988.
-
Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Санкт-Петербург:
Изд-во “Лань”, 1998.
-
Нефедов В.Н., Осипова В.А. Курс дискретной математики. Москва:
Изд-во МАИ, 1992.
-
Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем. Москва:Изд-во МГТУ им. Баумана, 2001.
11Материально-техническое обеспечение дисциплины
Материально-техническое обеспечение дисциплины за исключением наличия аудитории не требуется.
Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направлени - davaiknam.ru o_O