rpd000006219 (230100 (09.03.01).Б11 Вычислительные машины, комплексы и сети), страница 2

Тематика:

Трудоемкость(СРС): 9

Прикрепленные файлы: теоретические задания к курсовой работе.doc

Типовые варианты:

1. Рубежный контроль

1. Промежуточная аттестация

1. Экзамен

Прикрепленные файлы:

Вопросы для подготовки к экзамену/зачету:

1.Понятия «логика» и «интуиция». Интуиция-суждение, интуиция-догадка,

2.История развития логики. Математическая логика и современные компьютеры

3.Высказывания и высказывательные формы. Элементарные и составные предложения. Логические связки. Определения, примеры.

4.Конъюнкция и дизъюнкция. Определения. Свойства. Таблицы истинности. Примеры.

5.Отрицание. Импликация и эквиваленция. Определения. Свойства. Таблицы истинности. Примеры.

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

7.Язык и метаязык.

8.Составление таблиц истинности для данных формул. Тавтологии

9.Равносильность формул логики высказываний. Законы логики.

10.Отношение следования между формулами логики высказываний. Правильные и неправильные аргументы.

11.Составление формул по заданным таблицам истинности

12.Нормальные формы. Приведение формул к совершенным нормальным формам с помощью равносильных преобразований.

13.Переключательные схемы. Описание переключательных схем с помощью формул логики высказываний.

14.Понятие предиката. Кванторы. Понятия, определения, примеры.

15.Формулы логики предикатов. Понятия, определения, примеры.

16.Свойства формул логики предикатов в данной интерпретации.

17.Логически общезначимые формулы логики предикатов. Выполнимые и равносильные формулы.

18.Клаузальная форма формул логики предикатов. Преобразование формул логики предикатов в клаузальную форму.

19.Неклассические логики. Трехзначные логики Лукасевича, Гейтинга, Рейхенбаха, Бочвара и Клини.

20.Понятие нечеткого множества.

21.Нечеткие высказывания и максиминные операции над ними.

22.Неклассические логики. Модальные логики.

23. Неклассические логики. Временные (темпоральные) логики.

24.Алгоритмические логики.

25.Интуитивное представление об алгоритмах. Неформальное понятие алгоритма.

26.Машины Тьюринга. Применение машин Тьюринга к словам. Тезис Тьюринга (основная гипотеза теории алгоритмов).

27.Основные понятия теории рекурсивных функций и тезис Чёрча.

28.Нормальные алгоритмы Маркова. Марковские подстановки. Нормальные алгоритмы и их применение к словам.

29.Проблема алгоритмической неразрешимости. Примеры алгоритмически неразрешимых массовых проблем.

30.Сложность вычислений с помощью алгоритмов. Понятие о сложности. Временная сложность вычислений (алгоритма). Классы Р, NP.

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

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

1. Лихтарников Л.М. Математическая логика. Курс лекций. Задачник – практикум и решения: Учебное пособие. 4-е изд., стер.- СПб.: Издательство «Лань», 2009.- 288 с.

2. Зюзьков В.М., Шелупанов А.А. Математическая логика и теория алгоритмов: Учебное пособие для вузов._ 2-е изд.- М.: Горячая линия-Телеком, 2007.- 176 с.

3. Глухов М.М., Козлитин О.А., Шапошников В.А., Шишков А.Б. Задачи и упражнения по математической логике, дискретным функциям и теории алгоритмов: Учебное пособие.- СПб.: Издательство «Лань», 2008.- 112 с.

4. Математическая логика и теория алгоритмов: учебное пособие для студ. высш. учеб. заведений/ В.И. Игошин.- 4-е изд., стер.- М.: Издательский центр «Академия», 2010.-448 с.

5. Математическая логика и теория алгоритмов для программистов: учебное пособие/ Д.В. Гринченков, С.И. Птоцкий.-М.: КНОРУС, 2010.-208 с.

6. А.В. Гохман, М.А. Спивак, В.В. Розен и др. Сборник задач по математической логике и алгебре множеств. Издательство Саратовского университета. 1969

7. Галиев Ш.И. Математическая логика и теория алгоритмов.-Казань: издательство КГТУ им. А.Н. Туполева. 2002.

8. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов : учеб. пособие для студ. высш. учеб. заведений / В.И.Игошин. — 3-е изд., стер. — М. : Издательский центр «Академия», 2007. — 304 с.

б)дополнительная литература:

в)программное обеспечение, Интернет-ресурсы, электронные библиотечные системы:

1. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

Аудитория, доска, мел

Приложение 1
к рабочей программе дисциплины
«Математическая логика и теория алгоритмов »

Аннотация рабочей программы

Дисциплина Математическая логика и теория алгоритмов является частью Математического и естественно-научный цикл дисциплин подготовки студентов по направлению подготовки Информатика и вычислительная техника. Дисциплина реализуется на «Восход» факультете «Московского авиационного института (национального исследовательского университета)» кафедрой (кафедрами) Б21.

