Рабочая программа для студентов очной формы обучения направление 050100. 62 «Педагогическое образование»

Скачать 295.31 Kb.

Название	Рабочая программа для студентов очной формы обучения направление 050100. 62 «Педагогическое образование»
страница	3/3
Дата публикации	03.12.2014
Размер	295.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. Логика предикатов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тест по теме: «Основы математической логики»:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Ершов Ю.Л., Палютин Е.А. Математическая логика, СПб.: Лань, 2005 г. -336 с.

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

4. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов- 3-е издание- М.Академия,2007.-304 с.

5. Игошин В.И. Математическая логика и теории алгоритмов- 2-е издание- М.Академия,2008.- 448 с.
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.

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

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

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

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

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

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

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

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.

1 2 3

	Рабочая программа для студентов очной формы обучения направление... Иванов Д. И. Дополнительные главы лгебры. Учебно-методический комплекс. Учебно-методический комплекс. Рабочая программа для студентов...		Учебно-методический комплекс рабочая программа для студентов очной... Шармин Д. В. Информационные технологии в профессиональной деятельности. Учебно-методический комплекс. Рабочая программа для студентов...
	Рабочая программа для студентов направления подготовки 050100 (44.... Содержание: умк по дисциплине Экология растений для студентов направления подготовки 050100 (44. 03. 05) Педагогическое образование...		Учебно-методический комплекс рабочая программа для студентов направления... Содержание: умк по дисциплине Материаловедение и технология конструкционных материалов для студентов направления подготовки 050100....
	Рабочая программа для студентов 4 курса очной и заочной формы 050100.... Наталья Валерьевна. Печатная графика: Учебно-методический комплекс. Рабочая программа для студентов 4 курса очной и заочной формы...		Учебно-методический комплекс рабочая программа для студентов направления... Содержание: умк по дисциплине Основы исследований в математическом образовании для студентов направления подготовки 050100 (44. 03....
	Учебно-методический комплекс рабочая программа для студентов очной... Д. В. Информационные технологии в профессиональной деятельности. Учебно-методический комплекс. Рабочая программа для студентов очной...		Учебно-методический комплекс рабочая программа для студентов направления... Содержание: умк по дисциплине Современные методы обработки конструкционных материаловдля студентов направления подготовки 44. 03....
	Учебно-методический комплекс рабочая программа для студентов направления... Смирнова И. Р., Драчева С. О. Детская литература. Учебно-методический комплекс. Рабочая программа для студентов направления 050100....		Учебно-методический комплекс рабочая программа для студентов направления... Селиванова О. А. Молодежное движение и развитие социальной активности. Учебно-методический комплекс. Рабочая программа для студентов...
	Рабочая программа для студентов направления подготовки 050100 (44. 03. 01) Содержание: умк по дисциплине Популяционная экология для студентов направления подготовки 050100 (44. 03. 01) Педагогическое образование...		Рабочая программа для студентов направления подготовки 050100 (44. 03. 05) Содержание: умк по дисциплине Основы экологической безопасности для студентов направления подготовки 050100 (44. 03. 05) Педагогическое...
	Рабочая программа для студентов направления подготовки 44. 03. 01-... Рабочая программа предназначена для преподавания дисциплины вариативной части профессионального цикла студентам очной формы обучения...		Учебно-методический комплекс рабочая программа для студентов направления... Содержание: умк по дисциплине б 2 Педагогика школы для студентов направления подготовки 050100. 62 Педагогическое образование профиля...
	Рабочая программа для студентов направления подготовки 050100 (44.... Содержание: умк по дисциплине Возрастная анатомия, физиология и гигиена для студентов направления подготовки 050100 (44. 03. 01)...		Учебно-методический комплекс рабочая программа для студентов направления... Содержание: умк по дисциплине Философия для студентов направления подготовки 050100. 62 (44. 03. 01) Педагогическое образование профиля...

Рабочая программа для студентов очной формы обучения направление 050100. 62 «Педагогическое образование»

Похожие: