Рабочая учебная программа по дисциплине конспект лекций по дисциплине - umotnas.ru o_O
Главная
Поиск по ключевым словам:
страница 1страница 2 ... страница 6страница 7
Похожие работы
Название работы Кол-во страниц Размер
Рабочая учебная программа по дисциплине конспект лекций по дисциплине 3 708.63kb.
Рабочая учебная программа по дисциплине конспект лекций по дисциплине 9 2762.57kb.
Рабочая учебная программа по дисциплине конспект лекций по дисциплине 4 1539.61kb.
Рабочая учебная программа по дисциплине конспект лекций по дисциплине 4 1526.27kb.
Рабочая учебная программа по дисциплине конспект лекций по дисциплине 5 1826.22kb.
Рабочая учебная программа по дисциплине конспект лекций по дисциплине 2 499.95kb.
Рабочая учебная программа по дисциплине конспект лекций по дисциплине 2 486.97kb.
Рабочая учебная программа по дисциплине конспект лекций по дисциплине 4 1144.59kb.
Конспект лекций по данной дисциплине. Основное назначение содействие... 8 1145.85kb.
Рабочая учебная программа по дисциплине «Теория и практика перевода» 1 181.34kb.
Рабочая учебная программа по дисциплине теория машин и механизмов 1 175.1kb.
Теория вычислительных процессов 6 2338.76kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Рабочая учебная программа по дисциплине конспект лекций по дисциплине - страница №1/7




Автор-составитель:



Годяева Анна Евгеньевна, ст. преподаватель

Учебно-методический комплекс по дисциплине Математическая логика и теория алгоритмов расчетах составлен в соответствии с требованиями Государственного образовательного стандарта высшего профессионального образования и на основании примерной учебной программы данной дисциплины в соответствии с государственными требованиями к минимуму содержания и уровню подготовки инженера по специальности 230101.65 Вычислительные машины, комплексы, системы и сети. Дисциплина входит в федеральный компонент цикла общих математических и естественнонаучных дисциплин специальности и является обязательной для изучения. Данный учебно-методический комплекс рассмотрен и одобрен на заседании Учебно-методической комиссии РОАТ. Протокол №4 от 01.07.2011.




Содержание



Рабочая учебная программа по дисциплине ……………………………………

4

Конспект лекций по дисциплине ………………………………………………..

9

Задание на контрольную работу и общие указания к выполнению контрольной работы ……………………………………………………................

69

Методические указания студентам …………………………………………….

72

Методические указания преподавателям ………………………………………

73

Вопросы к экзамену по дисциплине ……………………………………………

74

Экзаменационные билеты ………………………………………………………

76





1. ЦЕЛЬ И ЗАДАЧИ ДИСЦИПЛИНЫ
Целью дисциплины «Математическая логика и теория алгоритмов» является изучение указанных в рабочей программе глав этой дисциплины, необходимых при изучении дисциплин, входящих в учебный план по специальности 230101.65, вычислительные машины, комплексы, системы и сети.

Изучение математической логики и алгоритмов способствует развитию логического и алгоритмического мышления студентов, освоению ими приемов исследования и решения математически формализованных задач, выработке умения применять полученные знания при формализации и решении прикладных задач на ЭВМ.


2. ТРЕБОВАНИЯ К УРОВНЮ ОСВОЕНИЯ ДИСЦИПЛИНЫ

Изучив дисциплину, студент должен:

2.1. Знать базовые понятия дискретной математики.

2.2. Владеть основами математической логики и теории алгоритмов.

2.3. Уметь решать типовые задачи.

2.4. Иметь представление об использовании полученных знаний при решении инженерных задач.


3. ОБЪЕМ ДИСЦИПЛИНЫ И ВИДЫ УЧЕБНОЙ РАБОТЫ


Вид учебной работы

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

1. Курс

2

2. Аудиторные занятия

12

2.1. Лекции

4

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

8

2.3. Лабораторный практикум

0

2.4. Индивидуальные занятия

0

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