Дисциплина нацелена на формирование следующих компетенций: ПКП-9.

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

Преподавание дисциплины предусматривает следующие формы организации учебного процесса: Лекция, мастер-класс, Практическое занятие, Лабораторная работа.

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

Общая трудоемкость освоения дисциплины составляет 4 зачетных единиц, 144 часов. Программой дисциплины предусмотрены лекционные (34 часов), практические (18 часов), лабораторные (16 часов) занятия и (49 часов) самостоятельной работы студента. Дисциплина «Математическая логика и теория алгоритмов» является частью математического и естественно-научного цикла дисциплин подготовки студентов по направлению подготовки 230100 «Информатика и вычислительная техника». Дисциплина реализуется в филиале «Восход» МАИ кафедрой Б22. Преподавание дисциплины предусматривает следующие формы организации учебного процесса: лекции, лабораторные работы, курсовую работу, самостоятельную работу студентов, консультации

Приложение 2
к рабочей программе дисциплины
«Математическая логика и теория алгоритмов »

Cодержание учебных занятий

1. Лекции

1.1.1. Основные понятия логики. (АЗ: 2, СРС: 1)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Логика и интуиция. Интуиция-суждение. Интуиция-догадка. История развития математической логики. Математическая логика и современные ЭВМ.

1.1.2. Семантика логики высказываний. (АЗ: 2, СРС: 1)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Высказывания и высказывательные формы. Элементарные и составные предложения. Конъюнкция и дизъюнкция. Отрицание. Импликация и эквиваленция.

1.1.3. Синтаксис логики высказываний. (АЗ: 4, СРС: 1)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Формулы логики высказываний. Язык и метаязык. Составление таблиц истинности для данных формул. Тавтологии. Логическая равносильность. Равносильность формул логики высказываний. Законы логики.

1.1.4. Логическое следование. Нормальные формы. Переключательные схемы (АЗ: 4, СРС: 1)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Логическое следование. Отношение следования между формулами логики высказываний. Правильные и неправильные аргументы. Нормальные формы. Составление формул по заданным таблицам истинности. Приведение формул к совершенным нормальным формам с помощью равносильных преобразований. Переключательные схемы. Описание переключательных схем с помощью формул логики высказываний.

1.2.1. Семантика логики предикатов. (АЗ: 2, СРС: 1)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Понятие предиката. Кванторы. Квантор всеобщности. Квантор существования.

1.2.2. Синтаксис логики предикатов. (АЗ: 2, СРС: 1)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Формулы логики предикатов. Интерпретация. Модель. Свойства формул в данной интерпретации. Логически общезначимые формулы. Выполнимые и равносильные формулы.

1.3.1. Неклассические логики. (АЗ: 6, СРС: 1)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Трехзначные логики. Трёхзначная логика Лукасевича. Трёхзначная логика Гейтинга. Трёхзначные логики Рейхенбаха, Бочвара и Клини. Многозначные логики. Понятие нечеткого множества. Нечеткие высказывания и максиминные операции над ними. Понятие о нечеткой лингвистической логике. Модальные логики. Временные (темпоральные) логики. Алгоритмические логики.

1.4.1. Понятие алгоритма. (АЗ: 2, СРС: 1)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Интуитивное представление об алгоритмах. Неформальное понятие алгоритма.

1.4.2. Машина Тьюринга. (АЗ: 2, СРС: 1)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Определение машины Тьюринга. Применение машин Тьюринга к словам. Конструирование машин Тьюринга. Тезис Тьюринга. Машины Тьюринга и современные электронно - вычислительные машины.

1.4.3. Рекурсивные функции (АЗ: 2, СРС: 1)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

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

1.4.4. Проблема алгоритмической неразрешимости (АЗ: 2, СРС: 1)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Массовые проблемы. Проблема алгоритмической (не)разрешимости. Примеры алгоритмически неразрешимых массовых проблем. Проблема эквивалентности слов. Проблема представимости матриц. Проблема неразрешимости логики предикатов. Проблема остановки.

1.4.5. Сложность вычислений с помощью алгоритмов (АЗ: 4, СРС: 1)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Понятие о сложности. Временная сложность вычислений (алгоритма). Полиномиальные алгоритмы и задачи. Класс Р. NP класс.

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

1.1.1. Высказывания и высказывательные формы. Элементарные и составные предложения. Конъюнкция и дизъюнкция. Отрицание. Импликация и эквиваленция(АЗ: 2, СРС: 2)

Форма организации: Практическое занятие

1.1.2. Формулы логики высказываний. Составление таблиц истинности для данных формул. Тавтологии. Логическая равносильность. Равносильность формул логики выск(АЗ: 4, СРС: 2)