1. Организационно-методический раздел. 1 Название курса. Математическая логика и теория алгоритмов



Дата08.10.2012
Размер87.9 Kb.
ТипДокументы
1. Организационно-методический раздел.

1.1 Название курса.

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

Направление - математика

Раздел - общие математические и естественно-научные дисциплины

Семестр(ы) - 2

1.2 Цели и задачи курса.

Основной курс "Математическая логика и теория алгоритмов" предназначен для студентов первого курса отделения прикладной инфоматики факультета информационных технологий Новосибирского государственного университета.

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

Для достижения поставленной цели выделяются задачи курса:

1) изучение теоретической части курса в соответствии с программой;

2) ознакомление с основными методам решения задач;

3) сдача экзамена и зачета.

1.3 Требования к уровню освоения содержания курса.

По окончании изучения указанного курса студент должен
- иметь представление о месте и роли изучаемой дисциплины среди других разделов математики;
- знать содержание программы курса, определения, формулировки теорем и их доказательства;

- иметь навыки решения задач.

1.4 Формы контроля

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

Текущий контроль. Предусмотрено проведение контрольной работы в середине каждого семестра.

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

2.1 Новизна.

Курс "Математическая логика и теория алгоритмов " является новым по отбору изучаемого материала. Курс характеризуется математической строгостью изложения, при этом достаточное внимание уделяется применениям изучаемых понятий и методов в информатике.


2.2 Тематический план курса.


Наименование разделов и тем

К о л и ч е с т в о ч а с о в

Лекции

Семинары

Лаборатор- ные работы

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

Всего часов

Логика высказываний

6

8

0

0

14

Теория множеств

10

8

0

0

18

Логика предикатов

6

4

0

0

10

Теория алгоритмов

10

12

0

0

22

Итого по курсу:

32

32

0

0

64

2.3 Содержание отдельных разделов и тем.

Математическая логика и теория алгоритмов
2.3.1. ЛОГИКА ВЫСКАЗЫВАНИЙ.

Язык логики высказываний. Понятие формулы. Таблицы истинности. Эквивалентность формул. Основные логические тождества. Нормальные формы. Приведение формулы к СДНФ и СКНФ.

Исчисление высказываний. Понятие вывода: линейного и в виде дерева. Допустимые правила вывода. Семантика исчисления высказываний, теорема о корректности. Синтаксическая эквивалентность формул, теорема о замене. Теорема о полноте исчисления высказываний.

2.3.2. ТЕОРИЯ МНОЖЕСТВ.

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

Отношения. Типы отношений. Композиция отношений, обратное отношение. Функции. Сюръективная, инъективная и биективная функции. Отношения частичного и линейного порядка, примеры. Отношение эквивалентности, фактор-множество и классы эквивалентности, теорема о разбиении.

Частично упорядоченные множества: понятия максимального, минимального, наибольшего и наименьшего элемента, (точной) верхней и нижней грани ч.у.м., примеры. Подобие (изоморфизм) частично упорядоченных множеств. Фундированные и вполне упорядоченные множества, примеры. Принцип трансфинитной индукции. Понятия цепи и индуктивного частично упорядоченного множества. Аксиома выбора, лемма Цорна и теорема Цермело (формулировки).

Сравнение множеств по мощности. Теорема Кантора-Бернштейна. Теорема Кантора. Конечные и бесконечные множества. Свойства бесконечных множеств. Счетные множества. Несчетность множества вещественных чисел.

2.3.3. ЛОГИКА ПРЕДИКАТОВ.

Понятия сигнатуры и алгебраической системы. Примеры. Термы и формулы логики предикатов. Истинность формулы на алгебраической системе. Примеры. Тождественно истинные и выполнимые формулы. Семантическая эквивалентность формул, основные эквивалентности. Пренексная нормальная форма.

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

Теории и их модели. Полные теории. Теорема о существовании модели (формулировка). Теорема компактности Мальцева. Теорема Гёделя о полноте исчисления предикатов.

Аксиматические теории PA и ZF.

2.3.4. ТЕОРИЯ АЛГОРИТМОВ.

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

Машины Тьюринга и Шенфилда. Функции, вычислимые на машинах Тьюринга и Шенфилда. Теорема о правильной вычислимости частично рекурсивных функций. Тезисы Чёрча и Тьюринга.

Вычислимые и вычислимо перечислимые множества. Теорема об эквивалентных определениях вычислимо перечислимых множеств. Теорема Поста.

Универсальные вычислимые функции, s-m-n-теорема, теорема о неподвижной точке. Пример частичной функции, не доопределимой до общерекурсивной. Пример вычислимо перечислимого множества, не являющегося вычислимым.

Гёделевская нумерация формул. Теорема Гёделя о неполноте формальной арифметики (формулировка).

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

2.5 Темы рефератов (курсовых работ).

Не предусмотрено.

2.6 Образцы вопросов для подготовки к экзамену (дифференцированному зачету, зачету).

  1. Язык логики высказываний. Понятие формулы. Таблицы истинности.

  2. Эквивалентность формул. Основные логические тождества.

  3. Нормальные формы. Приведение формулы к СДНФ и СКНФ.

  4. Исчисление высказываний. Понятие вывода: линейного и в виде дерева. Допустимые правила вывода.

  5. Семантика исчисления высказываний. Тождественно истинные формулы. Теорема о корректности.

  6. Теорема о полноте исчисления высказываний.

  7. Множества, основные операции над множествами и их свойства.

  8. Декартово произведение множеств, упорядоченные пары и наборы.

  9. Отношения. Типы отношений. Композиция отношений, обратное отношение.

  10. Функции. Сюръективная, инъективная и биективная функции.

  11. Отношения частичного и линейного порядка, примеры.

  12. Отношение эквивалентности. Фактор-множество и классы эквивалентности. Теорема о разбиении.

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

  14. Подобие (изоморфизм) частично упорядоченных множеств. Перечислить (с точностью до подобия) все трехэлементные ч.у.м.

  15. Фундированные и вполне упорядоченные множества, примеры.

Принцип трансфинитной индукции.

  1. Теорема о подобии одного вполне упорядоченного множества начальному сегменту другого.

  2. Понятия цепи и индуктивного частично упорядоченного множества. Аксиома выбора, лемма Цорна и теорема Цермело (формулировки).

  3. Сравнение множеств по мощности. Теорема Кантора-Бернштейна. Теорема Кантора.

  4. Конечные и бесконечные множества. Свойства бесконечных множеств. Счетные множества. Несчетность множества вещественных чисел.

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

  6. Термы и формулы логики предикатов. Истинность формулы на алгебраической системе. Примеры.

  7. Тождественно истинные и выполнимые формулы. Семантическая

эквивалентность формул, основные эквивалентности. Пренексная нормальная форма.

  1. Исчисление предикатов: аксиомы и правила вывода.

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

  3. Теории и их модели. Полные теории. Теорема о существовании модели. Теорема компактности Мальцева.

  4. Теорема Гёделя о полноте исчисления предикатов.

  5. Примитивно-рекурсивные и частично-рекурсивные функции.

  6. Машины Тьюринга (Шенфилда). Функции, вычислимые на машинах Тьюринга (Шенфилда).

  7. Теорема о правильной вычислимости частично-рекурсивных функций (формулировка). Тезисы Чёрча и Тьюринга.

  8. Рекурсивные и рекурсивно перечислимые множества. Теорема об эквивалентных определениях рекурсивно перечислимых множеств.

  9. Теорема Поста.

  10. Универсальные рекурсивные функции.

  11. Пример частичной функции, не доопределимой до общерекурсивной. Пример рекурсивно перечислимого множества, не являющегося рекурсивным.

  12. Гёделевская нумерация формул. Теорема Гёделя о неполноте формальной арифметики (формулировка).


2.7 Список основной и дополнительной литературы.

1. Ю.Л. Ершов, Е.А. Палютин, Математическая логика. М., Наука, 1989.

2. И.А. Лавров, Л.Л. Максимова, Задачи по теории множеств, математической логике и теории алгоритмов. М. Наука, 2004.

3. Н.Н. Непейвода, Прикладная логика, Новосибирск, изд-во НГУ, 2002.

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

Не предусмотрено.

Программу составил к.ф.-м.н. А.И. Стукачев

Похожие:

1. Организационно-методический раздел. 1 Название курса. Математическая логика и теория алгоритмов iconРабочая программа дисциплины Математическая логика и теория алгоритмов Направление подготовки 230700 Прикладная информатика
Целями освоения дисциплины «Математическая логика и теория алгоритмов» являются получение теоретических знаний по основам математическая...
1. Организационно-методический раздел. 1 Название курса. Математическая логика и теория алгоритмов iconУчебная программа Дисциплины р2 «Математическая логика и теория алгоритмов»
Фгос впо, содействует формированию мировоззрения и системного мышления. Целью преподавания дисциплины «Математическая логика и теория...
1. Организационно-методический раздел. 1 Название курса. Математическая логика и теория алгоритмов iconИзложение материала курса «Математическая логика и теория алгоритмов»
Лекции по математической логике и теории алгоритмов для студентов 2 курса специальности «Компьютерная безопасность»
1. Организационно-методический раздел. 1 Название курса. Математическая логика и теория алгоритмов iconЭкзаменационные вопросы по дисциплине: «Математическая логика и теория алгоритмов». Раздел основы математической логики
Логика высказываний: простые высказывания, логические связки, сложные высказывания
1. Организационно-методический раздел. 1 Название курса. Математическая логика и теория алгоритмов iconРабочая программа по курсу «Математическая логика и теория алгоритмов» для специальности 090102 «Компьютерная безопасность»
«Математическая логика и теория алгоритмов», рекомендованной Министерством образования Российской Федерации в 2000 году для специальностей...
1. Организационно-методический раздел. 1 Название курса. Математическая логика и теория алгоритмов iconТехнологий В. П. Битюцкий Н. В. Папуловская Математическая логика. Исчисления высказываний и предикатов Методическое пособие по дисциплине "Математическая логика и теория алгоритмов" Екатеринбург 2005 удк

1. Организационно-методический раздел. 1 Название курса. Математическая логика и теория алгоритмов iconМосковская государственная академия приборостроения и информатики кафедра " Персональные компьютеры и сети"
Ульянов М. В., Шептунов М. В. Математическая логика и теория алгоритмов, часть 1: Математическая логика. – М.: Мгапи, 2003. – 47...
1. Организационно-методический раздел. 1 Название курса. Математическая логика и теория алгоритмов iconМесто дисциплины в структуре ооп принципы построения курса: Курс входит в математический и естественнонаучный цикл ооп 010300 «Фундаментальная информатика и информационные технологии»
«Логика», «Математическая логика и теория алгоритмов», «Дискретная математика», «Языки программирования»
1. Организационно-методический раздел. 1 Название курса. Математическая логика и теория алгоритмов icon3 Введение. Математическая логика в системе современного образования 6
Математическая логика и теория алгоритмов: Учеб посо­бие для студ высш учеб заведений / Владимир Иванович Игошин. — М.: Издательский...
1. Организационно-методический раздел. 1 Название курса. Математическая логика и теория алгоритмов iconАвтоматизированная обучающая система поддержки курса "математическая логика и теория алгоритмов"
В докладе обсуждаются возможности и результаты использования компьютерных обучающих программ
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org