Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста [Оставьте этот титульный лист для дисциплины,
Скачать 291.1 Kb.
|
6Формы контроля знаний студентов
6.1Критерии оценки знаний, навыков Порядок формирования оценок по дисциплине Текущий контроль – домашняя контрольная работа в первом модуле, домашняя контрольная работа во втором модуле Итоговый контроль – устный зачет в конце второго модуля. Результирующая оценка за текущий контроль рассчитывается следующим образом: Отекущий = 0,5·Ок/р + 0,5·Од/з Активность работы студентов на практических лабораторных занятиях учитывается в рабочей ведомости и составляет оценку Оаудиторная. Также учитывается оценка Осам. работа самостоятельной работы студентов: в практических домашних задачах на программирование оценивается функциональность и объем созданных программ; в самостоятельных докладах на семинарах – полнота и глубина освещения темы. Итоговая оценка по курсу выставляется по следующей формуле: Оитоговая = 0,3·Озачет +0,4·Отекущий + 0,2·Оаудиторная где О зачет – оценка за работу непосредственно на зачете. 6.1.1 Таблица соответствия оценок по десятибалльной и системе зачет/незачет
7Содержание дисциплиныТема 1. Элементы теории множеств 1.1. Взаимно однозначное соответствие между множествами. Равномощность множеств. Счетные множества, простейшие теоремы о счетных множествах. 1.2. Теорема о конечности или счетности объединения конечного или счетного множества конечных или счетных множеств. Ее применения. 1.3. Теорема о равномощности бесконечного множества и его объединения с конечным или счетным множеством. 1.4. Определение неравенства между мощностями множеств. Теорема Кантора—Бернштейна. 1.5. Теорема Кантора. Несчетность множества всех бесконечных последовательностей из 0 и 1. 1.6. Парадоксы теории множеств. Основная литература Н. К. Верещагин, А. Шень, Начала теории множеств, МЦНМО, М., 1999 Ю. П. Шевелев, Дискретная математика, Лань, М., 2008 Г. П. Гаврилов, А. А. Сапоженко, Сборник задач по дискретной математике, Наука, М., 1977 Дополнительная литература И. А. Лавров, Л. Л. Максимова, Задачи по теории множеств, математической логике и теории алгоритмов, Наука, М., 1984 Тема 2. Вычислимость 2.1. Машина с неограниченными регистрами (МНР). Система команд. Программа. Схема работы МНР по заданной программе. 2.2. МНР-вычислимые функции. Разрешимые предикаты. 2.3. Теорема о вычислимости суперпозиции вычислимых функций. 2.4. Неформальные алгоритмы. Тезис Черча. 2.5. Теорема о существовании МНР-невычислимых функций. 2.6. Система нумерации МНР-команд и МНР-программ. Примеры явного описания программ по заданному номеры. 2.7. Построение МНР-невычислимой программы, использующее явную нумерацию программ. 2.8. Универсальная функция для заданного множества МНР-вычислимых функций. Теорема о существовании универсальной фукнции для множества всех МНР-вычислимых функций одного переменного. 2.9. Тотальные МНР-вычислимые функции. Теорема о несуществовании универсальной функции для множества всех тотальных МНР-вычислимых функций одного переменного. 2.10. Теорема о несуществовании алгоритма, определяющего тотальность/нетоталь-ность элементов множества всех МНР-вычислимых функций. 2.11. Разрешимые и перечислимые множества. Теорема о разрешимости любого перечислимого множества. Теорема о существовании перечислимых неразрешимых множеств. 2.12. Теорема о том, что всякое перечислимое множество натуральных чисел есть проекция на первую координату некоторого разрешимого подмножества в множестве всех пар натуральных чисел. 2.13. Алгебраические подмножества. Диофантовы подмножества. Теорема Матиясеви-ча (без доказательства). 10-я проблема Гильберта и ее отрицательное решение с помощью теоремы Матиясевича. 2.14. Теорема о том, что всякое перечислимое множество есть множество значений некоторой тотальной МНР-вычислимой функции. 2.15. Теорема о том, что множество перечислимо тогда и только тогда, когда оно является множеством неотрицательных значений некоторого многочлена от нескольких переменных с целыми коэффициентами. Приложение: существование «формулы простых чисел». Основная литература Н. Катленд, Вычислимость. Введение в теорию рекурсивных функций, Мир, М., 1983 Дополнительная литература Н. К. Верещагин, А. Шень, Лекции по математической логике и теории алгоритмов. Вычислимые функции, МЦНМО, М., 1999 Тема 3. Булевы функции 3.1. Основные определения: булева функция, конъюнкция, дизъюнкция, отрицание, импликация, эквивалентность, таблица истинности. 3.2. n-мерный единичный куб, его грани в вершины. Нумерация вершин с помощь двоичного разложения целых чисел. 3.3. Определение формулы. Задание булевых функций с помощью формул, вопрос о его единственности. Равносильность формул. Список важнейших равносильностей алгебры логики. 3.4. Носитель булевой функции. Теорема о носителе конъюнкции (дизъюнкции) булевых функций. 3.5. Элементарная конъюнкция. Правильная элементарная конъюнкция и теорема о ее носителе. 3.6. Дизъюнктивная нормальная форма (ДНФ) булевой функции и совершенная ДНФ (СДНФ). Теорема о существовании единственной СДНФ и любой ненулевой булевой функции. Практический способ нахождения СДНФ. 3.7. Полином Жегалкина булевой функции. Теорема о его существовании и единственности. 3.8. Сокращенная ДНФ. Правила обобщенного склеивания и поглощения. 3.9. Алгоритм Блейка нахождения СДНФ. 3.10. Тупикования ДНФ и способ ее нахождения. 3.11. Двойственная и самодвойственная булева функция. Теорема о суперпозиции двойственных булевых функций. 3.12. Монотонные булевы функции Теорема о суперпозиции монотонных булевых функций. 3.13. Функциональное замыкание совокупности булевых функций. Функционально замкнутые совокупности. Полные совокупности. Классы S, L, M, T0, T1, их функциональная замкнутость и полнота. 3.14. Теорема Поста о полноте. 3.15. Контактные схемы и булевы функции, ими реализуемые. Проблема минимизации контактных схем. Функция Шеннона. Теоремы Шеннона и Лупанова. Основная литература С. Г. Гиндикин, Алгебра логики в задачах, Наука, М., 1972 Дополнительная литература Ю. П. Шевелев, Дискретная математика, Лань, М., 2008 Г. П. Гаврилов, А. А. Сапоженко, Сборник задач по дискретной математике, Наука, М., 1977 Тема 4. Формальные исчисления 4.1. Компоненты, из которых состоит любое формальное исчисление: язык, аксиомы, правило вывода. 4.2. Язык, аксиомы и правило вывода исчисления высказываний. 4.3. Алгоритм, распознающий является ли конечная последовательность формул выводом в исчислении высказываний или нет. 4.4. Теорема об отсутствии в исчислении высказываний лишних правил вывода. 4.5. Формулы в исчислении высказываний, являющиеся тавтологией. Критерий выводимости формулы в исчислении высказываний (с доказательством того, что из выводимости следует тавтологичность). 4.6. Алгоритм эффективного нахождения вывода по данной выводимой формуле в исчислении высказываний. Основная литература В. А. Душский, Исчисление высказываний и его свойства, МИЭМ, М., 2007 Дополнительная литература П. С. Новиков, Элементы математической логики, Наука, М., 1973 И. А. Лавров, Л. Л. Максимова, Задачи по теории множеств, математической логике и теории алгоритмов, Наука, М., 1984 | ||||||||||||||||||||||||||||||||||||||||||||||
Похожие:
![Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста [Оставьте этот титульный лист для дисциплины, icon](/i/doc32.png) | Программа дисциплины [Введите название дисциплины] для направления/... Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления... | | Программа дисциплины [Введите название дисциплины] для направления/... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 080500. 62 "Бизнес-информатика"... |
| Программа дисциплины [Введите название дисциплины] для направления/... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки бакалавра... | | Программа дисциплины [Введите название дисциплины] для направления/... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 035800. 62 «Фундаментальная... |
| Программа дисциплины [Введите название дисциплины] для направления/... Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления... | | Программа дисциплины [Введите название дисциплины] для направления/... Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления... |
| Программа дисциплины [Введите название дисциплины] для направления/... Т. Г. Морозова, доктор географических наук, профессор взфэи, кафедра «Региональная экономика» | | Программа дисциплины [Введите название дисциплины] для направления/... Учебно-методическое пособие по курсу «Философия права». Таганрог: Изд-во трту, 2005. 23 с |
| Программа дисциплины [Введите название дисциплины] для направления/... Программа предназначена для студентов направления 032100. 62 «Востоковедение, африканистика» подготовки бакалавра, изучающих Материальную... | | Программа дисциплины [Введите название дисциплины] для направления/... Программа предназначена для студентов направления 032100. 62 «Востоковедение, африканистика» подготовки бакалавра, изучающих Материальную... |
| Программа дисциплины [Введите название дисциплины] для направления/... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 032100. 62 «Востоковедение,... | ![Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления подготовки» ] подготовки бакалавра/ магистра/ специалиста [Оставьте этот титульный лист для дисциплины, icon](/i/32.png) | Программа дисциплины [Введите название дисциплины] для направления/... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 032100. 62 «Востоковедение,... |
| Программа дисциплины [Введите название дисциплины] для направления/... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления 032100. 62 «Востоковедение,... | | Программа дисциплины [Введите название дисциплины] для направления/... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки/ специальности,... |
| Программа дисциплины [Введите название дисциплины] для направления/... Программа предназначена для преподавателей, ведущих данную дисциплину, учебных ассистентов и студентов направления подготовки для... | | Программа по формированию навыков безопасного поведения на дорогах... Программа дисциплины [Введите название дисциплины] для направления/ специальности [код направления подготовки и «Название направления... |
