Законов, закономерностей математики и отвечающих им методов расчета. Формирование базовой

Скачать 165.02 Kb.

Название	Законов, закономерностей математики и отвечающих им методов расчета. Формирование базовой
Дата публикации	05.07.2015
Размер	165.02 Kb.
Тип	Закон

100-bal.ru > Математика > Закон

$c:\users\15\desktop\скан\15.tif$

1.Рабочая учебная программа дисциплины

Организационно-методический раздел

2.Цель дисциплины:

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

3.Задачи дисциплины:

Основными задачами изучения дисциплины являются:

- ознакомление студентов с логикой высказываний, логикой предикатов и исчислениями

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

3.2. Формы текущего и промежуточного контроля

Очная форма обучения

Вид занятий (учебной работы)	3 сем	_сем	ИТОГО:
Лекции	32		32
Лабораторные
Практические	16		16
КСР
Семинары

*Итого аудиторных занятий:*	48		48
РГЗ
Реферат
Курсовой проект (работа)

Другие виды самостоят. работы	52		52
*Итого самостоятельных занятий:*	52		52
ИТОГО:	100		100
Вид итогового контроля - зачет

Заочная форма обучения

Вид занятий (учебной работы)	3 сем	_ сем	ИТОГО:
Лекции	12		12
Лабораторные
Практические	2		2
КСР
Семинары

*Итого аудиторных занятий:*	14		14
РГЗ
Реферат
Курсовой проект (работа)

Другие виды самостоят. работы
*Итого самостоятельных занятий:*	86		86
ИТОГО:	100		100
Вид итогового контроля - зачет

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

Очная форма обучения (3 семестр)

№ п/п	Раздел дисциплины	Лекции	Лаборат.	Практич.	КСР	Семинары	Итого аудиторных	РГЗ	Реферат	Курсовой проект (работа)	Другие виды сам.работы	Итого сам.работы	ИТОГО
	Введение	2					2					2	4
	Исчисление высказываний	4		1			5					9	14
	Исчисление предикатов (первого порядка)	4		2			6					8	14
	Аксиоматические системы	5		4			9					7	16
	Понятие алгоритма	5		4			9					3	12
	Рекурсивные функции	4		2			6					8	14
	Нормальные алгорифмы Маркова	4		1			5					7	12
	Машина Тьюринга	4		2			6					8	14
*Итого*		32		16			48					52	100
*Форма контроля – зачет*

4.

5.

Заочная форма обучения (3 семестр)

№ п/п	Раздел дисциплины	Лекции	Лаборат.	Практич.	КСР	Семинары	Итого аудиторных	РГЗ	Реферат	Курсовой проект (работа)	Другие виды сам.работы	Итого сам.работы	ИТОГО
	Введение	1					1					5	6
	Исчисление высказываний	1		1			2					12	14
	Исчисление предикатов (первого порядка)	2					2					11	13
	Аксиоматические системы	1					1					12	13
	Понятие алгоритма	2					2					11	13
	Рекурсивные функции	2					2					12	14
	Нормальные алгоритмы Маркова	1		1			2					11	13
	Машина Тьюринга	2					2					12	14
*Итого*		12		2			14					86	100
*Форма контроля – зачет*

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

3.4.1. Основные вопросы разделов и тем модулей

7.Раздел 1. Введение

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

Формулы исчисления высказываний и их интерпретация. Понятие высказывания. Синтаксис исчисления высказываний (ИВ). Интерпретация формул и ИВ. Общезначимые, выполнимые и невыполнимые формулы. Тривиальный алгоритм проверки выполнимости формул. Алгоритм Куайна. Алгебраический подход к ИВ. Алгебра логики и эквивалентные преобразования. Некоторые приложения алгебры логики. Нормальные формы. Дизъюнктивные и конъюнктивные нормальные формы в ИВ (ДНФ и КНФ). Методы построения ДНФ и КНФ, эквивалентных произвольным формулам ИВ (с помощью таблиц истинности и эквивалентных преобразований). Алгоритм Девиса-Патнема для проверки выполнимости нормальных форм. Метод резолюций и ИВ. Проблем а дедукции и ее значение в математической логике и информатике. Прямая и обратная дедукция. Теорема Робинсона и правило резолюций. Метод резолюций для решения проблемы дедукции. Дизъюнкты Хорна. Метод резолюций для дизъюнктов Хорна. Оценка трудоемкости метода.

