Образовательный стандарт по направлению 552800 «Информатика и вычислительная техника» (код оксо 230100) Рабочая программа

Вид материала

Образовательный стандарт

Содержание Составитель рабочей программы Цели и задачи учебной дисциплины Содержание дисциплины Учебно-методические материалы дисциплины 3.3. Основная и дополнительная литература 5. Протокол согласования рабочей программы учебной дисциплины. 6. Лист дополнений и изменений внесенных, в рабочую программу Федеральное агентство по образованию Направление 552800 "Информатика и вычислительная техника" 1. Общие положения

Подобный материал:

• Образовательный стандарт по направлению 552800 «Информатика и вычислительная техника», 245.41kb.
• Образовательный стандарт по направлению 552800 «Информатика и вычислительная техника», 199.12kb.
• Образовательный стандарт по направлению 552800 Информатика и вычислительная техника, 169.1kb.
• Образовательный стандарт по направлению 552800 Информатика и вычислительная техника, 255.08kb.
• Образовательный стандарт по направлению 552800 «Информатика и вычислительная техника», 166.41kb.
• Образовательный стандарт по направлению бакалавриата 552800 "Информатика и вычислительная, 565.08kb.
• Образовательный стандарт по направлению бакалавриата 552800 (230100) «Информатика, 198.39kb.
• Образовательный стандарт по направлению бакалавриата 552800 (230100) «Информатика, 288.84kb.
• Образовательный стандарт по направлению 230100. 62 Информатика и вычислительная техника, 328.94kb.
• Образовательный стандарт По направлению 552800 «Информатика и вычислительная техника», 114.27kb.

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ВОЛЖСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ (ФИЛИАЛ)

ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

КАФЕДРА “ИНФОРМАТИКА И ТЕХНОЛОГИЯ ПРОГРАММИРОВАНИЯ”


Утверждаю

Зам. директора по

учебной работе

___________Тишин О.А.

«__» _____________2006 г

Образовательный стандарт

по направлению 552800 «Информатика и вычислительная техника» (код ОКСО 230100)


Рабочая программа

По дисциплине «Математическая логика и теория алгоритмов »

Факультет инженерно-экономический

Курс	1
Семестр	2
Всего часов по учебному плану	102
Всего аудиторных занятий, часов	51
Лекции, часов	34
Лабораторные занятия, час	-
Практические занятия, час	17
СРС, час	51
ОргСРС, часов	13
Экзамен (семестр)	2
Зачет (семестр)	-

Волжский 2006 г.

Рабочая программа составлена на основании учебного плана по направлению 5528 «Информатика и вычислительная техника»

Составитель рабочей программы

Ст. преподаватель ________________ Бовда Н.Д.


Рабочая программа утверждена на заседании кафедры “Информатика и технология программирования”


Протокол №___ от“ ___” _______________ 2006 г.


Заведующий кафедрой

“Информатика и

технология программирования”

к.т.н., доцент ____________Рыбанов А.А.


Одобрено научно-методическим советом инженерно-экономического факультета ВПИ ВолгГТУ


Протокол №___ от“ ___” _______________ 2006 г.


Председатель

научно-методического совета ___________ Е.А. Приходько


Декан факультета ___________ Е.А. Приходько


Согласовано

зав. выпускающей кафедры

доцент, к.т.н. _____________Капля В.И.

1. Цели и задачи учебной дисциплины
   

Курс «Математическая логика и теория алгоритмов » как средство формирования понятий, как язык, как метод мышления является основополагающим для студентов данной специальности. данный курс представляет сжатое введение в некоторые основные разделы математической логики. Число новых понятий в курсе довольно велико, поэтому для овладения этими понятиями строгость изложения сведена до минимума. Целью курса является не детальное изучение сложной математической теории, а усвоение основных идей логики, овладение методами логического вывода и автоматического доказательства, понимание того, что можно и что нельзя сделать с помощью ЭВМ.

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

