Рабочая программа для студентов очной формы обучения, направление 230400. 62 «Информационные системы и технологии»

Скачать 249.31 Kb.

Название	Рабочая программа для студентов очной формы обучения, направление 230400. 62 «Информационные системы и технологии»
страница	3/3
Дата публикации	28.10.2014
Размер	249.31 Kb.
Тип	Рабочая программа

100-bal.ru > Математика > Рабочая программа

1 2 3

Разделы дисциплины и междисциплинарные связи с обеспечиваемыми (последующими) дисциплинами.

№ п/п	Наименование обеспечиваемых (последующих) дисциплин	Темы дисциплины необходимые для изучения обеспечиваемых (последующих) дисциплин
№ п/п	Наименование обеспечиваемых (последующих) дисциплин	1.1	1.2	2.1	2.2	2.3	3.1	3.2
1.	Теория автоматов	+	+		+	+	+	+
2.	Теория информации	+	+	+		+	+	+
3.	Теория информационных процессов и систем	+				+	+	+
4.	Технологии обработки информации	+	+	+		+	+	+
5.	Интеллектуальные информационные системы и технологии	+	+	+			+	+

Содержание дисциплины.

Модуль 1.

Тема 1.1. Булевы функции и логика высказываний.

Функции алгебры логики. Существенные и несущественные переменные. Формулы. Представление функций формулами. Операция суперпозиции. Операция введения несущественной переменной. Замыкание множества функций. Замкнутые классы. Равенство функций. Эквивалентность формул. Элементарные функции и их свойства. Совершенная дизъюнктивная нормальная форма. Совершенная конъюнктивная нормальная форма. Полные системы функций. Достаточное условие полноты. Примеры полных систем. Полиномы Жегалкина. Представление булевых функций полиномами. Линейные функции и их свойства. Функции, сохраняющие константы. Самодвойственные функции и их свойства. Монотонные функции и их свойства. Теорема Поста о полноте системы булевых функций. Возможность выделить из каждой полной системы полную подсистему, состоящую не более чем из 4-х функций. Базисы замкнутых классов. Примеры базисов в P₂. Предполные классы. Свойства предполных классов в P₂. Теорема Поста о конечной порожденности замкнутых классов булевых функций.

Тема 1.2. Исчисление высказываний.

Высказывания и операции над ними. Аксиомы классического исчисления высказываний. Схемы аксиом. Правила вывода. Вывод. Выводимые формулы. Вывод из системы гипотез. Простые свойства выводимости. Примеры вывода. Вывод формулы A → A. Теорема о дедукции. Тождественная истинность выводимых формул. Непротиворечивость классического исчисления высказываний. Теорема о полноте. Независимость схем аксиом исчисления высказываний. Теорема о независимости схем аксиом исчисления высказываний.
Модуль 2.

Тема 2.1. Логика предикатов.

Понятие предиката. Примеры. Логические операции над предикатами; кванторы. Теоретико-множественный смысл операций над предикатами. Условия полноты системы предикатов на конечном множестве. Формулы; свободные и связанные переменные. Модель, сигнатура модели. Значение формулы в модели. Формула, истинная в модели. Формула, истинная на множестве. Тождественно истинная формула. Правила эквивалентных преобразований формул логики предикатов. Нормальная форма. Приведение формул к нормальной форме.

7

Тема 2.2. Фильтры, теорема компактности.

Фильтры, максимальные фильтры. Теорема о вложении фильтров. Теорема об ультрафильтрах. Фильтрованные произведения, ультрапроизведения. Теорема об ультрапроизведениях. Теорема компактности. Предложение о бесконечных моделях. Нестандартные арифметики. Теорема о нестандартных арифметиках.

Тема 2.3. Исчисление предикатов.

Аксиомы классического исчисления предикатов. Правила вывода. Выводимые формулы. Примеры вывода. Специальный вывод из системы гипотез, теорема о дедукции. Тождественная истинность выводимых формул. Непротиворечивость классического исчисления предикатов. Теорема Гёделя о полноте.
Модуль 3.

Тема 3.1. Частично рекурсивные функции.

Частичные числовые функции. Простейшие функции. Операции суперпозиции и примитивной рекурсии. Примитивно рекурсивные функции. Операция минимизации. Частично рекурсивные функции, общерекурсивные функции. Тезис Чёрча. Теорема о совпадении класса частично рекурсивных функций и класса частичных числовых функций, вычислимых по Тьюрингу. Рекурсивные множества, разрешимые предикаты, рекурсивно перечислимые множества, частично разрешимые предикаты. Теорема Райса. Нормальные алгорифмы Маркова. Принцип нормализации.

