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

МИНОБРНАУКИ РОССИИ Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «МАЙКОПСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ» Факультет Инженерно-экономический Кафедра Высшей математики и системного анализа УТВЕРЖДАЮ Проректор по учебной работе ____________Л.И. Задорожная «_____»____________ 20____г. РАБОЧАЯ ПРОГРАММА по дисциплине В.В.2.2. Математическая логика и теория алгоритмов по направлению подготовки бакалавров 090900.62 Информационная безопасность по профилю подготовки Организация и технология защиты информации Квалификация (степень) выпускника Бакалавр МАЙКОП Рабочая программа составлена на основе ФГОС ВПО и учебного плана МГТУ по направлению 090900.62 Информационная безопасность. Составитель рабочей программы: доцент, кандидат экономических наук _____________ Кузьменко Н.А. (должность, ученое звание, степень) (подпись) (Ф.И.О.) Рабочая программа утверждена на заседании кафедры высшей математики и системного анализа (наименование кафедры) Заведующий кафедрой «___»________20___г. _____________ ДёминаТ.И. (подпись) (Ф.И.О.) Одобрено научно-методической комиссией факультета (где осуществляется обучение) «___»_______20__г. Председатель научно-методического совета направления (специальности) (где осуществляется обучение) _____________ _______________ (подпись) (Ф.И.О.) Декан факультета (где осуществляется обучение) «___»________20___г. _____________ _______________ (подпись) (Ф.И.О.) СОГЛАСОВАНО: Начальник УМУ «___»________20___г. __________ Гук Г.А. (подпись) (Ф.И.О.) Зав. выпускающей кафедрой по направлению (специальности) ___________ _____________ (подпись) (Ф.И.О.) Цели и задачи освоения дисциплины Целями освоения дисциплины «Математическая логика и теория алгоритмов» является формирование личности студентов, развитие их интеллекта и способностей к логическому и алгоритмическому мышлению, обучение основным математическим понятиям и методам математического анализа, , необходимым для анализа и моделирования устройств, процессов и явлений при поиске оптимальных решений практических задач, методам обработки и анализа результатов численных и натурных экспериментов. Дисциплина является одной из важнейших теоретических и прикладных математических дисциплин, определяющих уровень профессиональной подготовки современного инженера. Цель преподавания прикладных разделов дисциплины состоит в том, чтобы, используя теорию и методы научного познания овладеть основными понятиями, определениями и методами теории вероятностей и математической статистики, необходимыми для решения задач в области авиаперевозок; обучить студентов математическим методам принятия решений, необходимым при решении задач оптимизации, возникающих во всех областях человеческой деятельности, математическим методам организации транспортного процесса, в частности - при планировании и управлении процессами перевозок и организации авиаперевозок. Преподавание дисциплины состоит в том, чтобы на примерах математических понятий и методов продемонстрировать сущность научного подхода, специфику математики и её роль как способ познания мира, общности её понятий и представлений в решении возникающих проблем. При этом решаются следующие задачи: раскрыть роль и значение математических методов исследования при решении задач; ознакомить с основными понятиями и методами классической и современной математики; научить студентов применять методы математического анализа для построения математических моделей реальных процессов и явлений; 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 Множества и отображения. Алгебра множеств. Операции над множествами. Мощность множества. 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. Контрольные вопросы и задания для проведения текущего контроля для студентов ОФО Примерный вариант контрольной работы по теме: «Множества и отображения». Для следующих отображений найти композиции , . Для следующего отображения найти обратное и проверить, что композиции , дают тождественное отображение: Для следующего отображения найти , , , : Ответ пояснить графиком. Для следующего отображения найти и b : Пусть — множество всех вещественных непрерывных функций. Проверить, является ли следующее отображение инъективным, сюръективным, биективным. Найти обратное к нему с соответствующей стороны: Примерный вариант контрольной работы по теме: «Исчисление высказываний». Задание 1. Запишите логической формулой следующие умозаключения, и уточнить их справедливость тремя методами: а) Вы обязаны что-то сделать, значит, вы делаете это. б) Если закон всемирного тяготения верен, с его помощью можно открыть другие законы. Закон всемирного тяготения верен, поэтому с его помощью могут быть открыты другие законы. в) Если к телу, движущемуся равномерно и прямолинейно, не подводится сила, оно движется без ускорения; тело движется без ускорения; значит, к нему не подводится сила. Задание 2. Выявите структуру приведенного сложного высказывания, укажите, из каких простых высказываний оно образованно и с помощью каких логических связок: «Между тем как в моей повозке запрягали лошадей, приехала еще кибитка, тройкою запряженная». Задание 3. Сформулируйте высказывание, если: А- «Логика является разделом математики», В- «Логика- это раздел философии», С- «Логика изучается на юридическом факультете» Задание 4. Запишите с помощью символов высказывание и определите его тип. Составьте оставшиеся три компоненты логического квадрата. Выделите пары противных, подчиненных, подпротивных, противоречащих. а) «Всякий моряк умеет плавать», б) «На всякого мудреца довольно простоты». Задание 5. Определите с помощью таблиц истинности, какие из приведенных формул являются тавтологиями: а) ; б) . Примерный вариант контрольной работы по теме: «Исчисление предикатов». Задание 1. Формализуйте высказывание. Получите ДНФ, СДНФ, КНФ, СКНФ, СПНФ. Представьте высказывание в виде суперпозиции только следующих операций: 1) «штрих Шеффера, 2) «стрелка Пирса», 3) «импликация» и «отрицание», 4) «импликация» и «константа нуля». «Если я замолчу- возопиют камни и реки потекут вспять». Задание 2. Докажите или опровергните общезначимость формулы, используя законы алгебры логики и формулы равносильных преобразований: 6.2. Контрольные вопросы и задания для проведения промежуточной аттестации. Примерный перечень вопросов к экзамену по дисциплине «Математическая логика» Множества, операции над множествами. Подмножества. Основные свойства. Сочетания, размещения и перестановки в конечных множествах. Число подмножеств. Счетные множества. Примеры. Несчетность точек интервала (0;1) Равномощность бесконечных множеств. Теорема Кантора о множестве подмножеств Отображения. Композиции отображений. Образ и прообраз. Инъективность, сюръективность и биективность. Бинарные отношения. Функция как отношение. Отношение эквивалентности. Классы эквивалентности Отношение порядка. Упорядоченные и вполне упорядоченные множества. Высказывания, операции над высказываниями. Равносильные высказывания. Формулы алгебры высказываний. Существование и единственность КНФ и ДНФ. Связь КНФ и ДНФ Релейно-контактные схемы: анализ и синтез. Конструирование при помощи элемента «и-не» Исчисление высказываний: алфавит, формулы, аксиомы. Теорема о непротиворечивости исчисления высказываний Теорема о полноте исчисления высказываний Предикаты. Логические операции над предикатами. Основные свойства Кванторы. Основные равносильности с кванторами Многочлены Жегалкина. Существование и единственность представления функции алгебры логики многочленом Жегалкина Невыразимые предикаты. Изоморфизмы. Примеры Исчисление предикатов: алфавит, формулы, аксиомы, правила вывода. Связанные и свободные вхождения переменных в предикат. Правила подстановки Общезначимые формулы. Теорема о полноте и непротиворечивости исчисления предикатов Существование главной универсальной функции. Привести пример универсальной вычислимой функции, не являющейся главной. Теорема о неподвижной точке. Программа, печатающая собственный текст. Машина Тьюринга, переписывающая слово задом наперед. Алгоритм умножения в языке с конечным числом переменных. Алгоритм возведения в квадрат в языке с конечным числом переменных. Алгоритм b:=a[i] в языке с конечным числом переменных (массив а кодируется числом по основной теореме арифметики) . Арифметические формулы для всех типов команд в языке с конечным числом переменных. Теорема Тарского о невыразимости арифметики Теорема Гёделя о неполноте арифметики 6.3. Тематика контрольных работ для студентов ЗФО Заочная форма обучения не предусмотрена 7. Учебно-методическое и информационное обеспечение дисциплины а) основная литература ЭБС «Znanium.com» Игошин, В. И. Математическая логика: учебное пособие / В.И. Игошин. - М.: ИНФРА-М, 2012. - 399 с.: - Режим доступа: http://znanium.com/ Лавров, И.А. Математическая логика : учеб. пособие для студентов вузов / И.А. Лавров ; под ред. Л.Л. Максимовой. - М. : Академия, 2006. - 240 с. б) дополнительная литература ЭБС «Znanium.com» Игошин, В. И. Теория алгоритмов: учебное пособие / В.И. Игошин. - М.: ИНФРА-М, 2012. - 318 с.: - Режим доступа: http://znanium.com/ Игошин, В.И. Математическая логика и теория алгоритмов : учеб. пособие для студентов вузов / В.И. Игошин. - М. : Академия, 2008. - 448 с. в) программное обеспечение и Интернет-ресурсы http://www.exponenta.ru – Образовательный математический сайт Exponenta.ru. http://www.matclub.ru – Лекции, примеры решения задач. Электронные учебники. http://www. math.ru – Образовательный математический сайт Math.ru. http://www. mathelp.spb.ru – Лекции по высшей математике: математический анализ; дифференциальные уравнения; аналитическая геометрия, теория вероятностей и др. Калькулятор с функциями. Компьютер с программным обеспечением. 8. Материально-техническое обеспечение дисциплины Материально-техническое обеспечение дисциплины включает: 1) библиотечный фонд ФГБОУ ВПО «МГТУ»; 2) мультимедийное оборудование для чтения лекций-презентаций. Дополнения и изменения в рабочей программе за ________/________ учебный год В рабочую программу ____________________________________________________ (наименование дисциплины) для направления (специальности) ___________________________________________________ (номер направления (специальности) вносятся следующие дополнения и изменения: Дополнения и изменения внес _______________________________________________ (должность, Ф.И.О., подпись) Рабочая программа пересмотрена и одобрена на заседании кафедры _____________________________________________________________________________ (наименование кафедры) «____»___________________20___г. Заведующий кафедрой __________________ _____________ (подпись) (Ф.И.О.)