88

4. ВСЕГО ЧАСОВ НА ДИСЦИПЛИНУ

100

5. Вид и количество текущего контроля

Контр.раб.

№1 (одна)



6. Виды промежуточного контроля

Экзамен

4. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
4.1. РАЗДЕЛЫ ДИСЦИПЛИНЫ И ВИДЫ ЗАНЯТИЙ


Раздел


Лекции,

час.


Практические

занятия,


час.

1

Элементы классической математической логики

2

2

2

Элементы неклассических математических логик




4

3

Элементы теории алгоритмов

2

2

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


1. Элементы классической математической логики. Предмет классической математической логики. Предмет логики высказываний. Логические операции над высказываниями. Понятие формулы алгебры высказываний. Равносильность и классификация формул. Логические эквивалентности. Определение булевой алгебры. Примеры. Законы булевой алгебры. Переключательные функции (ПФ). Определение различных типов ПФ. Полностью и не полностью определенные ПФ. Способы задания ПФ.

Специальные разложения ПФ. Минимизация ПФ. Теорема о функциональной полноте. Примеры функционально полных базисов. Моделирование алгебры высказываний релейно-контактными схемами. Задачи анализа и синтеза. Алгебра предикатов. Кванторы. Применение нормальных форм в программировании. Примеры формальных (аксиоматических) систем. Исчисление высказываний. Исчисление предикатов. Непротиворечивость полнота.


2. Элементы неклассических математических логик. Предмет неклассических логик. Нечеткая логика. Нечеткие высказывания. Правила преобразования нечетких высказываний. Характеристическая функция нечеткого подмножества. Функции нечетких переменных. Таблица значений функции нечетких переменных. Равносильность двух функций нечетких переменных. Полиномиальные формы. Логическая структура функций нечетких переменных. Сети нечетких элементов. Сети нечетких элементов. Модальная логика. Логические операции в модальной логике высказываний. Понятие формулы модальной алгебры высказываний. Модальная логика предикатов. Терморальная логика. Алгоритмическая логика Хоара. Формальные (аксиоматические) системы. Языки и грамматики формальных неклассических систем.
3. Элементы теории алгоритмов. Интуитивное понятие алгоритма и его свойства. Понятие о четком (обычном) и нечетком алгоритме. Формализация понятия четкого алгоритма. Рекурсивные функции. Понятие о примитивно-рекурсивной функции. Функции, вычисляемые на машинах Тьюринга, нормальные алгоритмы Маркова. Тезис Черча. Эффективные алгоритмы Разрешимые и неразрешимые проблемы. Понятие сложности вычислений. Схемы алгоритмов. Схемы потоков данных.
4.4. ПРАКТИЧЕСКИЕ ЗАНЯТИЯ


Темы

Часы

Элементы классической математической логики.

Логика предикатов. Решение типовых задач



2

Понятие о формальных (аксиоматических) системах.

Понятие о неклассической логике. Элементы нечеткой логики.



2

Решение типовых задач по нечеткой логике

2

Решение типовых задач по теории алгоритмов

2



5. САМОСТОЯТЕЛЬНАЯ РАБОТА
Предусматривается выполнение одной контрольной работы, состоящей из 4 задач.

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

Основная литература

1. Аляев Ю.А. Дискретная математика и математическая логика: учебник. – М.: Финансы и статистика, 2006.


2.Игошин В.И. Математическая логика и теория алгоритмов: учебное пособие для студентов вузов. - М.: Издательский центр Академия, 2008.
3. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов: учебное пособие для студентов вузов. - М.: Издательский центр Академия, 2008.
4. Шевелев Ю.П. Математическая логика и теория алгоритмов: Учебное пособие/.- Балт. гос. техн. ун-т.- СПб, 20004.
5. Шапорев С.А. Математическая логика и теория алгоритмов: Учебное пособие .- Томск, Дельтаплан, 2007.
6. Шестаков А.А. и др. Дискретная математика. Элементы нечеткой логики: Учебное пособие/ Под ред. А.А.Шестакова.- М.: РГОТУПС, 2004.
7. Шестаков А.А. , Дружинина О.В. Дискретная математика. Элементы нечеткой логики: Учебное пособие- М.: РГОТУПС, 2004.
8.Гаврилов Г.Н., Сапоженко А.А. Задачи и упражнения по курсу дискретной математики. – М.: Наука, 2007.
9.Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов.- М.: Физматлит, 2005.

