Название курса
Скачать 87.9 Kb.
|
| 1. Организационно-методический раздел. 1.1 Название курса. Математическая логика и теория алгоритмов. Направление - математика Раздел - общие математические и естественно-научные дисциплины Семестр(ы) - 2 1.2 Цели и задачи курса. Основной курс "Математическая логика и теория алгоритмов" предназначен для студентов первого курса отделения прикладной инфоматики факультета информационных технологий Новосибирского государственного университета. Основной целью освоения курса является изучение студентами основных понятий и результатов математической логики и теории алгоритмов, а также освоение практических методов решения задач. Для достижения поставленной цели выделяются задачи курса: 1) изучение теоретической части курса в соответствии с программой; 2) ознакомление с основными методам решения задач; 3) сдача экзамена и зачета. 1.3 Требования к уровню освоения содержания курса. По окончании изучения указанного курса студент должен - иметь представление о месте и роли изучаемой дисциплины среди других разделов математики; - знать содержание программы курса, определения, формулировки теорем и их доказательства; - иметь навыки решения задач. 1.4 Формы контроля Итоговый контроль. Для контроля усвоения дисциплины учебным планом предусмотрены зачет и экзамен в конце первого семестра, а также дифференцированный зачет в конце второго семестра. Текущий контроль. Предусмотрено проведение контрольной работы в середине каждого семестра. 2 Содержание дисциплины. 2.1 Новизна. Курс "Математическая логика и теория алгоритмов " является новым по отбору изучаемого материала. Курс характеризуется математической строгостью изложения, при этом достаточное внимание уделяется применениям изучаемых понятий и методов в информатике. 2.2 Тематический план курса.
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 Образцы вопросов для подготовки к экзамену (дифференцированному зачету, зачету).
Принцип трансфинитной индукции.
эквивалентность формул, основные эквивалентности. Пренексная нормальная форма.
2.7 Список основной и дополнительной литературы. 1. Ю.Л. Ершов, Е.А. Палютин, Математическая логика. М., Наука, 1989. 2. И.А. Лавров, Л.Л. Максимова, Задачи по теории множеств, математической логике и теории алгоритмов. М. Наука, 2004. 3. Н.Н. Непейвода, Прикладная логика, Новосибирск, изд-во НГУ, 2002. 2.8 Для изучения дисциплин, которые предусматривают использование нормативно-правовых актов, указывать источник опубликования. Не предусмотрено. Программу составил к.ф.-м.н. А.И. Стукачев | |||||||||||||||||||||||||||||||||||||||||
Добавить документ в свой блог или на сайт
Похожие:
 | Название: 900 дней и ночей Название темы и раздела учебного курса: Великая война и Великая Победа. История нашей страны |  | Рабочая программа по географии (название учебного предмета, курса,... Программа курса географии 5–9 классов составлена на основе программы География: программа: 5 – 9 классы / А. А. Летягин, И. В. Душина... |
| Название курса Основной курс "Линейная алгебра и аналитическая геометрия" предназначен для студентов первого курса отделения прикладной инфоматики... | | Название курса «Алгебра». 9 класс Цель изучения курса: изучить свойства и графики элементарных функций, научиться использовать функционально-графические представления... |
| Рабочая программа по истории (название учебного предмета, курса,... ... | | Программа курса «Философия» Название курса. «Философия». Курс относится к разделу Федерального государственного образовательного стандарта высшего профессионального... |
| Календарно-тематический план по магистерской программе «Мировая экономика»... Календарно-тематический план по магистерской программе «Мировая экономика» по дисциплине (название читаемого курса) Экономика международного... | | Пояснительная записка цель данного курса Название курса: «Основы информационной культуры». Программа рассчитана на 64 часа и предназначается для учащихся 9-11 классов. Данный... |
| Освоение методики экспериментального исследования мира на уроках тризформатики в начальной школе Доклад базируется на «Пермской версии» пропедевтического курса информатики [1–4] (рабочее название курса – «тризформатика») и опыте... | | Название курса Смирнова Е. В., ст преподаватель кафедры дидактики и частных методик ипкиппро огпу |
| Название предмета или курса Рабочая программа учебного курса по алгебре для 9 класса разработана на основе Примерной программы основного общего образования (базовый... | | Название предмета или курса Рабочая программа учебного курса по алгебре для 8 класса разработана на основе Примерной программы основного общего образования (базовый... |
| Название Примечание Самостоятельная работа студентов в рамках учебного курса «Культурология» включает в себя | | Программа курса для специальности: (перечень специальностей, для... Программа курса составлена в соответствии с требованиями Государственного образовательного стандарта высшего профессионального образования... |
| Название курса Дисциплина "Теория расписаний" предназначена для студентов механико-математических факультетов университетов | | Название курса Выучить новые слова, найти в тексте все глаголы и объяснить употребление глагольных времен |
