Элективный курс по информатике по теме "Математическая логика и теория алгоритмов"

Одна из задач профильной школы — содействовать воспитанию нового поколения, отвечающего по своему уровню развития и образу жизни условиям информационного общества. Данный элективный курс актуален т.к. он выполняет основные задачи профильной школы.
Эта программа предназначена для проведения элективных курсов по информатике с учащимися 10-11 классов технологического профиля общеобразовательных школ.
Программа составлена на основе федерального компонента государственного стандарта и примерной программы основного общего образования. Программа определяет содержание элективного курса, дает распределение учебных часов по темам курса и определяет последовательность изучения тем.
Занятия проводятся в виде 1 часа в неделю, курс рассчитан на 38 часов. Итоговый контроль проходит на заключительных двух уроках курса в виде тестирования и контрольной работы.
Цель: Формирование представлений о математической логике и теории алгоритмов.
Задачи курса:
• Сформировать логическое мышление учащихся.
• Уметь решать задачи математической логики и теории алгоритмов.
• Применять полученные знания в других разделах информатики (программировании).

Тематическое планирование

№ Название раздела Количество часов Форма проведения Образовательный продукт
Всего Лекции Практика
1

Элементы логики высказываний.
8 5 3 Лекции, работа в группах, индивидуальная работа. Конспект, выполненные задания, таблицы.
2
Логика предикатов. 10 7 3 Лекции, практикум Выполненные задания, конспект, схемы.
3

Математические доказательства. 8 4 4 Лекции, практикум Выполненные задания, конспект, таблица.
4

Теория Алгоритмов
10 5 5 Лекции, практикум Выполненные задания, конспект, таблица.
5 Зачет
2 1 1 Тестирование,
контрольная работа Контрольная работа, тест.
Всего: 38 22 16

Содержание разделов.

РАЗДЕЛ I. Элементы логики высказываний.
Высказывания, их истинностные значения. Логические операции над высказываниями: отрицание, конъюнкция, дизъюнкция, эквиваленция. Таблицы истинности.
Логическая структура составных высказываний. Формулы логики высказываний; таблицы истинности для формул. Равносильность формул. Законы логики. Проверка равносильности с помощью таблиц истинности. Преобразование формул.
Алгебра множеств. Функции алгебры логики. Нормальные формы формул. Логический анализ предложений математического и естественного языков. Проблема разрешимости в алгебре логики.
Исчисление высказываний. Алфавит, формулы исчисления высказываний и правила вывода.
Решение задач средствами логики высказываний.
Учащиеся должны знать:
• этапы составления таблиц истинности;
• основные базовые элементы логических схем;
• правила составления логических схем;
• правила преобразования логических выражений и законы.
Учащиеся должны уметь:
• составлять таблицы истинности;
• решать логические задачи, сформулированные на обычном языке
• составлять логические схемы.

РАЗДЕЛ II. Логика предикатов.
Понятие предиката, предикаты различной местности. Множество истинности предиката. Логические операции над предикатами. Кванторные операции над предикатами.
Формулы логики предикатов. Нормальные формы формулы логики предикатов. Общезначимость и выполнимость формул логики предикатов.
Символическая запись предложений математического и естественного языков; их преобразование; построение отрицаний.
Учащиеся должны знать:
• Понятие предиката, предикаты различной местности;
• формулы логики предикатов;
• множество истинности предиката.
Учащиеся должны уметь:
• выполнять логические операции над предикатами;
• выполнять квантовые операции над предикатами;

РАЗДЕЛ III. Математические доказательства.
Общий вид условного математического предложения, его составные части: разъяснительная часть, условие, заключение. Отношения следования и равносильности между предложениями. Структура теоремы. Виды теорем. Необходимые и достаточные условия. Умозаключения и их виды. Способы математического доказательства.
Учащиеся должны знать:
• общий вид условного математического предложения, его составные части;
• структуру теоремы;
• виды теорем.
Учащиеся должны уметь:
• доказывать математически.
РАЗДЕЛ IV. Теория Алгоритмов
Понятие алгоритма, свойства алгоритма. Понятие эффективно вычисляемой функции (Черч, Гедель). Машина Тьюринга. Структура Машины Тьюринга. Нормальные алгоритмы Маркова. Решение задач с использованием Машины Тьюринга и Нормальных алгоритмов Маркова.
Учащиеся должны знать:
• Понятие алгоритма, свойства алгоритма;
• Структура Машины Тьюринга;
• Нормальные алгоритмы Маркова.
Учащиеся должны уметь:
• Решать задачи с помощью Машины Тьюринга и Нормального алгоритма Маркова.

Литература
1. Булос Дж., Джеффри Р. Вычислимость и логика. М.: Мир, 1994. [С. 12-55, 131-152, 167-180, 253-274.]
2. Мендельсон Э. Введение в математическую логику. М.: Наука, 1984. [С. 19-81, 86-102.]
3. Лавров И. А, Максимова Л. Л. Задачи по теории множеств, математической логике и теории алгоритмов. М.: Физ.-мат. литература, 1995. [С. 50-107, 124-147.]
5. Столл Р. Множества, логика, аксиоматические теории. М.: Просвещение, 1968. [С. 72-191.]
6. Успенский В. А., Верещагин Н. К., Плиско В. Е. Вводный курс математической логики. М.: МГУ, 1991 [С. 17-90, 96-98, 103-133.]
Дополнительная литература
1. Справочная книга по математической логике / Под ред. Дж. Барвайза. Часть 1, Теория моделей. М.: Наука, 1982. [С. 13-55.]
2. Гейтинг А. Интуиционизм. М., Мир, 1965.
3. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. М.: Мир, 1983. [С. 9-33, 75-114.]
4. Клини С. К. Математическая логика. М.: Мир, 1973. [С. 11-176, 270-296.]
5. Линдон Р. Заметки по логике. М.: Мир, 1968. [С. 11-88.]
6. Успенский В. А. Лекции о вычислимых функциях. М., Физматгиз, 1960. [С. 24-32, 53-81.]
7. Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. М.: Наука, 1983. [С. 11-52.]
8. Фейс Р. Модальная логика. М.: Наука
9. Методическая газета для учителей информатики «1 сентября. Информатика»

Автор: Костюченко Наталья Владимировна, учитель информатики и математики МОУ "СОШ №5" г. Ачинска