Рабочая программа по дисциплине В. В математическая логика и теория алгоритмов






Скачать 222.86 Kb.
НазваниеРабочая программа по дисциплине В. В математическая логика и теория алгоритмов
Дата публикации29.01.2015
Размер222.86 Kb.
ТипРабочая программа
l.120-bal.ru > Документы > Рабочая программа


МИНОБРНАУКИ РОССИИ
Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования
«МАЙКОПСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ»
Факультет Инженерно-экономический
Кафедра Высшей математики и системного анализа


УТВЕРЖДАЮ

Проректор по учебной работе

____________Л.И. Задорожная

«_____»____________ 20____г.

РАБОЧАЯ ПРОГРАММА
по дисциплине В.В.2.2. Математическая логика и теория алгоритмов

по направлению

подготовки бакалавров 090900.62 Информационная безопасность

по профилю подготовки Организация и технология защиты информации
Квалификация (степень)

выпускника Бакалавр


МАЙКОП

Рабочая программа составлена на основе ФГОС ВПО и учебного плана МГТУ по направлению 090900.62 Информационная безопасность.

Составитель рабочей программы:

доцент, кандидат экономических наук _____________ Кузьменко Н.А.

(должность, ученое звание, степень) (подпись) (Ф.И.О.)
Рабочая программа утверждена на заседании кафедры

высшей математики и системного анализа

(наименование кафедры)
Заведующий кафедрой

«___»________20___г. _____________ ДёминаТ.И.

(подпись) (Ф.И.О.)
Одобрено научно-методической комиссией факультета

(где осуществляется обучение) «___»_______20__г.
Председатель

научно-методического

совета направления (специальности)

(где осуществляется обучение) _____________ _______________

(подпись) (Ф.И.О.)
Декан факультета

(где осуществляется обучение)

«___»________20___г. _____________ _______________

(подпись) (Ф.И.О.)


СОГЛАСОВАНО:

Начальник УМУ

«___»________20___г. __________ Гук Г.А.

(подпись) (Ф.И.О.)
Зав. выпускающей кафедрой

по направлению (специальности) ___________ _____________

(подпись) (Ф.И.О.)


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


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

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

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

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

  1. раскрыть роль и значение математических методов исследования при решении задач;

  2. ознакомить с основными понятиями и методами классической и современной математики;

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


2. Место дисциплины в структуре ОП по направлению подготовки
Дисциплина «Математическая логика и теория алгоритмов» относится к вариативной части математического и естественнонаучного цикла дисциплин (Б2.В.3). Для изучения дисциплины «Математическая логика и теория алгоритмов» необходимы начальные знания по алгебре, математическому анализу, дискретной математике и базовые знания по математическим дисциплинам за курс средней общеобразовательной школы. Понятия и методы дисциплины используются при изучении других дисциплин математического и естественнонаучного и профессионального циклов.
3. Компетенции обучающегося, формируемые в результате освоения дисциплины

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

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

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

- способностью к саморазвитию, самореализации, приобретению новых знаний, повышению своей квалификации и мастерства (ОК-11);

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

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

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

- способностью осуществлять подбор, изучение и обобщение научно-технической литературы, нормативных и методических материалов по вопросам обеспечения информационной безопасности (ПК-24);
В результате изучения дисциплины «Математическая логика и теория алгоритмов» студенты должны:

Знать:

  • основные понятия и методы математики;

  • методику математического исследования прикладных задач.

Уметь:

  • при решении задач выбирать и использовать необходимые вычислительные методы в зависимости от поставленной задачи;

  • логически правильно строить рассуждения при решении задач;

Владеть:

  • навыками составления оптимизационных моделей;

  • логикой высказываний и предикатов; теорией сложности и алгоритмов;


4. Объем дисциплины и виды учебной работы
4.1. Объем дисциплины и виды учебной работы по очной форме обучения.

Общая трудоемкость дисциплины составляет 4 зачетных единицы (144 часа).

Вид учебной работы

Всего

часов/з.е.

Семестры

4

Аудиторные занятия (всего)

64/1,78

64/1,78

В том числе:







Лекции (Л)

32/0,89

32/0,89

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







Семинары (С)

32/0,89

32/0,89