Целью изучения дисциплины является:

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

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

В процессе изучения курса студент должен:

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

3. Взаимосвязь учебных дисциплин
   

Изучение дисциплины «Математическая логика и теория алгоритмов» базируется в основном на знаниях математики, полученных в школе, а также знаниях основ теории множеств и булевой алгебры, полученных при изучении курса «Дискретная математика» в первом семестре обучения.

Знания полученные при изучении курса «Математическая логика и теория алгоритмов» в дальнейшем используются при изучении следующих специальных дисциплин: «Основы трансляции», «Основы разработки автоматизированных систем», «Математическое моделирование и оптимизация», «Основы конструирования машин».

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

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


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

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


Таблица 2.1. Содержание учебной дисциплины «Математическая логика и теория алгоритмов»

№ темы	Название темы, наименование вопросов, изучаемых на лекциях	Лекций, час	Практич. занятия	Лаб. раб.	Метод. указ	Форма контроля
1.	Математическая логика				1,2	Сем.з,Эк
1.1.	Понятие логической системы. Семантика и синтаксис.	2	1
1.2.	исчисление высказываний: правильно построенные формулы, логическое следование и правило МР, теорема дедукции, способы доказательства: таблицы истинности, алгоритм Вонга, метод резолюций	4	1
1.3.	Система аксиом исчисления высказываний. Полнота и непротиворечивость	2	2
1.4.	Исчисление предикатов - синтаксис и семантика языка логики предикатов. Непротиворечивость, дедукция; теорема Геделя о полноте; клаузальные формы; метод резолюций в исчислении предикатов	4	2,3
1.5.	Формальные (аксиоматические) системы, формальный вывод и метатеории формальных систем	2	4
1.6.	Другие формальные системы: многозначные логики, вероятностная и модальная логики, нечетная логика, интуиционистская логика, динамическая логика, алгоритмическая логика Ч. Хоара	2	4,5
1.7.	Формальная арифметика, рекурсивные функции, геделевы номера.	4	5,6
2.	теория алгоритмов					экзамен
2.1.	Формализация понятия алгоритма, тезис Черча	2	7
2.2.	машина Тьюринга	2	8
2.3.	Неразрешимые проблемы	2	8
2.4.	Меры сложности алгоритмов; легко и трудноразрешимые задачи	2
2.5.	Классы задач P и NP; NP- полные задачи; понятие сложности вычислений; эффективные алгоритмы	2	9
2.6.	Основы нечетной логики	2	9
2.7.	Элементы алгоритмической логики	2	9
	Итого:	34

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

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

Таблица 3.1. Практические занятия

№	Наименование темы занятия	Объем в часах
1.	Исчисление высказываний: правильно построенные формулы, логическое следование и правило modus ponens	2
2.	Дедукция в исчислении высказываний; таблицы истинности, алгоритм Вонга и метод резолюций	2
3.	Синтаксис и семантика языка логики предикатов	2
4.	Клаузальные формы и метод резолюций в логике предикатов	2
5.	Формальная арифметика, рекурсивные функции	2
6.	Геделевы номера	2
7.	Формализация понятия алгоритма; эффективная вычислительность; тезис Черча	2
8.	машина Тьюринга	2
9.	Классы задач P и NP; NP- полные задачи; сложность вычислений и эффективные алгоритмы	1
	Итого:	17

3.2. Организуемая самостоятельная работа студентов


Таблица 3.2. Организуемая самостоятельная работа студентов

Форма ОргСРС	№ семестра	Срок выполнения	Время на выполнение
Семестровое задание	2	20 мая	13

3.3. Основная и дополнительная литература

1. В.Н. Нефедов, В.А. Осипова «Курс дискретной математики». М., МАИ, 1992.
   
2. Я.М. Ерусалимский «Дискретная математика». М., Вузовская книга, 2001.
   