8.Раздел 2. Исчисление предикатов (первого порядка)

Понятие предиката. Ограниченность ИВ. Примеры рассуждений, не формализуемых в рамках ИВ. Понятие предиката и примеры его использования в рассуждениях. Синтаксис и семантика формул исчисления предикатов. Синтаксис исчисления предикатов (ИП). Кванторы и типы вхождения переменных в формулы. Интерпретация формул в ИП. Примеры интерпретаций. Общезначимые, выполнимые и невыполнимые формулы. Схемы общезначимых формул, используемых для эквивалентных преобразований. Клаузальные формы. Подстановка и конкретизация в ИП. Универсальное и экзистенциальное замыкания. Предваренные и нормальные формы. Сколемовские и клаузальные формы. Алгоритм преобразования произвольной формулы ИП в клаузальную форму. Метод резолюций в ИП. Проблема дедукции в ИП. Фундаментальная резолюция. Унификация с помощью подстановки. Алгоритм унификации. Метод резолюций для ИП. Дизъюнкты Хорна и решение проблемы дедукции методом резолюций в ИП. При меры применения метода резолюций для решения проблемы дедукции. Связь ИП с системами представления знаний в задачах искусственного интеллекта.
Раздел 4. Аксиоматические системы

Определение аксиоматических систем (АС). Области применения АС. АС с правилом вывода MODUS PONENS. Полнота и минимальность АС. Примеры доказательств теорем. АС натурального вывода. Примеры доказательств теорем. Теорема Геделя о неполноте.
Раздел 5. Понятие алгоритма

Определения алгоритма, свойства.
Раздел 6. Рекурсивные функции

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

Определение нормального алгоритма Маркова. Функция вычислимая по Маркову. Операции над алгоритмами Маркова (композиция, соединение и др.). Теорема о взаимосвязи рекурсивной функции и функции и вычислимой по Маркову.
Раздел 8. Машина Тьюринга

Устройство машины Тьюринга (внешний алфавит, внутренний алфавит, бесконечная в обе стороны лента, управляющая головка). Работа машины Тьюринга. Реализация на машине Тьюринга алгоритмов вычисления различных функций. Теорема о взаимосвязи вычислимой по Тьюрингу функции с функцией частично вычислимой по Маркову и частично рекурсивной функцией.

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

Контрольные задания по математической логике и теории алгоритмов
Номер варианта определяется по последней цифре зачетной книжки:

Вариант №1 - последняя цифра 0, 4,8

Вариант №2 - последняя цифра 1,5,9

Вариант №3 - последняя цифра 2,6

Вариант №4 - последняя цифра 3,7

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

а) Построить таблицу истинности, привести функцию к СДНФ, СКНФ

б) Минимизировать полученную СДНФ с помощью карт Карно

в) Найти многочлен Жегалкина. Выяснить, является ли данная булева функция линейной?

(z→x)↔(y│x)

2. Пусть S(x,y,z) и П(x,y,z) – соответственно предикаты сложения (z является суммой x и y) и умножения (z является произведением x и y), рассматриваемые на множестве Z – всех целых чисел и на множестве N₀=NU{0} целых неотрицательных чисел. Какой смысл имеют следующие формулы и на каком множестве Z или N₀ они истинны?

а) (Ǝy)(x)S(x,y,z)

b) (⩝y)(⩝x)П(x,y,-x)
Вариант 2
1. Для заданной булевой функции трех переменных

а) Построить таблицу истинности, привести функцию к СДНФ, СКНФ

б) Минимизировать полученную СДНФ с помощью карт Карно

