МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ
федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
«Алтайский государственный университет»
Рубцовский институт (филиал)
УЧЕБНО-МЕТОДИЧЕСКИЙ КОМПЛЕКС ПО ДИСЦИПЛИНЕ
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ
Специальность - 230101.65 Вычислительные машины, комплексы, системы и сети
Форма обучения – очная
Кафедра – Математики и прикладной информатики
Рубцовск - 2011
СОДЕРЖАНИЕ
1. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА. 5
2. ТЕМАТИЧЕСКИЙ ПЛАН.. 6
3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ.. 10
4. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ.. 22
5. СПИСОК ОСНОВНОЙ И ДОПОЛНИТЕЛЬНОЙ ЛИТЕРАТУРЫ, ДРУГИЕ ИНФОРМАЦИОННЫЕ ИСТОЧНИКИ 23
1. ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
Курс математическая логика и теория алгоритмов обеспечивает приобретение знаний в соответствии с государственным образовательным стандартом, содействует фундаментализации образования и развитию логического мышления.
Цели освоения дисциплины:
Основной целью дисциплины «Математическая логика и теория алгоритмов» является изучение основных понятий и методов математической логики и теории алгоритмов, используемые в информатике и вычислительной технике; приобретение умений использования их для построения несложных логических моделей предметных областей, реализации логического вывода и оценки вычислительной сложности алгоритмов; получение представление о направлениях развития данной дисциплины и перспективах ее использования в информатике и вычислительной технике.
Задачи дисциплины:
– дать основы знаний по каждому разделу математической логике и теории алгоритмов и закрепить эти знания во взаимосвязи с другими дисциплинами и курсами, на которые опирается математическая логика и теория алгоритмов и для которых она служит теоретическим «фундаментом»;
– привить общие навыки решения конкретных задач по основным разделам математической логики и теории алгоритмов;
– получить общее представление о приложениях математической логики и теории алгоритмов, как теоретических так и технических.
Дисциплина «Математическая логика и теория алгоритмов» относится к циклу ЕН. Ф.01.04. Цикл общие математические и естественнонаучные дисциплины. Федеральный компонент.
Перечень дисциплин, усвоение которых студентами необходимо для изучения данного курса:
«Математический анализ», «Линейная алгебра и геометрия», «Информатика». Знания и навыки, полученные при изучении дисциплины «Математическая логика и теория алгоритмов», используются при изучении общепрофессиональных и специальных дисциплин.
Программа предусматривает различные формы работы со студентами: проведение лекционных, семинарских занятий, индивидуальных домашних и зачетных работ.
2. ТЕМАТИЧЕСКИЙ ПЛАН
(распределение часов курса по разделам и видам работ)
Очная форма обучения
Дидактические единицы (ДЕ) | Наименование тем | Максимальная нагрузка студентов, час. | Количество аудиторных часов при очной форме обучения | Самостоятельная работа студентов, час. | ||
Лекции | Семинары | Лабораторные работы | ||||
1 | 2 | 3 | 4 | 5 | 6 | 7 |
ДЕ 1 Логика высказываний и огика предикатов (50 баллов) | 1.Математическая логика и ее применение. Понятие высказывания. Логические операции. Формулы логики высказываний. Таблицы истинности. Приоритет логических операций. Тавтология, противоречие, выполнимая формула. Проблема разрешимости. Равносильные формулы. Критерий равносильности. Основные равносильности логики высказываний | 8 | 2 | 2 | 4 | |
2. .Нормальные формы формул логики высказываний. Понятие элементарной дизъюнкции, элементарной конъюнкции. Дизъюнктивная и конъюнктивная нормальные формы. Совершенные дизъюнктивные и конъюнктивные нормальные формы (СДНФ, СКНФ). Единственность представления в СКНФ (СДНФ). | 12 | 2 | 4 | 6 | ||
3. Понятие логического следования, критерий логического следования. Схема логического рассуждения и правильность логического рассуждения. Способы проверки правильности логических рассуждений. Прямые и косвенные виды доказательств. | 8 | 2 | 2 | 4 | ||
4. Булевы функции. Понятие булевой функции. Число булевых функций. Булевы функции формулы логики высказываний. Полные системы булевых функций. Специальные классы булевых функций. Теорема Поста о полноте системы булевых функций. Применение булевых функций к релейно-контактным схемам. Формализованное исчисление высказываний. Аксиоматические системы, формальный вывод. | 10 | 2 | 2 | 6 | ||
5. Логика предикатов. Понятие предиката. Классификация предикатов. Множество истинности предиката. Логические операции над предикатами. Кванторные операции. Синтаксис и семантика языка логики предикатов. Формулы логики предикатов. Равносильные формулы логики предикатов. Предваренная нормальная форма. Клаузальная форма. Метод резолюций в логике предикатов. Принцип логического программирования. Формализация исчисления логики предикатов. | 6 | 2 | 2 | 2 | ||
6. Метатеория формальных систем. Понятие алгоритмической системы. | 6 | 2 | 4 | |||
Промежуточный контроль | Контрольная работа (25 баллов) Индивидуальная домашняя работа (25 баллов) | |||||
ДЕ 2 (50 баллов) | 7. Теория алгоритмов. Определение алгоритма. Характерные черты алгоритма. Формализация понятия алгоритма. | 8 | 2 | 2 | 4 | |
8. Определение машины Тьюринга. Тезис Тьюринга. Машины Тьюринга и современные электронно-вычислительные машины | 12 | 4 | 4 | 4 | ||
9. Рекурсивные функции и тезис Чёрча. | 8 | 2 | 2 | 4 | ||
10. . Нормальный алгоритм Маркова. | 8 | 2 | 2 | 4 | ||
11. Алгоритмически неразрешимые проблемы. Меры сложности алгоритмов. Легко и трудноразрешимые задачи. Классы задач P и NP. NP – полные задачи. Понятие сложности вычислений; эффективные алгоритмы. | 7 | 2 | 1 | 4 | ||
12. Неклассические логики. Темпоральные логики; нечеткая и модальные логики; нечеткая арифметика; алгоритмическая логика Ч. Хоара. Основы нечеткой логики. Элементы алгоритмической логики. | 7 | 2 | 1 | 4 | ||
Промежуточный контроль | Контрольная работа (25 баллов) Зачетная работа (25 баллов) | |||||
Итоговый контроль | Экзамен – 40 баллов | |||||
Итого часов | 100 | 26 | 24 | 50 | ||
3. СОДЕРЖАНИЕ ДИСЦИПЛИНЫ
(дидактические единицы)
3.1 Обязательный минимум содержания образовательной программы
Математическая логика и теория алгоритмов. Логика высказываний; логика предикатов; исчисления; непротиворечивость; полнота; синтаксис и семантика языка логики предикатов. Клаузальная форма. Метод резолюций в логике предикатов. Принцип логического программирования. Темпоральные логики; нечеткая и модальные логики; нечеткая арифметика; алгоритмическая логика Ч. Хоара. Логика высказываний. Логическое следование, принцип дедукции. Метод резолюций. Аксиоматические системы, формальный вывод. Метатеория формальных систем. Понятие алгоритмической системы. Рекурсивные функции. Формализация понятия алгоритма; Машина Тьюринга. Тезис Черча. Алгоритмически неразрешимые проблемы. Меры сложности алгоритмов. Легко и трудноразрешимые задачи. Классы задач P и NP. NP – полные задачи. Понятие сложности вычислений; эффективные алгоритмы. Основы нечеткой логики. Элементы алгоритмической логики.
3.2 Содержание разделов учебной дисциплины
ДЕ 1 Логика высказываний
Тема 1. . Математическая логика. Алгебра высказываний
Аудиторное изучение: Математическая логика. Логика и интуиция. Логика традиционная и математическая логика. Понятие высказывания. Логические операции. Формулы логики высказываний. Таблицы истинности. Приоритет логических операций. Тавтология, противоречие, выполнимая формула. Проблема разрешимости. Равносильные формулы. Критерий равносильности. Основные равносильности логики высказываний.
Самостоятельное изучение: Математическая логика и современные ЭВМ.
Тема 2. Нормальные формы для формул алгебры высказываний
Аудиторное изучение: Нормальные формы формул логики высказываний. Понятие элементарной дизъюнкции, элементарной конъюнкции. Дизъюнктивная и конъюнктивная нормальные формы. Совершенные дизъюнктивные и конъюнктивные нормальные формы (СДНФ, СКНФ). Единственность представления в СКНФ (СДНФ).
Самостоятельное изучение: Приложение алгебры высказываний к логико-математической практике.
Тема 3. Понятие логического следования
Аудиторное изучение: Понятие логического следования, критерий логического следования. Схема логического рассуждения и правильность логического рассуждения. Способы проверки правильности логических рассуждений.
Самостоятельное изучение: Прямые и косвенные виды доказательств.
Тема 4. Булевы функции
Аудиторное изучение: .Булевы функции. Понятие булевой функции. Число булевых функций. Булевы функции формулы логики высказываний. Полные системы булевых функций. Специальные классы булевых функций. Теорема Поста о полноте системы булевых функций. Формализованное исчисление высказываний. Аксиоматические системы, формальный вывод. Принцип дедукции. Полнота, непротиворечивость, разрешимость.
Самостоятельное изучение: Применение булевых функций к релейно-контактным схемам.
Тема 5. Логика предикатов
Аудиторное изучение: Логика предикатов. Понятие предиката. Классификация предикатов. Множество истинности предиката. Логические операции над предикатами. Кванторные операции. Синтаксис и семантика языка логики предикатов. Формулы логики предикатов. Равносильные формулы логики предикатов. Предваренная нормальная форма. Клаузальная форма. Метод резолюций в логике предикатов. Принцип логического программирования.
Самостоятельное изучение: Формализация исчисления логики предикатов.
Тема 6. Метатеория формальных систем.
Аудиторное изучение: Метатеория формальных систем. Понятие алгоритмической системы.
Самостоятельное изучение: Формализация исчисления логики предикатов.
ДЕ 2.
Тема 7. Теория алгоритмов
Аудиторное изучение: Теория алгоритмов. Определение алгоритма. Характерные черты алгоритма. Необходимость уточнения алгоритма.
Самостоятельное изучение: Подход Геделя - Клини к формализации понятия алгоритма.
Тема 8. Машины Тьюринга
Аудиторное изучение: Определение машины Тьюринга. Тезис Тьюринга. Машины Тьюринга и современные электронно-вычислительные машины
Самостоятельное изучение: Композиция машин Тьюринга.
Тема 9. Рекурсивные функции
Аудиторное изучение: Происхождение рекурсивных функций. Основные понятия теории рекурсивных функций и тезис Чёрча. Примитивно рекурсивные функции. Примитивная рекурсивность предикатов. Вычислимость по Тьюрингу примитивно рекурсивных функций. Функции Аккермана. Оператор минимизации. Общерекурсивные и частично рекурсивные функции. Самостоятельное изучение: Вычислимость по Тьюрингу частично рекурсивных функций. Частичная рекурсивность функций, вычислимых по Тьюрингу.
Тема 10. Нормальный алгоритм Маркова
Аудиторное изучение: Марковские подстановки. Нормальные алгоритмы и их применение к словам.
Самостоятельное изучение: Нормально вычислимые функции.
Тема11. Алгоритмически неразрешимые проблемы
Аудиторное изучение: Алгоритмически неразрешимые проблемы. Меры сложности алгоритмов. Легко и трудноразрешимые задачи. Классы задач P и NP. NP – полные задачи.
Самостоятельное изучение: Понятие сложности вычислений; эффективные алгоритмы.
Тема 12. Неклассические логики
Аудиторное изучение: Неклассические логики. Темпоральные логики, нечеткая и модальные логики, нечеткая арифметика. Основы нечеткой логики. Элементы алгоритмической логики.
Самостоятельное изучение: Алгоритмическая логика Ч. Хоара.
3.3 Содержание лабораторных занятий (практических занятий)
Тема 1. Алгебра высказываний Высказывания и операции над ними.
Семинарское занятие – 2 часа.
План.
1. Алгебра высказываний Высказывания и операции над ними.
2. Формулы алгебры высказываний.
3. Тавтологии алгебры высказываний.
4. Логическая равносильность формул.
5. Нормальные формы для формул алгебры высказываний.
6. Логическое следование формул.
Тема 2. Нормальные формы формул логики высказываний.
Семинарское занятие –4 часа
План.
1. Элементарная дизъюнкция, э конъюнкция
2. Дизъюнктивная и конъюнктивная нормальные формы.
3. Совершенные дизъюнктивные и конъюнктивные нормальные формы (СДНФ, СКНФ).
Тема 3. Понятие логического следования.
Семинарское занятие –2 часа
План.
1. Понятие логического следования, критерий логического следования.
2. Схема логического рассуждения и правильность логического рассуждения. Способы проверки правильности логических рассуждений.
3. Прямые и косвенные виды доказательств.
4. Решение задач.
Тема 4. Булевы функции.
Семинарское занятие –2 часа
План.
1. Булевы функции от одного и двух аргументов.
2. Булевы функции от n аргументов.
3. Системы булевых функций.
4. Применение булевых функций к релейно-контактным схемам.
Тема 5. Логика предикатов.
Семинарское занятие - 4 часа.
План.
Формализованное исчисление предикатов.
1. Логика предикатов. Понятие предиката.
2. Классификация предикатов. Множество истинности предиката.
3. Логические операции над предикатами.
4. Кванторные операции.
5. Формулы логики предикатов.
6. Равносильные формулы логики предикатов.
7. Предваренная нормальная форма.
8. Формализация в логике предикатов.
Тема 7. Алгоритм, основные свойства.
Семинарское занятие – 2 часа..
План.
1. Понятие алгоритма и неформальной вычислимости: определения и основные особенности алгоритма.
2. Подход Геделя - Клини к формализации понятия алгоритма.
3. Решение задач.
Тема 8. Машины Тьюринга.
Семинарское занятие – 2 часа.
План.
1. Определение машины Тьюринга.
2. Конструирование машин Тьюринга. Частные производные.
3. Композиция машин Тьюринга. Частные производные высших порядков.
.
Тема 9. Рекурсивные функции.
Семинарское занятие – 2 часа.
План.
1. Основные понятия теории рекурсивных функций и тезис Чёрча.
2. Общерекурсивные и частично рекурсивные функции.
3. Вычислимость по Тьюрингу частично рекурсивных функций. Частичная рекурсивность функций, вычислимых по Тьюрингу
4. Нормальный алгоритм Маркова.
Тема 11, 12. Алгоритмически неразрешимые проблемы. Сложность алгоритмов. Неклассические логики.
Семинарское занятие – 2 часа.
План.
1. Алгоритмически неразрешимые проблемы. Сложность алгоритмов: в наихудшем случае и поведения в среднем.
2. Сложность задачи. Классификация задач по сложности: класс Р и класс Е. Класс NP. NP-трудные и NP-полные задачи.
3. Теорема Кука.
4. Неклассические логики.
5. Предикатные логики и их приложения к программированию.
6. Алгоритмические логики.
7. Контрольная работа.
Материалы к промежуточному и итоговому контролю.
Контрольная работа 1
1. Пусть значение высказывания 
истинное. Что можно сказать о значениях высказывания 
2. С помощью истинностных таблиц проверьте, являются ли эквивалентными формулы A и B. A=
3. С помощью таблицы истинности и эквивалентных преобразований привести формулу к ДНФ, КНФ, СКНФ и СДНФ.
Контрольная работа 2
Является ли тождественно-истинными формулы:
; 
.
примитивно рекурсивная. Пусть для слов в алфавите 
заданы подстановки 
Примените к слову abcddacba.
Определите, в какое слово переработает МТ слово 111*11, исходя из начального стандартного состояния. МТ задана функциональной схемой.Самостоятельная работа по теме «Предикаты»
1.Найти формулы ПНФ:
1. "x(A(x)®ù B(y))®$y(B(y)®ù A(x))
2. "x(ù A(x)®$x(ù C(x)))®"x((C(x)®A(x))
3. "x(A(x)®$x(B(x)))®$y(ù A(x)Úù C(y)ÚC(y)&B(x))
4. "x(A(x)®$x(B(y)))®$x(ù A(x)®ù B(y))
5. "x(A(x)®B(y))&"y(A(x)®(B(y)®C(z))®$z(A(x)®C(z))
6. "x(A(x)®$y(B(y)®C(z)))®"z(A(x)&B(y)®C(z))
7. "x(A(x)®B(z))&"y(C(y)®A(x))®$z(C(y)®B(z))
8. "x(A(x)®B(y))®"y((C(y)ÚA(x))®(C(y)Ú$y(B(y)))
9. "x(A(x)®B(y))&"y(A(x)®(B(y)®C(z)))®(A(x)®$z(C(z)))
10. "x(A(x)®B(y)&A(x)®"y(B(y)®C(z)))®(A(x)®$z(C(z)))
11. "x(A(x)®$z(B(y)®C(z)))®"y(B(y)®(A(x)®C(z)))
12. "x(A(x)®$z(B(y)®C(z)))®"y(B(y)®(A(x)®C(z)))
13. ("x(A(x))®$x(B(x)))®"z((B(x)®C(z))®(A(x)®C(z)))
14. ($x(ù A(x))®"x(ù B(x)))®(ù B(x)ÚA(x))
15. ("x(A(x)))®("x(B(x)))®$y(C(y)&A(x)®C(y)&B(x))
16. "x(ù A(x)®$y(B(y)))®(ù B(y)®A(x))
17. ("x(B(x))®$x(A(x)))&$y((A(x)®C(y))®(ù C(y)&B(x)))
18. "x(ù A(x)®$y(B(y)))®(B(y)ÚA(x))
19. "x(ù A(x)®$y(ù B(y)))®(B(y)®A(x))
20. "x(A(x)®B(x))&$y(B(x)®C(y)&$z(C(y)®D(z)))
2.Какие из нижеприведенных формул являются тождестивенно истинными:
1. $x(P1(x))&$x(P2.(x))®$x(P1(x)&P2.(x));
2. "y(P1.(x))&"y (P2.(x))®"y(P1.(x)&(P2.(x));
3. $x(P1(x)ÚP2.(x))®$x(P1(x))Ú$x(P2.(x));
4. "y(P1.(x)Ú(P2.(x))®"y(P1.(x))Ú"y (P2.(x))
3.Докажите выводимость заключения методом дедукции:
a) "x(P1.(x)®ù P2.(x)); "x(P3.(x)®P1.(x))
"x(P3.(x)®ù P2.(x));
б) "x($y(P21.(x; y)&P2.(y)® $y(P3.(y)&P24.(x; y)))
ù $x(P3.(x)®"x"y(P21.(x; y)®ù P2.(y)));
в) "x(P1.(x)®P2.(x)& P3.(x)); $x(P1.(x)& P4.(x))
$x(P4.(x)&P3.(x)).
4.Докажите выводимость заключения по принципу резолюции:
$x(P1.(x)&"y(P2.(y)® P23.(x; y)));
"x(P1.(x)®"y(P4.(y)® ù P23.(x; y)))
"y(P2.(y)®P4.(y)).
Вопросы к экзамену
1. Логика и интуиция. Логика традиционная и математическая логика.
2. Высказывания и операции над ними.
3. Формулы алгебры высказываний
4. Тавтологии алгебры высказываний. Основные правила получения тавтологий.
5. Логическая равносильность формул. Примеры равносильных формул. Равносильные преобразования формул.
6. Нормальные формы для формул алгебры высказываний. Представление формул алгебры высказываний совершенными дизъюнктивными нормальными (СДН) формами и совершенными конъюнктивными нормальными (СКН) формами. Два способа приведения формулы алгебры высказываний к совершенной нормальной форме
7. Логическое следование формул. Следование и равносильность формул. Правила логических умозаключений.
8. Приложение алгебры высказываний к логико – математической практике.
9. Методы доказательства математических теорем. Дедуктивные и индуктивные умозаключения. Правильные и неправильные дедуктивные умозаключения.
10. Булевы функции. Происхождение булевых функций. Булевы функции от одного аргумента. Булевы функции от двух аргументов. Свойства дизъюнкции, конъюнкции и отрицания. Свойства эквивалентности, импликации и отрицания. Выражение одних булевых функций через другие.
11. Булевы функции от n аргументов. Понятие булевой функции. Число булевых функций. Выражение булевых функций через конъюнкцию, дизъюнкцию и отрицание.
12. Булевы функции и формулы алгебры высказываний. Нормальные формы булевых функций.
13. Полные системы булевых функций. Специальные классы булевых функций. Теорема Поста о полноте системы булевых функций.
14. Применение булевых функций к релейно-контактным схемам. Идея применения. Две основные задачи теории релейно-контактных схем. Релейно-контактные схемы в ЭВМ.
15. Двоичный полусумматор. Одноразрядный двоичный сумматор. Шифратор и дешифратор
16. Система аксиом и теория формального вывода. Теорема о дедукции и следствия из неё. Применение теоремы о дедукции.
17. Производные правила вывода.
18. Полнота формализованного исчисления высказываний. Теорема адекватности.
19. Непротиворечивость формализованного исчисления высказываний. Разрешимость формализованного исчисления высказываний.
20. Независимость системы аксиом формализованного исчисления высказываний.
21. Понятие предиката. Классификация предикатов. Множество истинности предиката. Равносильность и следование предикатов
22. Логические операции над предикатами. Отрицание предиката. Конъюнкция двух предикатов. Дизъюнкция двух предикатов. Свойства отрицания, конъюнкции и дизъюнкции. Импликация и эквивалентность двух предикатов.
23. Кванторные операции над предикатами. Квантор общности. Квантор существовании. Численные кванторы. Ограниченные кванторы.
24. Понятие формулы логики предикатов. Классификация формул логики предикатов. Тавтологии логики предикатов
25. Равносильные преобразования формул и логическое следование формул логики предикатов.
26. Проблемы разрешения для общезначимости и выполнимости формул.
27. Применение логики предикатов к логико-математической практике.
28. Формализованное исчисление предикатов. Первоначальные понятия. Система аксиом исчисления предикатов. Правила вывода. Теория формального вывода.
29. Неформальные аксиоматические теории. Примеры аксиоматических теорий. Интерпретации и модели аксиоматической теории. Свойства аксиоматической теории.
30. Формальные аксиоматические теории. Понятие формальной аксиоматической теории.
31. Формализованное исчисление высказываний как формальная аксиоматическая теория. Формализация теории аристотелевых силлогизмов.
32. Свойства формализованного исчисления предикатов. Непротиворечивость формализованного исчисления предикатов. Теорема Гёделя о существовании модели. Полнота и адекватность формализованного исчисления предикатов. Неполнота формализованного исчисления предикатов в абсолютном и узком смыслах. Теорема компактности.
33. Интуитивное представление об алгоритмах.
34. Машины Тьюринга. Определение машины Тьюринга. Применение машин Тьюринга к словам.
35. Конструирование машин Тьюринга. Вычислимые по Тьюрингу функции. Правильная вычислимость функций на машине Тьюринга. Композиция машин Тьюринга. Тезис Тьюринга (основная гипотеза теории алгоритмов) Машины Тьюринга и современные электронно-вычислительные машины.
36. Рекурсивные функции. Основные понятия теории рекурсивных функций и тезис Чёрча. Примитивно рекурсивные функции. Примитивная рекурсивность предикатов. Вычислимость по Тьюрингу примитивно рекурсивных функций. Функции Аккермана. Оператор минимизации.
37. Общерекурсивные и частично рекурсивные функции. Вычислимость по Тьюрингу частично рекурсивных функций. Частичная рекурсивность функций, вычислимых по Тьюрингу.
38. Характеристики сложности алгоритмов.
39. Пропозициональные логики: интуиционистские логики, многозначные логики, нечеткие логики и нечеткие множества, модальные логики, временные (темпоральные логики).
40. Предикатные логики.
41. Предикатные временные логики и их приложение к программированию.
42. Алгоритмическая логика Хоара.
Методические рекомендации по освоению учебного материала.
Методические рекомендации преподавателю:
При проведении практических занятий по математической логике и теории алгоритмов рекомендуется:
§ уделять внимание разбору теоретических задач, предлагаемых на лекциях и на семинарских занятиях;
§ уделять внимание краткому повторению теоретического материала, который используется при решении упражнений и задач;
§ осуществлять регулярную проверку домашних заданий;
§ ставить проблемные вопросы, по возможности использовать примеры и задачи с практическим содержанием;
§ использовать при проведении практических занятий активные методы обучения;
§ развивать математическую логику у студентов.
Методические указания студентам:
Учиться преодолевать самый высокий уровень непонимания материала («непонятно, что непонятно»).
При разборе примеров в аудитории или при выполнении домашних заданий целесообразно каждый шаг обосновывать теми или иными теоретическими положениями.
При изучении теоретического материала не задерживать внимание на трудных и непонятных местах, смело их пропускать и двигаться дальше, а затем возвращаться к тому, что было пропущено (часто последующее проясняет предыдущее).
При чтении учебников и лекционных материалов активно отмечать карандашом непонятные места. Карандаш легко стирается, когда вопрос можно снять.
С первых студенческих дней конструировать собственный стиль понимания сути изучаемого материала. Математические дисциплины в этой ситуации являются наиболее успешным полигоном.
Самостоятельная работа студентов. Аудиторная самостоятельная работа студентов по дисциплине выполняется на учебных занятиях под непосредственным руководством преподавателя и по его заданию. Она включает: текущие консультации; коллоквиум как форма контроля освоения теоретического содержания дисциплины (в часы консультаций); прием и разбор домашних заданий (в часы практических занятий).
Внеаудиторная самостоятельная работа выполняется студентом по заданию преподавателя, но без его непосредственного участия. Она включает: формирование и усвоение содержания конспекта лекций, а также самостоятельное изучение отдельных вопросов на базе рекомендованной преподавателем учебной литературы, включая информационные образовательные ресурсы (электронные учебники, электронные библиотеки); написание рефератов; подготовка к выступлению на конференции; подготовка к семинарам, их оформление; выполнение микроисследований; выполнение домашних заданий в виде решения отдельных задач, проведения типовых расчетов, расчетно-компьютерных и индивидуальных работ по отдельным разделам содержания дисциплины; компьютерный текущий самоконтроль и контроль успеваемости.
Для того, чтобы заработать то количество баллов, которое вы видите в тематическом плане дисциплины «Математическая логика и теория алгоритмов» по каждой теме, вам необходимо сделать задание по данной теме на оценку «отлично». В противном случае преподаватель имеет право снять несколько баллов. Снять баллы преподаватель может и за пропущенные семинарские или лекционные занятия.
Баллы, характеризующие успеваемость студента по дисциплине, набираются им в течение всего периода обучения за изучение дидактических единиц.
При выборе критериев оценки освоения студентом программы дисциплины в обязательном порядке учитывается: выполнение программы в части лекционных, практических занятий; выполнение предусмотренных программой аудиторных и внеаудиторных контрольных и иных письменных работ. Преподаватель осуществляет текущий контроль и выставляет рейтинговый балл по каждой контрольной точке модуля.
Максимальная сумма баллов, набираемая студентом по дисциплине (за один семестр), равна 100. Студент, набравший менее 60 баллов получает итоговую оценку – неудовлетворительно, от 61 до 75 – удовлетворительно, от 76 до 90 - хорошо, 91 и выше баллов - отлично.
4. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ
В учебном процессе используются стандартно оборудованные лекционные аудитории для проведения лекций и семинарских занятий, компьютерный класс, мобильный класс на ноутбуках. Совместно с данным оборудованием используются мультимедийный видеопроектор, интерактивная доска и интерактивная панель. В компьютерном классе должны быть установлены средства MS Office: Word, Excel, и др.
Мобильные классы на ноутбуках используется в учебно-образовательной деятельности, как для учебных занятий, так и для организации доступа к ресурсам корпоративной сети и Internet на всей территории РИ АлтГУ. Все компьютеры объединены в единую локальную вычислительную сеть и имеет доступ в Интернет.
5. СПИСОК ОСНОВНОЙ И ДОПОЛНИТЕЛЬНОЙ ЛИТЕРАТУРЫ, ДРУГИЕ ИНФОРМАЦИОННЫЕ ИСТОЧНИКИ
1. М Математическая логика. Дискретные функции. Теория алгоритмов: учеб. пособие / М. М Глухов., - СПб.: Лань, 2012. – 416 с.
2. Глухов, и упражнения по математической логике, дискретным функциям и теории алгоритмов: учеб. пособие / , В. А Шапошников и др. - СПб. : Лань, 2008. –
112 с. (Учебник для вузов. Специальная литература)
3. Лихтарников, логика : Курс лекций : Задачник-практикум и решения : учеб. пособие / , . – изд. 4-е, стер. – СПб. [и др.] : Лань, 2009. – 288 с.
Дополнительная литература
4. Акимов, математика: Логика, группы, графы / . - доп.- М.: Лаборатория Базовых Знаний, 20c
5. Аляев, математика и математическая логика: учебник/ , .-М.: Финансы и статистика, 2006.-368с.
6. Асанов, математика: графы, матрицы, алгоритмы / , . - Ижевск: НИЦ «Регулярная и хаотическая динамика», 20c.
7. Асеев, математика: учебное пособие / . - Ростов-н/Д: Феникс, 20c.
8. Галиев, логика и теория алгоритмов: учебное пособие / . -Казань: Издательство КГТУ им. . 20с.
9. Галушкина, лекций по дискретной математике / , . – М.: Айрис-пресс, 2007. – 176 с.
10. Гончарова, дискретной математики / , . - М.: ФОРУМ-ИНФРА-М, 20c
11. Игошин, и упражнения по математической логике и теории алгоритмов: учебное пособие / . - М.: Изд. центр «Академия», 20c.
12. Игошин, логика и теория алгоритмов: учебное пособие / . - М.: Издательский центр «Академия», 20c.
13. Кузнецов, математика для программистов : Учебник / . - СПб: Питер, 20c.
14. Лавров, логика: учебное пособие / ; под ред. . – М.: Издательский центр «Академия», 2006. – 240с.
15. Лихтарников, логика. Курс лекций. Задачник – практикум и решения: учебное пособие / . - Спб.: Лань, 19с.
16. Новиков, математика для программистов: учебник / . - СПб: Питер, 20c
17. Судоплатов, логика и теория алгоритмов: учебник / , . - М.-Новосибирск: ИНФРА-М - НГАЭиУ, 20c.
Базы данных, Интернет-ресурсы,
информационно-справочные и поисковые системы
18. Единое окно доступа к образовательным ресурсам. Электронная библиотека [Электронный ресурс]: инф. система. – М.: ФГАУ ГНИИ ИТТ "Математика", . – Режим доступа: //www. http://window. *****, свободный. – Загл. с экрана (дата обращения 11.04.2012)
19. Единое окно доступа к образовательным ресурсам. Электронная библиотека [Электронный ресурс] Университетская библиотека on-line. Режим доступа:// http://www. *****/collection. phpid=24– Загл. с экрана (дата обращения 11.10.2012).
20. Единое окно доступа к образовательным ресурсам. Электронная библиотека [Электронный ресурс] Издательство Лань. Режим доступа:// http://e. /– Загл. с экрана (дата обращения 15.10.2012).
21. Поисковые системы: Google, Yandex, Rambler.