3. С.В. Судоплатов, Е.В. Овчинникова «Элементы дискретной математики», Москва, ИНФРА-М, 2002.
   
4. Ф.А. Новиков «Дискретная математика для программистов». СПб: Питер, 2001.
   
5. И.А. Лавров, Л.Л. Максимова. «Задачи по теории множеств, математической логике и теории алгоритмов». М., Физматлит, 2002.
   
6. Мендельсон Э. ВВедение в математическую логику, М.: Наука, 1976 .
   
7. Клини С. Введение в математику, М.: 1957 г.
   
8. Новиков П. Элементы математической логики, М.: 1973
   
9. Ершов Ю.Л., Палютин Е.А. Математическая логика, М.: 1979 г.
   
10. Линдон Р. Заметки по логике, М.: 1968 г.
    
11. Мальцев А.И. Алгоритмы и рекурсивные функции, М.: 1976 г.
    
12. Матросов В.Л. Теория алгоритмов: учебник – М.? Энергия, 1972 г.
    
13. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи, М.: 1982 г.
    

4. Перечень методических указаний
   

1. Методы доказательства в исчислении высказываний: Методические указания для студентов дневной формы обучения по курсу «Математическая логика и теория алгоритмов». / Сост.: ст. преп. ВПИ ВолгГТУ Н. Д. Бовда – Волгоград 2006г.
   
2. .Минимизация булевых функций. Методические указания. Волгоград 2000 г.
   

3. Рейтинговый контроль изучения дисциплины
   

Таблица 4.1.

Виды занятий	Баллы
	2 семестр
Практические занятия	40
ОргСРС	20
Экзамен	40
Итого	100

5. Протокол согласования рабочей программы учебной дисциплины.

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

6. Лист дополнений и изменений внесенных, в рабочую программу.

Дополнения и изменения	Номер протокола. Дата пересмотра. Подпись зав. каф.	Дата утверждения и подпись декана

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ВОЛЖСКИЙ ПОЛИТЕХНИЧЕСКИЙ ИНСТИТУТ (ФИЛИАЛ)

ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ


Кафедра « Информатика и технология программирования»

СОГЛАСОВАНО Зам. директора по учебной работе ______________Тишин О.А. «____»_______________2006 г.

УТВЕРЖДАЮ Зав. кафедрой ВИТ _______________Рыбанов А.А. «____»_____________2006 г.

МЕТОДИКА


Рейтингового контроля знаний студентов по дисциплине

«Математическая логика и теория алгоритмов»


Направление 552800 "Информатика и вычислительная техника"

(код ОКСО 230100)


Курс 1

Семестр 2


Разработал старший преподаватель кафедры

«Информатика и технология программирования»_____________ Н.Д. Бовда

Волжский 2006

1. ОБЩИЕ ПОЛОЖЕНИЯ

По дисциплине “Математическая логика и теория алгоритмов” предусмотрены следующие виды работ, за которые студенты в течение семестра получают соответствующие баллы:

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

Количество практических занятий в семестре – 8 (9)


2. тЕКУЩИЙ рейтинговый контроль по дисциплине

Таблица 1

№ п/п	Вид работы студента	Баллы
		Min	Max
1.	Посещение занятий	8	12
2.	Выполнение домашнего задания	12	16
3.	Самостоят. аудиторные работы	2	4
4.	Коллоквиум	2	4
5.	Ответы у доски с места	2	4
6.	Семестровое задание или контр. работа	15	20
	Сумма баллов	41	60
	Экзамен	1	40

3. Методика рейтингового контроля на экзамене и зачёте

К сдаче экзамена допускаются студенты, имеющие за семестр не менее 41 балла.

По дисциплине “ Математическая логика и теория алгоритмов ” предусмотрен экзамен. Экзаменационный билет включает два теоретических вопроса и задачу: теоретические вопросы оцениваются по 12 баллов каждый, задача-16 баллов. Положительная оценка на экзамене определяется в интервале 15-40 баллов.