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




Скачать 141.57 Kb.
НазваниеПрограмма дисциплины математическая логика и теория алгоритмов
Дата01.03.2013
Размер141.57 Kb.
ТипПрограмма дисциплины

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


"УТВЕРЖДАЮ"

Проректор

__________ В.С.Бухмин


ПРОГРАММА ДИСЦИПЛИНЫ


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


Цикл ЕН.Ф.


Специальность: 013800 – Радиофизика и электроника

Специализация: 013817 – Компьютерные информационные системы и защита информации


Принята на заседании кафедры Теории относительности и гравитации

(протокол № 6 от "5" июня 2009 г.)

Заведующий кафедрой
________________ (А.В. Аминова)



Утверждена Учебно-методической комиссией физического факультета КГУ.

(протокол №___ от "__"__________200__ г.)


Председатель комиссии
____________________ (Д.А. Таюрский)


Рабочая программа дисциплины "Математическая логика и теория алгоритмов" предназначена для студентов 3 курса

по специальности: 013800 – Радиофизика и электроника

Специализация: 013817 – Компьютерные информационные системы и защита информации


АВТОР: Иваньшин П.Н.


КРАТКАЯ АННОТАЦИЯ: Курс лекций «Математическая логика и теория алгоритмов» состоит из разделов: исчисление высказываний, исчисление предикатов, элементы теории булевых и псевдобулевых функций, многозначные логики (теория Полиа), теория алгоритмов, реляционное исчисление.


1. Требования к уровню подготовки студента, завершившего изучение дисциплины "Математическая логика и теория алгоритмов".

Студенты, завершившие изучение данной дисциплины должны:

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

  • овладеть методами решения соответствующих задач;

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



2. Объем дисциплины и виды учебной работы (в часах)

Форма обучения очная

Количество семестров 1

Форма контроля: 5 семестр экзамен



п/п


Виды учебных занятий

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







5 семестр

1.

Всего часов по дисциплине

100

2.

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

46

3.

Аудиторных занятий

54




в том числе: лекций

36




семинарских (или лабораторно-практических) занятий

18





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

ТРЕБОВАНИЯ ГОСУДАРСТВЕННОГО ОБРАЗОВАТЕЛЬНОГО СТАНДАРТА К ОБЯЗАТЕЛЬНОМУ МИНИМУМУ СОДЕРЖАНИЯ ПРОГРАММЫ



Индекс

Наименование дисциплины и ее основные разделы

Всего часов

ЕН.Ф.10

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

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

100

Примечание: Если дисциплина, устанавливается вузом самостоятельно, то в данной таблице ставится прочерк.


СОДЕРЖАНИЕ РАЗДЕЛОВ ДИСЦИПЛИНЫ.







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

N п/п

Название темы и ее содержание

лекции

лаб. практ. занятия

1

Элементы теории множеств. Понятия: алфавит, буква, слово, исчисление, аксиома, теорема. Операции теории множеств: пересечение, объединение, свойства операций.

2

1

2

Исчисление высказываний (ИВ). Понятия: алфавит ИВ, формула ИВ, терм. Правила вывода. Теорема о дедукции.

2

1

3

Эквивалентность формул. Основные эквивалентные формулы. Цепи эквивалентностей. Таблицы истинности.

2

1

4

Непротиворечивость ИВ, правила введения и удаления, полнота. Главная интерпретация ИВ (на множестве {0, 1}). Независимость ИВ.

2

1

5

Исчисление предикатов (ИП). Понятия: предикат, n-местное отношение (его свойства), функция как двуместное отношение, квантор. ИВ как часть ИП.

2

1

6

Общезначимость в ИП. Теорема о дедукции в ИП.

Непротиворечивость и правила вывода теории доказательств ИП.

2

1

7

Утверждения о полноте и непротиворечивости ИП. Теоремы Линденбаума и Геделя.

2

1

8

Булевы и псевдобулевы функции. Представление булевой функции в виде полинома. Степень представления. Псевдобулевы функции. Определение, представление в виде полиномов и позиформ (минимизация булевой функции). Пример: алгоритмическая теория графов.

2

1

9

Преобразование Фурье булевой и псевдобулевой функции. Вес Хэмминга булевой функции. Свойства дискретного преобразования Фурье.

2

1

10

Криптографичекие свойства булевых функций. Аффинная эквивалентность, алгебраическая степень, нелинейность, сбалансированность и k-резилентность. Линейные ядро и структура.

4

2

11

Многозначные логики. Основные типы: Лукашевича, Геделя, t-норм система, трехзначная, четырехзначная система Данна-Беллнапа, система произведения.

2

1

12

Функция k-значной логики. Отношение эквивалентности на множестве функций k-значной логики. Циклический полином. Лемма Бернсайда. Теоремы де Брюина и Полиа.

4

2

13

Понятие алгоритма и вычислимой функции. Примитивно и частично рекурсивные функции. Тезис Черча. Машина Тьюринга-Поста. Вычисления функций на машине Тьюринга-Поста. Универсальная машина Тьюринга. Теорема об универсальном алгоритме. Эффективные алгоритмы.

4

2

14

Сложность алгоритма. Оценки функции сложности. Пример: сложность арифметических операций. Классы задач P и NP. Тезис Колмогорова.

2

1

15

Реляционная алгебра, реляционное исчисление, понятие реляционной схемы, его характеристики. Операции реляционной алгебры. Базы данных.

2

1




Итого часов

36

18



ЛИТЕРАТУРА


1. E. Boros, P.L. Hammer, Pseudo-Boolean optimisation, survey, 2001.

2. Y. Crama, P.L. Hammer, Boolean functions. Theory, algorithms and applications, first draft, 2006.

3. C. Carlet, Boolean Functions for Cryptography and Error Correcting Codes, To appear soon as a chapter of the volume ”Boolean Methods and Models”, published by Cambridge University Press, Eds Yves Crama and Peter Hammer.

4. А.К. Гуц, Математическая логика и теория алгоритмов, Омск, 2003.

5. А.А. Марков, Н.М. Нагорный, Теория алгорифмов, Москва, Наука, 1984.

6. С.К. Клини, Математическая логика, Москва, Мир, 1973.

7. А.В. Черемушкин, Лекции по арифметическим алгоритмам в криптографии, Москва, МЦНМО, 2002.

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

9. С.Д. Кузнецов, Основы современных баз данных, Информационно-аналитические материалы Центра Информационных Технологий.

10. Н. Коблиц, Курс теории чисел и криптографии, Москва, ТВП, 2001.


Вопросы к экзамену


  1. Понятия теории множеств: алфавит, буква, слово, исчисление, аксиома, теорема. Определения и основные свойства.

  2. Операции теории множеств: пересечение, объединение, свойства операций.

  3. Основные понятия исчисления высказываний: алфавит ИВ, формула ИВ, терм, коньюнкция, дизьюнкция и их свойства.

  4. Правила вывода ИВ. Теорема о дедукции ИВ.

  5. Эквивалентность формул ИВ. Основные эквивалентные формулы ИВ (с доказательством). Цепи эквивалентностей ИВ.

  6. Теорема о замене связок ИВ.

  7. Таблицы истинности в ИВ. Теорема о подстановке вместо атомов.

  8. Основная теорема о подстановках.

  9. Теорема о дедукции ИВ и ее следствия.

  10. Понятия доказуемости и выводимости в ИВ. Теоремы о формальных доказательствах и выводах.

  11. Правила введения и удаления ИВ.

  12. Теорема о полноте ИВ.

  13. Главная интерпретация ИВ (на множестве {0, 1}).

  14. Основные понятия ИП: предикат, n-местное отношение (его свойства), функция как двуместное отношение, квантор. ИВ как часть ИП.

  15. Таблица истинности формулы ИП. Общезначимость в ИП.

  16. Основные утверждения об общезначимости ИП.

  17. Понятия следование, доказуемости и выводимости ИП.

  18. Теорема о дедукции ИП.

  19. Правила введения и удаления в ИП. Непротиворечивость ИП.

  20. Цепи эквивалентностей ИП. Теорема о замене.

  21. Теорема об изменении кванторов (основные формулы).

  22. Утверждения о полноте ИП. Лемма Линденбаума.

  23. Теорема Геделя о полноте ИП.

  24. Булевы функции. Определение, свойства. Булевы выражения.

  25. Двойственность для булевой функции. Свойства двойственных функций.

  26. Алгебраическая нормальная форма булевой функции. Теорема о представлении булевой функции в нормальной форме.

  27. Алгоритм получения нф булевой функции. Алгебраическая степень представления булевой функции в нормальной форме.

  28. Численная нормальная форма булевой и псевдобулевой функции. Обобщенная степень булевой функции.

  29. Основные представления булевых функций. Представление в виде позиформ.

  30. Алгоритмическая теория графов.

  31. Псевдобулевы функции. Определение, примеры, свойства.

  32. Представление псевдобулевой функции в виде полинома.

  33. Дискретное преобразование Фурье (Адамара) псевдобулевой функции. Алгоритм вычиления преобразования Фурье от данной функции. Вес Хэмминга.

  34. Свойства преобразование Фурье (Адамара) псевдобулевой функции.

  35. Криптографические характеристики булевой функции: алгебраическая степень и нелинейность.

  36. Криптографические характеристики булевой функции: нелинейность порядка r и сбалансированность.

  37. Криптографическая характеристика булевой функции: отсутствие ненулевой линейной структуры.

  38. Многозначные логики. Основные типы: Лукашевича, Геделя, t-норм система, трехзначная, четырехзначная система Данна-Беллнапа, система произведения.

  39. Функция k-значной логики. Отношение эквивалентности на множестве функций k-значной логики. Циклический полином. Лемма Бернсайда.

  40. Теоремы де Брюина и Полиа для классов функций k-значной логики.

  41. Понятие алгоритма и вычислимой функции. Примитивно и частично рекурсивные функции.

  42. Тезис Черча. Машина Тьюринга-Поста.

  43. Вычисления функций на машине Тьюринга-Поста. Универсальная машина Тьюринга.

  44. Теорема об универсальном алгоритме.

  45. Эффективные алгоритмы. Алгоритмически неразрешимые проблемы.

  46. Сложность алгоритма. Оценки функции сложности.

  47. Сложность арифметических операций.

  48. Классы задач P и NP. Тезис Колмогорова.

  49. Реляционная алгебра, реляционное исчисление, понятие реляционной схемы, его характеристики.

  50. Операции реляционной алгебры. Базы данных.