Тема 3.2. Машина Тьюринга.

Машина Тьюринга и универсальные функции. Машина Поста. Сводимости и степени. Сводимость по Тьюрингу, степени неразрешимости.

Планы семинарских занятий.

Тема 1.1. Булевы функции и логика высказываний. Основные бинарные отношения: эквивалентность и частичный порядок. Принципы трансфинитной индукции, максимума и теорема об эквивалентностях. Задание булевых функций, контактно-релейные схемы. Предложения о КНФ и ДНФ. Теорема об описании предполных классов Поста..

Тема 1.2. Исчисление высказываний. Формулировка ИВ: алфавит, формулы, секвенции доказуемые и правила вывода, доказательство секвенций. Вспомогательные леммы и теоремы о полноте ИВ а узком и широком смыслах.

Тема 2.1. Логика предикатов. Язык логики предикатов. Истинность формул в системах данной сигнатуры. Эквивалентные и конгруэнтные и формулы. Основные эквивалентности. Приведение формул к предваренному виду.

Тема 2.2. Фильтры и фильтрованные произведения. Фильтры и ультрафильтры. Теорема о вложении фильтров в ультрафильтры и описание ультрафильтров. Понятие фильтрованного произведения систем. Теоремы об ультрапроизведениях и компактности. Предложения о нестандартных арифметиках и бесконечных моделях.

Тема 2.3. Исчисление предикатов. Формулировка исчисления, предварительные результаты. Две леммы и теорема о существовании модели непротиворечивого множества формул. Теоремы о полноте ИП и независимости аксиом.

Тема 3.1. Вычислимые функции. Тезис Чёрча. Частично рекурсивные функции. Общерекурсивные функции. Рекурсивно перечислимые множества и их классы.

Тема 3.2. Машина Тьюринга. Машина Поста. Сводимости.
8

Темы лабораторных работ (Лабораторный практикум).

Не планируются.

Примерная тематика курсовых.

Не планируются.

Учебно - методическое обеспечение самостоятельной работы студентов. Оценочные средства для текущего контроля успеваемости, промежуточной аттестации по итогам освоения дисциплины (модуля).

a) Текущая аттестация:

контрольные работы; В каждом семестре проводятся контрольные работы (на семинарах).
тестирование (письменное или компьютерное) по разделам дисциплины;

b) Промежуточная аттестация:

тестирование по дисциплине;
зачёт (письменно-устная форма). Зачёт выставляется после решения всех задач контрольных работ и выполнения самостоятельной работы.

Текущий и промежуточный контроль освоения и усвоения материала дисциплины ˅осуществляется в рамках рейтинговой (100-бальной) системы оценок.
Тест по теме: «Основы математической логики»:

1. Наука, изучающая законы и формы мышления, называется:
а) алгебра;
б) геометрия;
в) философия;
г) логика.

2. Повествовательное предложение, в котором что-то утверждается или отрицается называется:
а) выражение;
б) высказывание;
в) вопрос;
г) Умозаключение.

3. Константа, которая обозначается «1» в алгебре логики называется:
а) ложь;
б) правда;
в) истина;
г) неправда.

4. Какое из следующих высказываний являются истинными?
а) город Париж — столица Англии;
б) 3+5=2+4;
в) II + VI = VIII;
г) томатный сок вреден.

9

5. Объединение двух высказываний в одно с помощью союза «и» называется:
а) инверсия;
б) конъюнкция;
в) дизъюнкция;
г) импликация.

6. Чему равно значение логического выражения (1v1)&(1v0)?
а)1;
б) 0;
в) 10;
г) 2.

7. Двойное отрицание логической переменной равно:
а) 0;
б) 1;
в) исходной переменной;
г) обратной переменной.
Варианты контрольных работ:
Контрольная работа №1.

1. Составьте таблицу истинности булевой функции, реализованную данной формулой. Составьте по таблице истинности СДНФ и СКНФ:

2. Проверьте, будут ли эквивалентны формулы, применяя следующие способы:

a) составлением таблиц истинности;

b) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.

3. С помощью эквивалентных преобразований приведите формулу к ДНФ, КНФ, СДНФ, СКНФ. Постройте полином Жегалкина.

4. Найдите сокращенную, все тупиковые и минимальные ДНФ булевой функции, следующими способами:

a) методом Квайна;

b) с помощью карт Карно.

f(0, 1, 0)= f(1, 0, 0)= f(1, 0, 1)=0.

Выяснить, каким классам Поста принадлежит данная функция.

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

Доказать секвенции:

˥ (X→Y) ├ X,
X, Y ├ ˥ (X→˥ Y),
˥ X→Y├˥ Y→X,.

