Geum.ru

М. К. Аммосова институт математики и информатики рабочая программа

Вид материалаРабочая программа

Содержание


Рабочая программа утверждена на заседании кафедры алгебры и геометрии
Выписка из учебного плана (ОПД.Ф.06)
Распределение часов
Недельная нагрузка
Дисциплина – математическая логика и теория алгоритмов
3. Принципы и цели
3.2. Цели курса
7. Рекомендуемая литература
Дополнительная литература
8. Контролирующие материалы
Подобный материал:

МИНИСТЕРСТВО ОБРАЗОВАНИЯ

РОССИЙСКОЙ ФЕДЕРАЦИИ

ЯКУТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМ. М.К. АММОСОВА


ИНСТИТУТ МАТЕМАТИКИ И ИНФОРМАТИКИ


РАБОЧАЯ ПРОГРАММА


курса

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

(наименование курса)


Для государственных университетов

Направление 510100 – Математика


(шифр, название)


Степень – бакалавр математики


Якутск 2004


Составители: ассистент Иванова А.О.,

ст. преподаватель Антонен А.И.

(уч. ст., уч. зв., должн., ФИО)


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


“ “ _________________ 2004 г. протокол № _____

Зав. кафедрой: Никитина Е.С.


Рабочая программа утверждена на заседании методкомиссии ИМиИ

“ “ _________________ 2004 г. протокол № _____


Председатель методкомиссии ИМиИ: Афанасьева В.И.


Рабочая программа утверждена на заседании научно – методического совета ЯГУ

“ “ _________________ 2004 г. протокол № _____


Председатель научно – методического совета ЯГУ: Яковлева А.Н.


Выписка из учебного плана (ОПД.Ф.06)


Объем работы студентов (в часах) из учебного плана направления 510100 – Математика составляет 100 часов, в том числе:

– аудиторных занятий – 54;

– СРС – 46.

Распределение часов


Вид занятий
Семестр

VI (18 нед.)

Аудиторные
54

Лекционные
36

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

СРС
46

Итого
100

Форма контроля
Зачет


Недельная нагрузка


Вид занятий
Семестр

VI

Аудиторные

3

Лекционные

2

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



  1. ТРЕБОВАНИЯ К ОБЯЗАТЕЛЬНОМУ МИНИМУМУ СОДЕРЖАНИЯ ОСНОВНОЙ ОБРАЗОВАТЕЛЬНОЙ ПРОГРАММЫ ПОДГОТОВКИ БАКАЛАВРА МАТЕМАТИКИ ПО СПЕЦИАЛЬНОСТИ 510100 - Математика

ДИСЦИПЛИНА – МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ


Логические исчисления, модели: исчисление высказываний; аксиомы; правило вывода; производные правила вывода; тождественная истинность выводимых формул; непротиворечивость исчисления высказываний; теорема о полноте исчисления высказываний; предикаты; логические операции над предикатами и их теоретико-множественный смысл; кванторы; геометрический смысл квантора существования; модели; формулы; свободные и связанные переменные; истинность формул в модели, на множестве; общезначимые формулы; эквивалентные формулы логики предикатов; правила преобразований формул в эквивалентные; нормальная форма; исчисление предикатов; аксиомы; правила вывода; производные правила вывода; тождественная истинность выводимых формул; непротиворечивость исчисления предикатов; формулировка теоремы о полноте исчисления предикатов. *Теорема о полноте для случая одноместных предикатов. Вычислимые функции: машины Тьюринга; вычислимые функции; тезис Черча; примеры вычислимых функций; рекурсивные, рекурсивно перечислимые множества и их алгоритмическая характеристика; теорема Поста; примеры алгоритмически неразрешимых проблем; неразрешимость проблем самоприменимости, применимости; теорема Поста-Маркова о существовании ассоциативного исчисления с алгоритмически неразрешимой проблемой равенства. *Теорема о неразрешимости проблемы распознавания тождественно истинных формул исчисления предикатов; операции суперпозиции и примитивной рекурсии; примитивно-рекурсивные функции; операция минимизации; частично-рекурсивные функции; вычислимость частично-рекурсивных функций; частичная рекурсивность вычислимых функций; формула Клини.


2. ТРЕБОВАНИЯ СТАНДАРТА К УРОВНЮ ПОДГОТОВКИ ВЫПУСКНИКА ПО СПЕЦИАЛЬНОСТИ 510100 – Математика


Бакалавр математики отвечает следующим требованиям:

    1. Имеет целостное представление о процессах и явлениях, происходящих в неживой и живой природе, понимает возможности современных научных методов познания природы и владеет ими на уровне, необходимом для решения задач, имеющих естественнонаучное содержание и возникающих при выполнении профессиональных функций;
    2. Способен продолжить обучение в магистратуре и по специальности, в соответствии с п.1.3., вести профессиональную деятельность в иноязычной среде (требование рассчитано на реализацию в полном объеме через 10 лет);
    3. Владеет культурой мышления, знает его общие законы, способен в письменной и устной речи правильно (логически) оформить его результаты;
    4. Умеет на научной основе организовать свой труд, владеет компьютерными методами сбора, хранения и обработки (редактирования) информации, применяемые в сфере его профессиональной деятельности;
    5. Способен в условиях развития науки и изменяющейся социальной практики к переоценке накопленного опыта, анализу своих возможностей, умеет приобретать новые знания, обучаться в магистратуре, использовать другие формы обучения, включая самостоятельные и информационно образовательные технологии;
    6. Понимает сущность и социальную значимость своей будущей профессии, основные проблемы дисциплин, определяющих конкретную область его деятельности, видит их взаимосвязь в целостной системе знаний;
    7. Способен к проектной деятельности в профессиональной сфере на основе системного подхода, умеет строить и использовать модели для описания и прогнозирования различных явлений, осуществлять их качественный и количественный анализ;
    8. Способен поставить цель и сформулировать задачи, связанные с реализацией профессиональных функций, умеет использовать для их решения методы изученных им наук;
    9. Готов к кооперации с коллегами и работе в коллективе, знаком с методами управления, умеет организовать работу исполнителей, находить и принимать управленческие решения в условиях различных мнений, знает основы педагогической деятельности;
    10. Методически и психологически готов к изменению вида и характера своей профессиональной деятельности, работе над междисциплинарными проектами;
    11. Способен к совершенствованию своей профессиональной деятельности в области математики.