Лабораторные работы (ЛР)







Самостоятельная работа студентов (СРС) (всего)

80/2,22

80/2,22

В том числе:







Курсовой проект (работа)







Расчетно-графические работы

8/0,22

8/0,22

Реферат







Другие виды СРС (если предусматриваются, приводится перечень видов СРС)

1. Составление плана-конспекта

2. Подготовка к текущим занятиям

3. Подбор и анализ примеров



10/0,28

14/0,39

12/0,33



10/0,28

14/0,39

12/0,33

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

экзамен


36/1

36/1

Общая трудоемкость


144/4

144/4


4.2. Объем дисциплины и виды учебной работы по заочной форме обучения.

Заочная форма обучения не предусмотрена
5. Структура и содержание дисциплины

5.1. Структура дисциплины для очной формы обучения

1 семестр:

п/п

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

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

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

(в часах)

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

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

(по семестрам)

Л

С/ПЗ

ЛР

СРС




1.

Множества и отображения.

1-2

4

4




8

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

2.

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

3-6

8

8




10

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

3.

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

7-10

8

8




10

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

4.

Элементы теории алгоритмов

11-16

12

12




16

Тестирование




Промежуточная аттестация.













36

Экзамен




ИТОГО:




32

32




80





5.2. Структура дисциплины для заочной формы обучения

Заочная форма обучения не предусмотрена


5.3. Содержание разделов дисциплины «Математическая логика», образовательные технологии

Лекционный курс

п/п

Наименование темы дисциплины

Трудоемкость (часы/

зач. ед.)


Содержание

Формируемые компетенции

Результаты освоения

(знать, уметь, владеть)

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

Тема 1.

Множества и отображения.

4/0,12

Алгебра множеств. Операции над множествами. Число элементов подмножеств конечных множеств.

Счетные и несчетные множества. Мощность. Теорема Кантора о множестве подмножеств.

Функции и отображения. Образ и прообраз. Композиции и обратные отображения. Отношения эквивалентности и порядка. Упорядоченные множества.

ОК-

8,9,11

ПК-1,2,20,24

Знать: основные научные принципы и базовые понятия теории множеств и отображений

Уметь: устанавливать отношения эквивалентности и порядка; проводить операции над множествами;

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

Слайд - лекции

Тема 2.

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

8/0,22

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

Нормальные формы высказываний. Релейно-контактные схемы.

Булевы функции. Функции алгебры логики. Многочлены Жегалкина. Критерий полноты (теорема Поста).

Исчисление высказываний. Аксиомы и правило Modus ponens. Полнота и непротиворечивость исчисления высказываний.

ОК-

8,9,11

ПК-1,2,20,24

Знать: основные понятия и определения исчисления высказываний;

Уметь: применять формулы алгебры высказываний; приводить к нормальным формам, многочленам Жегалкина; выяснять полноту и непротиворечивость высказываний;

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

Лекция - визуализация

Тема 3.

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

8/0,22

Предикаты. Кванторы. Логические операции над предикатами Выразимые предикаты. Арифметические предикаты.

Синтаксис и семантика языка предикатов. Общезначимые формулы. Аксиомы и правила вывода.

Непротиворечивость и полнота исчисления предикатов (теорема Геделя).

ОК-

8,9,11

ПК-1,2,20,24

Знать: методы практического построения и анализа исчисления предикатов;

Уметь: проводить логические операции над предикатами; выяснять полноту и непротиворечивость предикатов;

Владеть: навыками освоения большого объема информации и решения сложных и нестандартных задач.

Лекции в традиционной форме

Тема 4.

Элементы теории алгоритмов

12/0,33

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

Нумерации и операции. Главные универсальные функции и множества. Свойства главных нумераций и перечислимые свойства функций. Теорема о неподвижной точке (теорема Клини).

Машины Тьюринга. Понятие алгоритма по Тьюрингу. Алгоритмически разрешимые и неразрешимые проблемы.

Арифметичность вычислимых функций. Теоремы Гёделя и Тарского.

Рекурсивные функции. Примитивно и частично рекурсивные функции. Тезис Чёрча. Оценки скорости роста и сложность алгоритмов.

ОК-

8,9,11