X→Z, Y→Z ├ (˥ X→Y)→Z,
X→Y, X→˥ Y├ X→Z.

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

1. Предикатный символ D(x,y) интерпретируется на множестве натуральных чисел N как «x делитель y», + интерпретируется стандартно. Записать формулами языка I-го порядка в сигнатуре {+, D} условия «x=0» и «x=2».

2. Привести к предваренному виду формулу

(x)((z)(z
Будет ли эта формула истинной на множестве натуральных чисел, когда < интерпретируется стандартно, а P(x) означает произвольное свойство натуральных чисел?

3. Проверить, что ПВ4 сохраняет тождественную истинность секвенций.

4. Показать, что (x)A(x)v(x)B(x)≡(x)(A(x)v(x)B(x)) не является тождеством.
Контрольная работа №4.

1. Построить стандартную машину Тьюринга, вычисляющую функцию x+y.

2. Пусть A={a₀, a₁,…,a_n} внешний алфавит машины Тьюринга. Построить машину Тьюринга, которая меняет слово, записанное на ленте, на слово, состоящее из букв исходного, но записанных в обратном порядке.

Темы рефератов:

Нейронные сети.
Вероятностные вычисления.
Квантовые вычисления.
Биомолекулярные вычисления.
Вычисления над кольцом целых чисел.
Вычисления над кольцом действительных чисел.
Вычисления над кольцом комплексных чисел.
Структурная сложность.
Коммуникационная сложность.
Дескриптивная сложность.
Алгебраическая сложность.

Вопросы к зачёту:

1. Булевы функции, КНФ и ДНФ, контактно-релейные схемы.
2. Теорема Поста о предполных классах.
3. Аксиоматика ИВ, вспомогательные леммы и теорема о полноте ИВ.
4. Формулы ЛП, их истинность в системах данной сигнатуры.
5. Предложения о конгруэнтных формулах и предваренной форме.
6. Основные эквивалентности.
7. Фильтры и ультрафильтры, две теоремы о них.
8. Теорема об ультрапроизведениях и компактности.

11

9. Предложения о нестандартной модели арифметики и бесконечных моделях.
10. ИП. Теорема о существовании модели.
11. Теоремы о полноте ИП и независимости аксиом.
12. ЧРФ и машины Тьюринга.
13. Рекурсивно перечислимые множества. Теорема Поста. Построение простого множества.
14. Неразрешимые проблемы. Элементарная теория арифметики. Тождественно истинные формулы ИП.

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

аудиторные занятия:

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

активные и интерактивные формы (семинары в диалоговом режиме по темам 1.1, 2.1, 3.1, 3.2, компьютерное моделирование и практический анализ результатов, научные дискуссии по темам 2.2, 2.3, работа студенческих исследовательских групп, вузовские и межвузовские видеоконференции)

внеаудиторные занятия:

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

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

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

1. Дегтев А.Н. Алгебра и логика: Учебное пособие. Тюмень: Издательство Тюменского государственного университета, . 2000. - 88 с.

2. Ершов Ю.Л., Палютин Е.А. Математическая логика, М.: “Наука”, 1979 г.

3. Мендельсон Э. Введение в математическую логику. М.: Наука, 1984.

4. Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики. М.: Физматлит, 2002.

5. Колмогоров А. Н., Драгалин А. Г. Математическая логика. М.: УРСС, 2004.

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

7. Клини С. К. Математическая логика. М.: Мир, 1973.

8. Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 2. Языки и исчисления. М.: МЦНМ, 2000

12

9. Верещагин Н. К., Шень А. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. М.: МЦНМ, 1999.

10. Крупский В. Н., Плиско В. Е. Теория алгоритмов. М.: Издательский центр «Академия», 2009.
11.2. Дополнительная литература:

1. Александров П. С. Введение в теорию множеств и общую топологию. М.: Наука, 1977.

2. Архангельский А. В. Канторовская теория множеств. М.: Изд-во МГУ, 1988.

3. Булос Дж., Джеффри Р. Вычислимость и логика. М.: Мир, 1994.

4. Гиндикин С. Г. Алгебра логики в задачах. М.: Наука, 1972.

5. Гладкий А. В. Математическая логика. М.: РГГУ, 1998.

6. Ершов Ю. Л., Палютин Е. А. Математическая логика. 2-е изд., испр. и доп. М.: Наука. Гл. ред. физ.-мат. лит., 1987.

7. Логический подход к искусственному интеллекту: От модальной логики к логике баз данных / Тейз А., Грибомон П., Юлен Г. и др. М.: Мир, 1998.

8. Столл Р. Множества, логика, аксиоматические теории. М.: Просвещение, 1968.

9. Фейс Р. Модальная логика. М.: Наука, 1974.

10. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983.

11.Чёрч А. Введение в математическую логику. М.: ИЛ, 1960.

12. Шёнфилд Дж. Математическая логика. М.: Наука, 1975.

11.3. Программное обеспечение и Интернет – ресурсы:

1. Крупский В. Н. Лекции по теории алгоритмов для первого курса мехмата (2004). http://lpcs.math.msu.su/~krupski/download/mm1/lect_kru.pdf, http://lpcs.math.msu.su/~krupski/download/mm1/lect_kru.ps

2. Крупский В. Н. Подборка задач по теории алгоритмов. http://lpcs.math.msu.su/~krupski/download/mm1/zad_alg.pdf, http://lpcs.math.msu.su/~krupski/download/mm1/zad_alg.ps

3. Плиско В. Е. Математическая логика: Курс лекций. http://lpcs.math.msu.su/~plisko/matlog.pdf, http://lpcs.math.msu.su/~plisko/matlog.ps

4. Плиско В. Е. Теория алгоритмов: Курс лекций. http://lpcs.math.msu.su/~plisko/ta.pdf, http://lpcs.math.msu.su/~plisko/ta.ps

5. Bilaniuk S. A Problem Course in Mathematical Logic. (2003) http://www.trentu.ca/mathematics/sb/pcml/

Технические средства и материально-техническое обеспечение дисциплины (модуля).

Учебные аудитории для проведения лекционных и практических занятий, в том числе, оснащённые мультимедийным оборудованием, доступ студентов к компьютеру с Microsoft Office.

13

1 2 3

	Министерство образования и науки государственное образовательное учреждение Тонов м. Л. Алгебра и геометрия. Учебно-методический комплекс. Рабочая программа для студентов очной формы обучения по направлению...		Методические указания для студентов-магистрантов дневной формы обучения... Методическая разработка предназначена для студентов- магистрантов направлений 230400. 68 «Информационные системы и технологии» и230100....
	Пояснительная записка: Цели и задачи дисциплины. Дисциплина «Языки программирования» Ступников А. А. Языки программирования. Учебно-методический комплекс. Рабочая программа для студентов очной формы обучения, направления...		Учебно-методический комплекс рабочая программа для студентов очной... Учебно-методический комплекс. Рабочая программа для студентов очной формы обучения направления 230400. 62
	Методическое пособие по выполнению, оформлению и защите курсовых... Методическое пособие предназначено для бакалавриата Кубанского государственного аграрного университета по специальности 230400. 62...		Рабочая программа по направлению 230400 «Информационные системы и технологии» Рабочая программа составлена доцентом А. В. Жаровым на основании Федерального государственного образовательного стандарта высшего...
	Учебно-методический комплекс рабочая программа для студентов направления Учебно-методический комплекс. Рабочая программа для студентов направления 230401. 62 информационные системы и технологии, очной формы...		Учебно-методический комплекс рабочая программа для студентов очной... Шармин Д. В. Информационные технологии в профессиональной деятельности. Учебно-методический комплекс. Рабочая программа для студентов...
	Рабочая программа учебной дисциплины «Информационные технологии в экономике» Рабочая программа предназначена для преподавания дисциплины «Информационные технологии в экономике» вариативной части естественнонаучного...		Учебно-методический комплекс рабочая программа для студентов очной... Рассмотрено на заседании умк институту математики, естественных наук и информационных технологий, протокол №1 от 21. 04. 2001 г
	Рабочая программа для студентов очной формы обучения направление... Иванов Д. И. Математическая логика и теория алгоритмов. Учебно-методический комплекс. Рабочая программа для студентов очной формы...		Рабочая программа для студентов очной формы обучения, направление 030100. 62 «Философия» Дёгтев А. Н. Математическая логика. Учебно-методический комплекс. Рабочая программа для студентов очной формы обучения, направления...
	Рабочая программа для студентов очной формы обучения, направление... И. Математическая логика. Учебно-методический комплекс. Рабочая программа для студентов очной формы обучения, направления 010500....		Рабочая программа для студентов 230400. 62 направления «Информационные системы и технологии» ...
	Рабочая программа для студентов 230400. 62 направления «Информационные системы и технологии» ...		Рабочая программа для студентов очной формы обучения. Направление... Рабочая программа дисциплины «Алгебра» для студентов очной формы обучения по направлению подготовки 010500. 62 «Математическое обеспечение...

Рабочая программа для студентов очной формы обучения, направление 230400. 62 «Информационные системы и технологии»

Похожие: