Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направлени - davaiknam.ru o_O
Главная
Поиск по ключевым словам:
страница 1
Похожие работы
Название работы Кол-во страниц Размер
Программа дисциплины [Введите название дисциплины] для направления/... 8 663.57kb.
Программа дисциплины [Введите название дисциплины] для направления/... 1 230.86kb.
Программа дисциплины [Введите название дисциплины] для направления/... 1 192.94kb.
Программа дисциплины «Разработка и технология производства рекламного... 5 338.54kb.
Программа дисциплины [Введите название дисциплины] для направления/... 5 347.67kb.
Программа дисциплины [Введите название дисциплины] для направления/... 1 314.05kb.
Программа дисциплины [Введите название дисциплины] для направления/... 1 129.88kb.
Программа дисциплины [Введите название дисциплины] для направления/... 4 410.56kb.
Программа дисциплины для направления/ специальности подготовки бакалавра/... 1 283.24kb.
Программа дисциплины для направления/ специальности подготовки бакалавра/... 4 390.6kb.
Программа дисциплины Финансирование проектов частно-государственного... 1 338.52kb.
Программа дисциплины «математическая логика» 1 233.76kb.
Направления изучения представлений о справедливости 1 202.17kb.

Программа дисциплины [Введите название дисциплины] для направления/ специальности - страница №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Основная литература


  1. Колмогоров А.Н., Драгалин А.Г. Математическая логика.

Москва: Издание 2-е, стереотипное: Едиториал УРСС (Классический университетский учебник), 2005

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


теории алгоритмов.
Москва: Издание 5-е, исправленное, ФИЗМАТЛИТ, 2004

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


  1. Андерсон Джеймс А. Дискретная математика и комбинаторика./ Пер. М.М. Беловой/ .Москва:

Издательский дом “Вильямс”, 2002.

  1. Вирт Никлаус. Алгоритмы и структуры данных. Санкт-Петербург:

Невский диалект, 2001.

  1. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. Москва:

Энергоатомиздат, 1988.

  1. Лихтарников Л.М., Сукачева Т.Г. Математическая логика. Санкт-Петербург:

Изд-во “Лань”, 1998.

  1. Нефедов В.Н., Осипова В.А. Курс дискретной математики. Москва:

Изд-во МАИ, 1992.

  1. Овчинников В.А. Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем. Москва:Изд-во МГТУ им. Баумана, 2001.



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


Материально-техническое обеспечение дисциплины за исключением наличия аудитории не требуется.




Реальность — это иллюзия, вызываемая отсутствием алкоголя. Норман Фредерик Симпсон
ещё >>