Дополнительная литература

10.Яблонский С.В.Введение в дискретную математику.- М.: Лань, 2009.


11.Кофман А.Введение в теорию нечетких множеств. М.: ФИЗМАТЛИТ,2007.
12.Успенский В.А., Верещагин Н.К., Плиско В.Е. Вводный курс математической логики.- М.: ФИЗМАТЛИЗ, 2004.
13. Тимофеева И.Л. Математической логика. Курс лекций: Учеб. пособие для студентов вузов – М.:КДУ,2007.
14. Закревский А.Д., Поттосин Ю.В., Черемисинова Л.Д. Логические основы проектирования дискретных устройств.- М.: ФИЗМАТЛИТ, 2007.

Конспект лекций

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

1.1 Различные подходы к определению алгоритма:

10. Неформальное понятие алгоритма (последовательность инструкций для выполнения действия).

20. Машина с неограниченными регистрами (МНР).

30 Машина Тьюринга – Поста (МТ-П).

40 Нормальные алгоритмы Маркова (НАМ).
1.1.1 Машина с неограниченными регистрами (МНР).

Имеется некое устройство, в котором счетное число ячеек памяти (регистров), в которых хранятся целые числа.

Допустимые команды:

Z(n) - обнуление регистра Rn.

S(n) - увеличение числа в регистре Rn на 1.

T(m,n) - копирует содержимое Rm в регистор Rn.

I(p,q,n) - если содержимое Rp = Rq то выполняется команда с номером n , если нет

следующая.

Программа для МНР должна быть последовательностью команд Z, S, T, I с определенным порядком, выполняемые последовательно.
Тезис Черча (Churcha): Первое и второе определение алгоритма эквивалентны между собой. Любой неформальный алгоритм может быть представлен в программе для МНР.
1.1.2 Машина Тьюринга - Поста.

Имеется устройство просматривающее бесконечную ленту, где есть ячейки содержащие элементы алфавита: , где - пустой символ (пустое слово), который может принадлежать и не принадлежать А. Также существует управляющая головка (устройство) (УУ)/(УГ), которая в начальный момент расположена в определенном месте, в состоянии . Также существуют внутренние состояния машины:



Слово в данном алфавите - любая конечная упорядоченная последовательность букв данного алфавита, притом длина слова это количество букв в нем (у пустого слова длина 0).

Допустимые команды:



1) ,где .

2) (остановка программы).



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


1.1.3 Нормальные алгоритмы Маркова.

Тип машины перерабатывающий слова, в которой существует некий алфавит , для которого W - множество всех слов.

Допустимые команды: (Для машин этого типа важна последовательность команд.)


где

Пример:

Программа:




1.1.4 Реализация функции натурального переменного.

но мы допускаем не всюду определенную функцию.

то это означает, что

притом , если f не определена, то и программа не должна ничего выдавать.



притом , если f не определена, то и программа не должна ничего выдавать.

( , а числа представляются в виде ,например .)

1.2 Эквивалентность трех подходов к понятию алгоритм.
1.2.1 Теорема об эквивалентности понятия вычислимой функции.

вычислима: ()


  1. Если существует программа МНР, которая вычисляет эту функцию.

  2. Если существует программа МТ-П, которая вычисляет эту функцию.

  3. Если существует программа НАМ, которая вычисляет эту функцию.

Использование НАМ:




Теор.: Классы функций вычислимых на МТ-П, с помощью НАМ и с помощью МНР совпадают.

Пусть которая вычисляется на МТ-П, вычислим её на НАМ.


следующая страница >>