Похожие:

Программа дисциплины математическая логика и теория алгоритмов iconРабочая программа дисциплины Математическая логика и теория алгоритмов Направление
Целями освоения дисциплины «Математическая логика и теория алгоритмов» являются получение теоретических знаний по основам математическая...
Программа дисциплины математическая логика и теория алгоритмов iconРабочая программа по дисциплине в 2-Математическая логика и теория алгоритмов
Математическая логика и теория алгоритмов в соответствии требованиями фгос впо, утвержденного приказом Министра образования и науки...
Программа дисциплины математическая логика и теория алгоритмов icon«Математическая логика и теория алгоритмов»
Математическая логика и теория алгоритмов" является фундаментальное образование в области принципов построения эффективных и надежных...
Программа дисциплины математическая логика и теория алгоритмов iconУльянов М. В., Шептунов М. В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов
Ульянов М. В., Шептунов М. В. Математическая логика и теория алгоритмов, часть 2: Теория алгоритмов. – М.: Мгапи, 2003. – 80 с
Программа дисциплины математическая логика и теория алгоритмов iconМатематическая логика и теория алгоритмов

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

Программа дисциплины математическая логика и теория алгоритмов iconПрограмма дисциплины по кафедре Прикладная математика и информатика математическая логика и теория алгоритмов
Утверждена научно-методическим советом университета для направлений подготовки (специальностей) в области информатики и вычислительной...
Программа дисциплины математическая логика и теория алгоритмов iconМинистерство образования и науки российской федерации государственное образовательное учреждение высшего профессионального образования
Цель дисциплины «Математическая логика и теория алгоритмов» – формирование систематизированных знаний в области математической логики...
Программа дисциплины математическая логика и теория алгоритмов iconПрограмма наименование дисциплины: Математическая логика и теория алгоритмов
Для достижения поставленной цели выделяются задачи курса: освоение теории множеств, навыки работы с пропозициональными и предикатными...
Программа дисциплины математическая логика и теория алгоритмов iconПрограмма наименование дисциплины: Математическая логика и теория алгоритмов
Для достижения поставленной цели выделяются задачи курса: освоение теории множеств, навыки работы с пропозициональными и предикатными...
Разместите кнопку на своём сайте:
Библиотека


База данных защищена авторским правом ©lib.znate.ru 2014
обратиться к администрации
Библиотека
Главная страница