в) Найти многочлен Жегалкина. Выяснить, является ли данная булева функция линейной

((x↓y)→z)y

2. Пусть S(x,y,z) и П(x,y,z) – соответственно предикаты сложения (z является суммой x и y) и умножения (z является произведением x и y), рассматриваемые на множестве Z – всех целых чисел и на множестве N₀=NU{0} целых неотрицательных чисел. Какой смысл имеют следующие формулы и на каком множестве Z или N₀ они истинны?

а) (⩝y)(x)S(x,y,0)

b) (∃y)(⩝x)П(x,y,x)
Вариант 3
1. Для заданной булевой функции трех переменных

а) Построить таблицу истинности, привести функцию к СДНФ, СКНФ

б) Минимизировать полученную СДНФ с помощью карт Карно

в) Найти многочлен Жегалкина. Выяснить, является ли данная булева функция линейной?

(

→x)↔(

|y)

2. Пусть S(x,y,z) и П(x,y,z) – соответственно предикаты сложения (z является суммой x и y) и умножения (z является произведением x и y), рассматриваемые на множестве Z – всех целых чисел и на множестве N₀=NU{0} целых неотрицательных чисел. Какой смысл имеют следующие формулы и на каком множестве Z или N₀ они истинны?

а) (Ǝx)(∃y)П(x,y,-5)

b) (⩝y)(∃x)S(x,y,-5)
Вариант 4
1. Для заданной булевой функции трех переменных

а) Построить таблицу истинности , привести функцию к СДНФ, СКНФ

б) Минимизировать полученную СДНФ с помощью карт Карно

в) Найти многочлен Жегалкина. Выяснить, является ли данная булева функция линейной?

(z→x)(x│

)

2. Пусть S(x,y,z) и П(x,y,z) – соответственно предикаты сложения (z является суммой x и y) и умножения (z является произведением x и y), рассматриваемые на множестве Z – всех целых чисел и на множестве N₀=NU{0} целых неотрицательных чисел. Какой смысл имеют следующие формулы и на каком множестве Z или N₀ они истинны?

а) (Ǝy)(∃x)П(x,y,0)

b) (∃x)(∃y)S(x,y,-12)

3.4.3. Примерный перечень вопросов к зачету (экзамену) по разделам учебной дисциплины

Роль математической логики, как теоретической основы математики.
Влияние математической логики на развитие информатики.
Понятие искусственного интеллекта.
Необходимость формализации рассуждений.
Понятие высказывания.
Синтаксис исчисления высказывания.
Интерпретация формул в исчислении высказываний.
Общезначимые, выполнимые и невыполнимые формулы.
Дизъюнктивные и конъюнктивные нормальные формы в исчислении высказываний.
Проблема дедукции и ее значение в математической логике и информатике.
Прямая и обратная дедукция.
Метод резолюций для решения проблемы дедукции.
Дизъюнкты Хорна.
Метод резолюций для дизъюнктов Хорна.
Понятие предиката.
Синтаксис исчисления предикатов.
Кванторы и типы вхождения переменных в формулы.
Связь исчисления предикатов с системами представления знаний в задачах искусственного интеллекта.
Определение аксиоматических систем.
Правило вывода MODUS PONENS/
Теорема Геделя о неполноте.
Определение алгоритма.
Рекурсивная функция.
Определение нормального алгорифма Маркова.
Функция вычислимая по Маркову.
Машина Тьюринга.
Устройство машины Тьюринга и ее работа.

3.4.4. Рекомендуемые информационные источники

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

1. Судоплатов С. В., Овчинникова Е. В. Математическая логика и теория алгоритмов. Учебник – М.: Новосибирский государственный технический университет (НГТУ), Инфра-М, 2008

2. Игошин В. И. Математическая логика и теория алгоритмов – М.: Академия, 2008
Дополнительная литература