ПК-1,2,20,24

Знать: основные научные принципы и базовые понятия элементов теории алгоритмов; свойства главных нумераций и перечислимые свойства функций;

Уметь: работать с вычислимыми функциями, главными универсальными функциями и множествами; вычислять рекурсии функций;

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

Лекции в традиционной форме




Итого

32/0,89















5.4. Практические и семинарские занятия, их наименование, содержание и объем в часах


п/п

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

Наименование практических и семинарских занятий

Объем в часах/трудоемкость в з.е.

  1. 1

Множества и отображения.

Алгебра множеств. Операции над множествами. Мощность множества.

4/0,11



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

Алгебра высказываний. Таблицы истинности. Тавтологии и эквивалентность.

8/0,22



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

Логические операции над предикатами. Действия с кванторами.

8/0,22



Элементы теории алгоритмов

Вычислимые функции. Машины Тьюринга.

12/0,34




Итого




32/0,89


5.5. Лабораторные занятия, их наименование и объем в часах


п/п

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

Наименование лабораторных работ

Объем в часах/трудоемкость в з.е.

-

-

-

-


5.6. Примерная тематика курсовых проектов (работ)

Курсовой проект (работа) учебным планом не предусмотрен.

5.7. Самостоятельная работа студентов ОФО


Разделы и темы рабочей программы самостоятельного изучения

Перечень домашних заданий и других вопросов для самостоятельного изучения

Сроки выполнения

Объем в часах/трудоемкость в з.е.

Раздел 1. Функции: композиции обратные, образ и прообраз.

Подготовка к текущим занятиям,

Подбор и анализ примеров,

Работа с учебной литературой.

1-2

неделя

8/0,22

Раздел 2. Нормальные формы. Релейно-контактные схемы. Булевы функции. Многочлены Жегалкина. Полнота систем функций. Исчисление высказываний. Аксиомы и правило Modus ponens. Полнота и непротиворечивость исчисления высказываний.

Подготовка к текущим занятиям,

Составление плана-конспекта.

Работа с учебной литературой.

Выполнение и анализ письменных графо-аналитических работ по теме.

3-6

неделя

10/0,28

Раздел 3. Непротиворечивость и полнота исчисления предикатов (теорема Геделя). Синтаксис и семантика языка предикатов. Общезначимые формулы. Аксиомы и правила вывода

Подготовка к текущим занятиям,

Работа с учебной литературой.

Подбор задач.

Выполнение и анализ письменных графо-аналитических работ по теме.

7-10

неделя

10/0,28

Раздел 4. Теорема о неподвижной точке (теорема Клини). Арифметичность вычислимых функций. Теоремы Гёделя. Рекурсивные функции. Примитивно и частично рекурсивные функции. Тезис Чёрча.Оценки скорости роста и сложности алгоритмов

Подготовка к текущим занятиям,

Составление плана-конспекта.

Работа с учебной литературой.

Выполнение и анализ письменных графо-аналитических работ по теме.

Подбор и анализ примеров.

11-16

неделя

16/0,44

Промежуточная аттестация.







36/1

Итого







80/2,22


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

6.1. Контрольные вопросы и задания для проведения текущего контроля для студентов ОФО
Примерный вариант контрольной работы по теме: «Множества и отображения».


  1. Для следующих отображений найти композиции , .




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

, дают тождественное отображение:




  1. Для следующего отображения найти , , , :



Ответ пояснить графиком.

  1. Для следующего отображения найти и b :




  1. Пусть — множество всех вещественных непрерывных функций. Проверить, является ли следующее отображение инъективным, сюръективным, биективным. Найти обратное к нему с соответствующей стороны:


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

а) Вы обязаны что-то сделать, значит, вы делаете это.

б) Если закон всемирного тяготения верен, с его помощью можно открыть другие законы. Закон всемирного тяготения верен, поэтому с его помощью могут быть открыты другие законы.

в) Если к телу, движущемуся равномерно и прямолинейно, не подводится сила, оно движется без ускорения; тело движется без ускорения; значит, к нему не подводится сила.

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

«Между тем как в моей повозке запрягали лошадей, приехала еще кибитка, тройкою запряженная».

Задание 3. Сформулируйте высказывание, если: А- «Логика является разделом математики», В- «Логика- это раздел философии», С- «Логика изучается на юридическом факультете»

Задание 4. Запишите с помощью символов высказывание и определите его тип. Составьте оставшиеся три компоненты логического квадрата. Выделите пары противных, подчиненных, подпротивных, противоречащих.

а) «Всякий моряк умеет плавать»,

б) «На всякого мудреца довольно простоты».

Задание 5. Определите с помощью таблиц истинности, какие из приведенных формул являются тавтологиями:

а) ;

б) .
Примерный вариант контрольной работы по теме: «Исчисление предикатов».
Задание 1. Формализуйте высказывание. Получите ДНФ, СДНФ, КНФ, СКНФ, СПНФ. Представьте высказывание в виде суперпозиции только следующих операций: 1) «штрих Шеффера, 2) «стрелка Пирса», 3) «импликация» и «отрицание», 4) «импликация» и «константа нуля».

  1. «Если я замолчу- возопиют камни и реки потекут вспять».



Задание 2. Докажите или опровергните общезначимость формулы, используя законы алгебры логики и формулы равносильных преобразований:
6.2. Контрольные вопросы и задания для проведения промежуточной аттестации.

Примерный перечень вопросов к экзамену по дисциплине «Математическая логика»



  1. Множества, операции над множествами. Подмножества. Основные свойства.

  2. Сочетания, размещения и перестановки в конечных множествах. Число подмножеств.

  3. Счетные множества. Примеры. Несчетность точек интервала (0;1)

  4. Равномощность бесконечных множеств. Теорема Кантора о множестве подмножеств

  5. Отображения. Композиции отображений. Образ и прообраз. Инъективность, сюръективность и биективность.

  6. Бинарные отношения. Функция как отношение.

  7. Отношение эквивалентности. Классы эквивалентности

  8. Отношение порядка. Упорядоченные и вполне упорядоченные множества.

  9. Высказывания, операции над высказываниями. Равносильные высказывания.

  10. Формулы алгебры высказываний.

  11. Существование и единственность КНФ и ДНФ. Связь КНФ и ДНФ

  12. Релейно-контактные схемы: анализ и синтез. Конструирование при помощи элемента «и-не»

  13. Исчисление высказываний: алфавит, формулы, аксиомы.

  14. Теорема о непротиворечивости исчисления высказываний

  15. Теорема о полноте исчисления высказываний

  16. Предикаты. Логические операции над предикатами. Основные свойства

  17. Кванторы. Основные равносильности с кванторами

  18. Многочлены Жегалкина. Существование и единственность представления функции алгебры логики многочленом Жегалкина

  19. Невыразимые предикаты. Изоморфизмы. Примеры

  20. Исчисление предикатов: алфавит, формулы, аксиомы, правила вывода.

  21. Связанные и свободные вхождения переменных в предикат. Правила подстановки

  22. Общезначимые формулы. Теорема о полноте и непротиворечивости исчисления предикатов

  23. Существование главной универсальной функции.

  24. Привести пример универсальной вычислимой функции, не являющейся главной.

  25. Теорема о неподвижной точке.

  26. Программа, печатающая собственный текст.

  27. Машина Тьюринга, переписывающая слово задом наперед.

  28. Алгоритм умножения в языке с конечным числом переменных.

  29. Алгоритм возведения в квадрат в языке с конечным числом переменных.

  30. Алгоритм b:=a[i] в языке с конечным числом переменных (массив а кодируется числом по основной теореме арифметики) .

  31. Арифметические формулы для всех типов команд в языке с
    конечным числом переменных.

  32. Теорема Тарского о невыразимости арифметики

  33. Теорема Гёделя о неполноте арифметики


6.3. Тематика контрольных работ для студентов ЗФО

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

  1. ЭБС «Znanium.com» Игошин, В. И. Математическая логика: учебное пособие / В.И. Игошин. - М.: ИНФРА-М, 2012. - 399 с.: - Режим доступа: http://znanium.com/

  2. Лавров, И.А. Математическая логика : учеб. пособие для студентов вузов / И.А. Лавров ; под ред. Л.Л. Максимовой. - М. : Академия, 2006. - 240 с.


б) дополнительная литература

  1. ЭБС «Znanium.com» Игошин, В. И. Теория алгоритмов: учебное пособие / В.И. Игошин. - М.: ИНФРА-М, 2012. - 318 с.: - Режим доступа: http://znanium.com/

  2. Игошин, В.И. Математическая логика и теория алгоритмов : учеб. пособие для студентов вузов / В.И. Игошин. - М. : Академия, 2008. - 448 с.


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

  1. http://www.exponenta.ru – Образовательный математический сайт Exponenta.ru.

  2. http://www.matclub.ru – Лекции, примеры решения задач. Электронные учебники.

  3. http://www. math.ru – Образовательный математический сайт Math.ru.

  4. http://www. mathelp.spb.ru – Лекции по высшей математике: математический анализ; дифференциальные уравнения; аналитическая геометрия, теория вероятностей и др.

  5. Калькулятор с функциями.

  6. Компьютер с программным обеспечением.


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

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

1) библиотечный фонд ФГБОУ ВПО «МГТУ»;

2) мультимедийное оборудование для чтения лекций-презентаций.

Дополнения и изменения в рабочей программе

за ________/________ учебный год

В рабочую программу ____________________________________________________

(наименование дисциплины)

для направления (специальности) ___________________________________________________

(номер направления (специальности)

вносятся следующие дополнения и изменения:

Дополнения и изменения внес _______________________________________________

(должность, Ф.И.О., подпись)

Рабочая программа пересмотрена и одобрена на заседании кафедры _____________________________________________________________________________

(наименование кафедры)

«____»___________________20___г.

Заведующий кафедрой __________________ _____________

(подпись) (Ф.И.О.)

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

Похожие:

Рабочая программа по дисциплине В. В математическая логика и теория алгоритмов iconРабочая программа дисциплины Математическая логика и теория алгоритмов Направление
Целями освоения дисциплины «Математическая логика и теория алгоритмов» являются получение теоретических знаний по основам математическая...

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

Рабочая программа по дисциплине В. В математическая логика и теория алгоритмов iconРабочая программа составлена в соответствии с требованиями фгос впо...
Дёгтев А. Н. Теория алгоритмов. Учебно-методический комплекс. Рабочая программа для студентов направления 010100. 62 – математика,...

Рабочая программа по дисциплине В. В математическая логика и теория алгоритмов iconРабочая программа дисциплины министерство образования и науки российской...
Рабочая программа дисциплины по дисциплине «Математическая логика и теория алгоритмов» составлена в соответствии с требованиями государственного...

Рабочая программа по дисциплине В. В математическая логика и теория алгоритмов iconРабочая программа дисциплины Математическая логика и теория алгоритмов
Федеральное государственное автономное образовательное учреждение высшего профессионального образования

Рабочая программа по дисциплине В. В математическая логика и теория алгоритмов iconУчебно-методический комплекс по дисциплине «Математическая логика и теория алгоритмов»
Сперанский Д. В., доктор технических наук, профессор кафедры «Высшая и прикладная математика»

Рабочая программа по дисциплине В. В математическая логика и теория алгоритмов iconА. Л. Гудков 16 января 2012 г
«Математическая логика и теория алгоритмов» является формирование представлений о методах и моделях описания предметной и проблемной...

Рабочая программа по дисциплине В. В математическая логика и теория алгоритмов iconЛогика и теория алгоритмов 4 семестр 2013-14 уч г, спец. Иу7 модуль 1: Теория алгоритмов
Б. А. Кушнер. Лекции по конструктивному математическому анализу. – М.: Наука, 1973. – 448 с

Рабочая программа по дисциплине В. В математическая логика и теория алгоритмов iconПравительство Российской Федерации Нижегородский филиал
Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 035800. 62 «Фундаментальная...

Рабочая программа по дисциплине В. В математическая логика и теория алгоритмов iconМатематическая логика и теория алгоритмов
Большое внимание уделено практическим аспектам обсуждаемых понятий: автоматизации логического вывода, проверки корректности программ,...

Вы можете разместить ссылку на наш сайт:


Литература


При копировании материала укажите ссылку ©ucheba 2000-2015
контакты
l.120-bal.ru
..На главную