Главная страница 1
скачать файл



МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

Томский государственный университет систем управления и радиоэлектроники

УТВЕРЖДАЮ
Первый проректор – проректор по УР

____________________Л.А. Боков

“ ___ “ _____________ 2012 г.
РАБОЧАЯ ПРОГРАММА
по дисциплине «Математическая логика и теория алгоритмов»
для специальности 230105.65 – «Программное обеспечение вычислительной техники

и автоматизированных систем»


Факультет систем управления,

Профилирующая кафедра: Автоматизированных систем управления


Курс - 2

Семестр - 3


Учебный план набора 2008 года и последующих лет

Распределение учебного времени (Всего часов)


Лекции  26 часов

Практические занятия  18 часов

Всего ауд. занятий  44 часа
Самостоятельная работа  56 часов

Общая трудоемкость  100 часов


Экзамен  3 семестр

Томск 2012

Рабочая программа по курсу «Математическая логика и теория алгоритмов» составлена на основании требований Государственного образовательного стандарта по специальности 230105.65 «Программное обеспечение вычислительной техники и автоматизированных систем», утвержденного 27 марта 2000 года.

Рабочая программа обсуждена на заседании кафедры АСУ,

протокол № 15 от « 28 » июня . 2012 г.
Разработчик,

доцент каф. АСУ, к.т.н. Е.Н. Сафьянова


Зав. обеспечивающей кафедрой АСУ,

д.т.н., профессор А.М. Кориков


Рабочая программа согласована с факультетом, профилирующей и выпускающей кафедрой специальности 230105.65
Декан ФСУ, к.т.н., доцент П.В. Сенченко
Зав. профилирующей и выпускающей кафедрой АСУ,

д.т.н., профессор А.М. Кориков




  1. ЦЕЛИ И ЗАДАЧИ ДИСЦИПЛИНЫ И ЕЕ МЕСТО В УЧЕБНОМ ПРОЦЕССЕ

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

Дисциплина «Математическая логика и теория алгоритмов» (МЛ и ТА) читается в 3 семестре и предусматривает чтение лекций, проведение практических занятий, выполнение контрольных работ, получение различного рода консультаций.



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


    1. Задачи изучения дисциплины

МЛ и ТА относится к числу федеральных компонентов цикла общих математических и естественнонаучных дисциплин (ЕН.Ф.1.4). Знания и навыки, полученные при ее изучении, используются в последующих дисциплинах цикла.

Студент, изучивший данную дисциплину, должен:

знать терминологию, основные понятия и определения дисциплины, содержание ее основных разделов;

уметь формулировать и доказывать основные результаты этих разделов.

владеть навыками решения задач по всем указанным разделам, в том числе, и с использованием ЭВМ.

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




  1. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ

    1. Лекции


Тема 1. Алгебра высказываний.

Лекции - 2 часа, самостоятельная работа - 1 час.

Понятие высказывания. Логические операции. Переменные высказывания. Истинностные таблицы. Равносильность. Тавтологии.
Тема 2. Булевы функции.

Лекции – 6 часов, самостоятельная работа - 6 часов.

Определение булевой функции. Булевы функции одной и двух переменных. Некоторые свойства элементарных булевых функций. Представление булевых функций в совершенных дизъюнктивной и конъюнктивной нормальных формах. Полнота системы булевых функций. Классы функций, сохраняющих ноль и единицу. Классы самодвойственных, монотонных и линейных функций. Теорема о полноте. Минимизация дизъюнктивных нормальных форм. Метод Квайна.
Тема 3. Синтез логических схем.

Лекции - 3 часа, самостоятельная работа - 2 часа.

Автоматные описания систем управления. Понятие комбинационной схемы. Автомат с памятью. Основные этапы синтеза комбинационных схем.
Тема 4. Логика предикатов.

Лекции - 4 часа, самостоятельная работа - 2 часа.

Понятие предиката. Операции над предикатами. Определенные и переменные предикаты. Обобщение операций квантирования. Равносильность формул логики предикатов.
Тема 5. Формальные теории.

Лекции - 4 часа, самостоятельная работа - 4 часа.

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

Лекции – 7 часов, самостоятельная работа - 10 часов.

Интуитивное понятие алгоритма и проблема его уточнения. Основные понятия теории рекурсивных функций. Простейшие числовые функции. Основные операторы. Примитивно-рекурсивные функции. Частично-рекурсивные функции. Тезис Черча. Машины Тьюринга. Композиция и итерация машин Тьюринга. Нормальные «алгорифмы» Маркова. Алгоритмически неразрешимые проблемы.
Всего часов лекций 26, самостоятельная работа 25 часов.


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




Наименование темы

Количество

часов


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

работа


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

4

4

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

4

4

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

4

4

  1. Синтез логических схем. Операции над предикатами. Равносильность.

2

4

  1. Рекурсивные функции. Машины Тьюринга.

4

4

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

Всего часов практических занятий  18. Для подготовки к занятиям и выполнения домашних заданий к ним требуется 20 часов самостоятельной работы.


    1. Контрольные работы


Контрольная работа № 1.

Тема работы – математическая логика. В работе требуется выполнить следующие задания.



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

  2. Для указанной функции трех переменных:

  • составить таблицу истинности;

  • определить, к каким классам булевых функций она относится;

  • записать совершенные ДНФ и КНФ;

  • найти минимальную ДНФ;

  • для полученной минимальной ДНФ построить логическую схему в базисах:

а) дизъюнкция, отрицание; б) конъюнкция, отрицание.

  1. Доказать полноту (или неполноту) приведенной системы булевых функций.


Контрольная работа № 2.

Эта контрольная работа включает в себя задания по теории алгоритмов. В работе требуется выполнить три задания.



  1. Приведите три самостоятельных примера применения оператора подстановки к простейшим числовым функциям. Например,

s(С23 (I13 (3, 2, 4), I23 (5, 8, 1), I33( 5, 6, 7))) = 3.

  1. Приведите два самостоятельных примера применения оператора примитивной рекурсии (аналогично примерам из учебного пособия).

  2. Напишите программу для машины Тьюринга в соответствии с Вашим вариантом.

Для подготовки к контрольным работам требуется 4 часа самостоятельной работы.


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




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

Количество

часов


Форма

контроля


  1. Проработка лекционного материала

25

Опрос на занятиях

(устно)


  1. Подготовка к практическим занятиям

20

Отчеты

  1. Самостоятельное изучение тем теоретической части

7

Дом. задание, тест

  1. Подготовка к контрольным работам

4

Оценка

Всего часов на самостоятельную работу

56 часов

Темы для самостоятельного изучения (Всего 7 часов)

1. Классы функций, сохраняющих ноль и единицу. Класс самодвойственных функций.

2. Основные этапы синтеза комбинационных схем.

3. Основные понятия теории рекурсивных функций.


  1. УЧЕБНО-МЕТОДИЧЕСКИЕ МАТЕРИАЛЫ ПО ДИСЦИПЛИНЕ

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




  1. Шевелев Ю.П. Математическая логика и теория алгоритмов: учебное пособие / Ю.П. Шевелев. - Томск: Дельтаплан, 2007. - 219 с. (50 экз.)

  2. Клини С.К. Математическая логика: Пер. англ. / С.К. Клини; пер.: Ю.А. Гастев; ред. пер.: Г. Е. Минц . - 3-е изд., стереотип. - М.: КомКнига, 2007; М.: УРСС, 2007. – 480 с. (20 экз.)




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




  1. Зюзьков В.М. Математическая логика и теория алгоритмов: Учебное пособие для вузов / В.М. Зюзьков, А.А. Шелупанов. - 2-е изд. - М: Горячая линия-Телеком, 2007. - 176 с (101 экз.)

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

  3. Шапорев, С.Д. Математическая логика. Курс лекций и практических занятий: Учебное пособие для вузов / С.Д. Шапорев. – СПб: БХВ-Петербург, 2005. - 410 с. (59 экз.)




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




  1. Сафьянова Е.Н. Математическая логика и теория алгоритмов: методические указания по проведению практических занятий, а также и самостоятельной и индивидуальной работе студентов всех форм обучения для направления 010500.62 - Прикладная математика и информатика / Е.Н. Сафьянова. – Томск: ТУСУР, 2012. – 6 с. [Электронный ресурс]. – Режим доступа: http://asu.tusur.ru/learning/spec230105/d17/




  1. ПРИМЕНЕНИЕ РЕЙТИНГОВОЙ СИСТЕМЫ


Контроль обучения – экзамен.

Максимальный рейтинг – 100 баллов.

По дисциплине «Математическая логика и теория алгоритмов» проведение экзамена является обязательным. При этом балльная оценка в соотношении 70/30 распределяется на две составляющие: семестровую и экзаменационную. Т.е. 70 баллов можно получить за текущую работу в семестре, а 30 баллов – за ответы на экзамене.

Для стимулирования планомерности работы студента в семестре в раскладку баллов по элементам контроля введен компонент своевременности, который применяется только для студентов, без опозданий отчитывающихся по предусмотренным элементам контроля (тесты, практические работы).

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

Текущий контроль изучения дисциплины состоит из следующих видов:



  • контроль за усвоением теоретического материала – проведение трех тестов;

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

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

В таблице 4.1 содержится распределение баллов в течение семестра для дисциплины «Математическая логика и теория алгоритмов», завершающейся экзаменом и содержащей 14 лекций (27 час.) и 9 практических занятий (18 час.).

Таблица 4.1 – Дисциплина «Математическая логика и теория алгоритмов» (экзамен, лекции, практические занятия)



Элементы учебной деятельности

Максимальный балл на 1-ую контрольную точку с начала семестра

Максимальный балл за период между 1КТ и 2КТ

Максимальный балл за период между 2КТ и на конец семестра

Всего за

семестр


Посещение занятий

2

2

2

6

Тестовый контроль

2

2

2

6

Выполнение и защита результатов решения

практических задач



4

8

4

16

Выполнение и защита индивидуальных самостоятельных работ

8

8

6

22

Контрольные работы

4




4

8

Компонент своевременности

4

4

4

12

Экзамен







30

30

Итого максимум за период

24

24

52

100

Нарастающим итогом

24

48

100



По результатам текущего контроля формируется допуск студента к итоговому контролю – экзамену по дисциплине. Экзамен осуществляется в форме опроса по теоретической части дисциплины.

В составе суммы баллов, полученной студентом по дисциплине, заканчивающейся экзаменом, экзаменационная составляющая должна быть не менее 10 баллов. В противном случае экзамен считается не сданным, студент в установленном в ТУСУРе порядке обязан его пересдать.

Методика выставления баллов за ответы на экзамене определяется из расчета по 12 баллов за 1 и 2 вопросы и 6 баллов за 3 вопрос.

Неудовлетворительной сдачей экзамена считается экзаменационная составляющая менее 10 баллов. При неудовлетворительной сдаче экзамена (<10 баллов) или неявке на экзамен экзаменационная составляющая приравнивается к нулю (0).
Таблица 4.2 – Пересчет баллов в оценки за контрольные точки

Баллы на дату контрольной точки

Оценка

Не менее 90% от максимальной суммы на дату КТ

5

От 70% до 89% от максимальной суммы на дату КТ

4

От 60% до 69% от максимальной суммы на дату КТ

3

Менее 60% от максимальной суммы на дату КТ

2

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


Таблица 4.3 – Пересчет итоговой суммы баллов в традиционную и международную оценку

Оценка (ГОС)

Итоговая сумма

баллов, учитывает

успешно сданный экзамен

Оценка (ECTS)

5 (отлично)

90 – 100

А (отлично)

4 (хорошо)

85 – 89

В (очень хорошо)

75 – 84

С (хорошо)

70 – 74

D (удовлетворительно)

3 (удовлетворительно)

65 – 69

60 – 64

E (посредственно)

2 (неудовлетворительно)

Ниже 60 баллов

F (неудовлетворительно)


скачать файл



Смотрите также:
Рабочая программа по дисциплине «Математическая логика и теория алгоритмов» для специальности 230105. 65 «Программное обеспечение вычислительной техники и автоматизированных систем»
160.45kb.
Реферат по отечественной истории
143.96kb.
Программа вступительного экзамена в аспирантуру по специальности 05. 13
143.75kb.
Рабочая программа дисциплины Теория вероятностей и математическая статистика
109.69kb.
1 Алгоритмы и их сложность Представление алгоритмов в машинных командах, на равнодоступной адресной машине (рам) и языке высокого уровня. Временная и емкостная сложность алгоритмов для разных представлений
231.89kb.
Рабочая программа дисциплины теория алгоритмов направление подготовки 230700 прикладная информатика профиль подготовки
215.84kb.
Методы и средства обеспечения надежности автоматизированных информационных систем
100.54kb.
Учебная программа Дисциплины р6 «Аппаратные средства вычислительной техники»
165.89kb.
Программа курса для студентов специальности 1 40 01 01- программное обеспечение информационных технологий
69.01kb.
Программа дисциплины Теория алгоритмов и эволюционные вычисления для направления 080500. 62 Бизнес-информатика подготовки бакалавра
321.66kb.
Рабочая программа по дисциплине «Методика преподавания изобразительного искусства» Для специальности 070901 «дпи и народные промыслы»
339.07kb.
Рабочая программа по дисциплине «Технологии программирования» для специальности 230101 «Вычислительные машины, комплексы, системы и сети»
201.87kb.