Тейз А. и др. Логический подход к искусственному интеллекту. - М.: Мир, 1990
Исследование вычислительной сложности алгоритмов логического вывода: Методические указания к курсовой работе по дисциплине "Математическая логика и теория алгоритмов"/ Сост.: Пантелеев М.Г., Календарев А.С.; ГЭТУ. СПб.: 1997
Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. - М: Наука, 1983

Перечень обучающих и контролирующих компьютерных программ

http://www. exponenta.ru – «Образовательный математический сайт Exponenta.ru».
http://www. matclub.ru – Лекции, примеры решения задач, интегралы и производные, дифференцирование, ТФКП, Электронные учебники. Типовой расчет из задачника Кузнецова.
http://www. math.ru – «Образовательный математический сайт Math.ru».
http://www. mathelp.spb.ru – «Высшая математика» (помощь студентам) – Лекции, электронные учебники, решение контрольных работ.
http://www. mathelp.spb.ru – Лекции по высшей математике: Математический анализ; Дифференциальные уравнения; Аналитическая геометрия, Теория вероятностей и др.
http://www.fismat.ru – Высшая математика для студентов и абитуриентов – интегралы и производные, ряды, ТФКП, дифференцирование, лекции, задачи, учебники.
http://www.truba.nnov.ru – Сайт о математическом анализе.
http://www.aup.ru/books/i008.htm - Электронные книги по экономико-математическим методам и моделям.

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

	Цель дисциплины рассмотрение методов исследования, т е. методов проверки,... В программе курса отражены методы проверки, обоснования, оценивания количественных закономерностей и качественных утверждений (гипотез)...		Рабочая программа по русскому языку в 9 классе индивидуальное обучение 2013-2014 учебный год Количество часов 2 часа в неделю, 68 часов в год. Учитывая состояние обучающегося, обучение ведется в ознакомительном плане. Основные...
	Тематическое планирование по биологии 11 класс Сущность, значение и соотношение между собой событий, явлений, процессов, законов и исторических закономерностей		Положение о ведении классных журналов Сущность, значение и соотношение между собой событий, явлений, процессов, законов и исторических закономерностей
	Урок основная организационная форма Сущность, значение и соотношение между собой событий, явлений, процессов, законов и исторических закономерностей		Программа основного общего образования (5-9 класс) Сущность, значение и соотношение между собой событий, явлений, процессов, законов и исторических закономерностей
	Урок в шестом классе на тему "царство растения" Сущность, значение и соотношение между собой событий, явлений, процессов, законов и исторических закономерностей		Программа по формированию навыков безопасного поведения на дорогах... Тема: распознавание слов, отвечающих на вопрос кто? И слов, отвечающих на вопрос что?
	Решение задач, предлагаемых в изученной литературе Выявить уровень владения абитуриента научной терминологией, ведущих идей, закономерностей и законов, относящейся к курсу экология...		Школьная олимпиада по биологии 6 класс Знание главнейших понятий, закономерностей и законов, касающихся строения, жизни и развития растительного, животного и человеческого...
	Xx гимназическая научно-практическая конференция Знание главнейших понятий, закономерностей и законов, касающихся строения, жизни и развития растительного, животного и человеческого...		Научные исследования в заповеднике «Кузнецкий Алатау» Знание главнейших понятий, закономерностей и законов, касающихся строения, жизни и развития растительного, животного и человеческого...
	Ii всероссийская (XVII) молодежная научная конференция Знание главнейших понятий, закономерностей и законов, касающихся строения, жизни и развития растительного, животного и человеческого...		Конспект урока по изобразительному искусству в 5 классе Тема : Древние... Сущность, значение и соотношение между собой событий, явлений, процессов, законов и исторических закономерностей
	Пояснительная записка Цели и задачи дисциплины Изучение фундаментальных... Формирование навыков проведения научных исследований, ознакомление с современной научной аппаратурой. Ознакомление с историей физики...		Урок 13 Биология. 7 класс Тема: «Отдел Мхи» Знание главнейших понятий, закономерностей и законов, касающихся строения, жизни и развития растительного, животного и человеческого...