Похожие:

	Учебно-методический комплекс по дисциплине математическая логика и теория алгоритмов Курс математическая логика и теория алгоритмов обеспечивает приобретение знаний в соответствии с государственным образовательным...		Программа дисциплины «Информатика, математическая логика и теория... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направлений подготовки 231000....
	Рабочая программа по дисциплине В. В математическая логика и теория алгоритмов Рабочая программа составлена на основе фгос впо и учебного плана мгту по направлению 090900. 62 Информационная безопасность		Рабочая программа составлена в соответствии с требованиями фгос впо... Дёгтев А. Н. Теория алгоритмов. Учебно-методический комплекс. Рабочая программа для студентов направления 010100. 62 – математика,...
	Программа вступительных испытаний по дисциплине «Математика» Курс математическая логика и теория алгоритмов обеспечивает приобретение знаний в соответствии с государственным образовательным...		Методические указания к выполнению лабораторных работ 1-3 по дисциплине... Целью работы является теоретическое изучение основных логических функций и эквивалентностей исчисления высказываний и приобретение...
	Рефератов по курсу «Математическая логика и теория алгоритмов» Темпоральные логики высказываний линейного времени и вычислительных деревьев: их синтаксис и семантика		Вопросы к государственному экзамену по информатике Дискретная математика. Теория алгоритмов. Математическая логика. Численные методы. Теоретические основы информатики. Исследование...
	Рабочая программа дисциплины «Математическая логика и теория алгоритмов» Рабочая программа предназначена для преподавания дисциплины вариативной части профессионального цикла студентам очной формы обучения...		Вопросы к экзамену по курсу «Математическая логика и теория алгоритмов» Методические указания предназначены для студентов, обучающихся по направлению 020400. 68 «Биология», магистерская программа 020400....
	Учебно-методический комплекс дисциплины «Математическая логика и теория алгоритмов» Заведующий кафедрой И7 д ф м н., профессор /С. Д. Шапорев/ Составитель д ф м н., профессор /С. Д. Шапорев		Индивидуальное домашнее задание по дисциплине «Дискретная математика»... Курс математическая логика и теория алгоритмов обеспечивает приобретение знаний в соответствии с государственным образовательным...
	Название курса Основной курс "Математическая логика и теория алгоритмов" предназначен для студентов первого курса отделения прикладной инфоматики...		Радиофизический факультет Фгос впо, содействует формированию мировоззрения и системного мышления. Целью преподавания дисциплины «Математическая логика и теория...
	Рабочая программа составлена в соответствии с требованиями фгос впо... Математика, профили подготовки: «Алгебра, теория чисел, математическая логика»; «Вещественный, комплексный и функциональный анализ»;...		Математическая логика и теория алгоритмов Основными видами учебных занятий являются лекции и семинарские занятия. Аудиторные занятия составляют 54 часа в 3 семестре и 72 часа...