3. ПРИНЦИПЫ И ЦЕЛИ


3.1. Принципы построения курса


3.1.1. Данный курс разработан в соответствии с Государственным образовательным стандартом высшего профессионального образования по специальности 510100 – Математика;

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

3.1.3. Курс имеет теоретическую направленность: лекционные – 36 ч., самостоятельная работа – 46 ч.;

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

3.2. Цели курса


№
Содержание

Студент должен иметь представление о


понятиях, лежащих в основе логических исчислений


задачах, поддающихся решению методами математической логики; задачах упрощения электрических цепей


построении конструктивных моделей; приложениях к анализу и алгебре


физической интерпретации пропозициональных форм и алгебраических систем


месте предмета в системе математических дисциплин и роли оснований

Студент должен знать


правила вывода, элементарного мономорфизма


свойства пропозициональных форм, электрических цепей, алгебраических форм, электрических цепей, алгебраических систем


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


теорему дедукции

Студент должен уметь


решать задачи на преобразование пропозициональных форм, построение алгебраических систем и теорий


строить таблицы истинности, упрощать формулу с помощью равносильных преобразований


находить СДНФ и СКНФ формулы


составлять РКС и упрощать ее


приводить формулу логики предикатов к ПНФ


пользоваться правилами вывода и производными правилами вывода


строить машины Тьюринга; по данной машине Тьюринга определять функцию, которую она задает


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


использовать формулу как единицу математического текста



7. РЕКОМЕНДУЕМАЯ ЛИТЕРАТУРА


ОСНОВНАЯ ЛИТЕРАТУРА

  1. Мендельсон Э. Введение в математическую логику. – М: 1976
  2. Лихтарников Л.М., Сукачева Т.Г. Математическая логика. – Санкт-Петербург: 1999
  3. Антонен А.И., Попов О.Н., Иванова А.О. Лабораторные работы по курсу «Математическая логика» (методические указания). – Якутск: 2001


ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА

  1. Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.: 1979
  2. Игошин В.И. Задачник – практикум по математической логике. – М.: 1986
  3. Игошин В.И. Математическая логика и теория алгоритмов. – Саратов: 1991
  4. Кейслер Г., Чен Ч. Теория моделей. – М.: 1977
  5. Лавров И.А, Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. – М.: 1975
  6. Лихтарников Л.М. Задачи мудрецов: Книга для учащихся. – М.: 1996
  7. Мальцев А.И. Алгоритмы и рекурсивные функции. – М.: 1965
  8. Математическая логика (под общей редакцией А.А. Столяра и др.). – Минск: 1991
  9. Михайлов А.Б., Плоткин А.И. Введение в алгебру и математический анализ. Сборник задач 1. Высказывания. Предикаты. Множества. – Санкт-Петербург: 1992
  10. Новиков П.С. Элементы математической логики. – М.: 1973
  11. Новиков П.С. Элементы математической логики. – М.: 1973
  12. Сакс Дж. Теория насыщенных моделей.
  13. Черч А. Введение в математическую логику. – М.: 1960
  14. Шенфильд Дж. Математическая логика. – М.: 1975
  15. Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. – М.: 1966



8. КОНТРОЛИРУЮЩИЕ МАТЕРИАЛЫ


Вопросы коллоквиумов.

Модуль 1. Алгебра логики.
  1. Высказывания. Логические операции над высказываниями.
  2. Формулы. Истинностные значения формул.
  3. Основные равносильности. Равносильные преобразования формул.
  4. Полные и неполные системы функций. СДНФ и СКНФ.
  5. Тавтологии. Две теоремы о тавтологиях.

Модуль 2. Исчисление высказываний.
  1. Доказательство формул выводимости. Правила выводимости.
  2. Теорема дедукции.
  3. Непротиворечивость, полнота и разрешимость исчисления высказываний.

Модуль 3. Исчисление предикатов.
  1. Понятие предиката. Формулы логики предикатов.
  2. Истинности значений логики предикатов.
  3. Равносильности логики предикатов.
  4. Предваренная нормальная форма. Общезначимость и выполнимость формул.
  5. Проблема разрешения для общезначимости и выполнимости формул.
  6. Язык первого порядка. Термы и формулы.
  7. Логические и специальные аксиомы.
  8. Правила вывода. Доказательство теории.
  9. Проблемы непротиворечивости, полноты, разрешимости теорий.
  10. Непротиворечивость исчисления предикатов.
  11. Интерпретация языка теории.
  12. Истинностные значения формул в интерпретации.
  13. Модель теории.
  14. Категоричность теории.
  15. Теорема полноты.
  16. Теория натуральных чисел.
  17. Теорема Геделя о неполноте.