| Закреплена за кафедрой | Кафедра вычислительной техники и электроники |
|---|---|
| Направление подготовки | 09.03.01. Информатика и вычислительная техника |
| Профиль | Программно-техническое обеспечение инфокоммуникационных технологий |
| Форма обучения | Очная |
| Общая трудоемкость | 5 ЗЕТ |
| Учебный план | 09_03_01_Информатика и вычислительная техника_ПОИТ-2023 |
|
|
||||||||||||||
Распределение часов по семестрам
| Курс (семестр) | 2 (4) | Итого | ||
|---|---|---|---|---|
| Недель | 22 | |||
| Вид занятий | УП | РПД | УП | РПД |
| Лекции | 36 | 36 | 36 | 36 |
| Практические | 36 | 36 | 36 | 36 |
| Сам. работа | 81 | 81 | 81 | 81 |
| Часы на контроль | 27 | 27 | 27 | 27 |
| Итого | 180 | 180 | 180 | 180 |
| 1.1. | Дисциплина обеспечивает приобретение знаний в соответствии с государственным образовательным стандартом, содействует фундаментализации образования, развитию логического мышления и развитию математического мышления. Цель изучения дисциплины – формирование у будущих специалистов теоретических знаний и практических навыков по применению основ математической логики и теории алгоритмов для решения широкого спектра задач в различных областях с использованием современных персональных компьютеров и программных средств, а именно: ознакомить студентов с основами теории алгоритмов и математической логики; привить навыки решения задач математической логики, разработки алгоритмов и оценки их сложности; изложить основные разделы математической логики и теории алгоритмов. А также цель изучения дисциплины – формирование у будущих специалистов теоретических знаний и практических навыков по использованию современных персональных компьютеров и программных средств для решения широкого спектра задач в различных областях, а именно: ознакомить студентов с основами теории вычислений и оценками погрешностей численных методов; привить навыки работы с различными математическими пакетами и языками программирования для создания прикладных программ. Основными задачами изучения дисциплины являются: - овладение фундаментальными знаниями по математической логике и теории алгоритмов: целостное представление о науке и ее роли в развитии информационных и компьютерных технологий; владеть общими вопросами теории разработки алгоритмов; - приобретение навыков логического и алгоритмического мышления; - приобретение практических навыков по решению задач математической логики основам алгоритмизации и программирования; - овладение фундаментальными знаниями по численным методам: целостное пред-ставление о науке и ее роли в развитии вычислительных технологий; - владеть общими вопросами оценок погрешностей вычислительных методов; - приобретение практических навыков работы на персональном компьютере с пакетами прикладных программ (MathLab, Mathematika, MathCad). |
|---|
| Цикл (раздел) ООП: Б1.О.05 |
| ОПК-1 | Способен применять естественнонаучные и общеинженерные знания, методы математического анализа и моделирования, теоретического и экспериментального исследования в профессиональной деятельности; |
| ОПК-1.1 | Знать: основы математики, физики, вычислительной техники и программирования |
| ОПК-1.2 | Уметь: решать стандартные профессиональные задачи с применением естественнонаучных и общеинженерных знаний, методов математического анализа и моделирования. |
| ОПК-1.3 | Владеть: навыками теоретического и экспериментального исследования объектов профессиональной деятельности |
| ОПК-8 | Способен разрабатывать алгоритмы и программы, пригодные для практического применения; |
| ОПК-8.1 | Знать: алгоритмические языки программирования, операционные системы и оболочки, современные среды разработки программного обеспечения |
| ОПК-8.2 | Уметь: составлять алгоритмы, писать и отлаживать коды на языке программирования, тестировать работоспособность программы, интегрировать программные модули |
| ОПК-8.3 | Владеть: языком программирования; навыками отладки и тестирования работоспособности программы |
| В результате освоения дисциплины обучающийся должен | |
| 3.1. | Знать: |
|---|---|
| 3.1.1. | основы математики, физики, вычислительной техники и программирования; алгоритмические языки программирования, операционные системы и оболочки, современные среды разработки программного обеспечения. |
| 3.2. | Уметь: |
| 3.2.1. | решать стандартные профессиональные задачи с применением естественнонаучных и общеинженерных знаний, методов математического анализа и моделирования; составлять алгоритмы, писать и отлаживать коды на языке программирования, тестировать работоспособность программы, интегрировать программные модули. |
| 3.3. | Иметь навыки и (или) опыт деятельности (владеть): |
| 3.3.1. | навыками теоретического и экспериментального исследования объектов профессиональной деятельности; языком программирования; навыками отладки и тестирования работоспособности программы. |
| Код занятия | Наименование разделов и тем | Вид занятия | Семестр | Часов | Компетенции | Литература |
|---|---|---|---|---|---|---|
| Раздел 1. Семестр 4 | ||||||
| 1.1. | Что изучает логика и математическая логика? Компоненты формальных теорий. Что такое высказывание? Логические операции (связки: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция). Формулы логики высказываний (подформулы). Интерпретация формул. Таблицы истинности для формул. Выполнимые и опровержимые формулы. Тождественно-истинные и тождественно-ложные формулы (тавтологии и противоречия). Теоремы 1 и 2 «о тавтологиях». Наиболее важные тавтологии. Примеры тавтологий и противоречий. Логическая эквивалентность – равносильность формул. Основные равносильности (правила равносильных преобразований). Правило подстановки. Теоремы 1,2,3 «о равносильностях». | Лекции | 4 | 6 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.2. | Формальные теории (ФТ). Состав формальной теории Γ. Выводимость формул: определения «выводимой формулы», «вывода», «теоремы», свойства «сохранения выводимости при добавлении лишних гипотез», интерпретации и «модели множества формул», «модели ФТ». Общезначимость, непротиворечивость, полнота, независимость и разрешимость теории Г: определения общезначимой (тавтологии) и противоречивой формул, формулы «логического следствия» множества формул Г, определения «семантически и формально непротиворечивых» теории Г. Формулировки «метатеорем» о «семантически и формально непротиворечивых» теориях Г (без доказательства). Определения «полной» теории Г, «аксиоматизируемого» множества формул F, «независимой» системы аксиом, «разрешимой и полуразрешимой» теории Г. | Лекции | 4 | 6 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.3. | Исчисление высказываний – формальная теория L: определение ИВ (ее состав). Определения: «формула В - частный случай формулы А», унификатор, «формула С - совместный частный случай формул А и В», унифицируемые формулы и наиболее общий унификатор, частный случай набора формул и совместный частный случай набора формул. Различные аксиоматизации ИВ: Аксиомы Клини. Доказательство Теоремы 1: A->A. Доказательство Теоремы 2: A->(B->A) и ее смысл (производное правило – правило «введения импликации»). Доказательство Теоремы «дедукции». Применимость правила дедукции для более широкого класса ФТ. Следствие 1(доказательство). Следствие 2:правило «транзитивности»(доказательство). Следствие 3: правило «сечения» (доказательство). Некоторые важные теоремы ИВ: ТЕОРЕМЫ (с доказательством): а)теорема «удаления двойного отрицания», б)теорема «введения двойного отрицания», в) , г) 1-ая теорема контрапозиции, д)2-ая теорема контрапозиции, е), ж). Множество теорем ИВ: доказательство основной леммы ИВ. Множество теорем ИВ: доказател | Лекции | 4 | 6 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.4. | Исчисление предикатов (ИП) – формальная теория К: определение и состав ИП. Свободное и связанное вхождение переменных в формулы. Контрарные литералы. Определение «свободного терма» в формуле, «чистого и прикладного ИП (ЧИП и ПИП)». Интерпретация ИП: определение, свойства интерпретации (11 свойств, в том числе определения истинной и открытой формул, модели множества формул). Общезначимость: определение и две теоремы. Метатеоремы 1, 2 о полноте ЧИП (без доказательства). Определения «логического следования» и «логической эквивалентности». Некоторые следствия и эквивалентности. | Лекции | 4 | 4 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.5. | Теория равенства: определение и 3 теоремы (с доказательством): 1) рефлексивность; 2) симметричность; 3) транзитивность. Вывод из теории равенства. Формальная арифметика (аксиоматика). Теория абелевых групп (АГ): определения АГ конечного порядка, полной АГ, периодической АГ. Формулировки 2-х Метатеорем Геделя о «неполноте» ПИП 1-го порядка. Вывод из теорем.Темпоральные логики; нечеткая и модальные логики, нечеткая арифметика. | Лекции | 4 | 4 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.6. | Автоматическое доказательство теорем (АДТ): постановка задачи, теорема «доказательство от противного» (как основа метода «резолюции»). Сведение формул ИП к предложениям. Теорема «о невыполнимости множества предложений, полученных из противоречия». Правило резолюции (ПР) для ИВ. Теорема (с доказательством): «ПР логично, т.е. резольвента – логическое следствие резольвируемых предложений». Правило резолюции для ИП. Алгоритм АДТ: «опровержение методом резолюций» (3 возможных случая). Вывод в отношении ИП на основании 3-го случая. Пример доказательства теорем ИВ по алгоритму АДТ «опровержение методом резолюций». | Лекции | 4 | 2 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.7. | Понятие алгоритма и неформальной вычислимости: определения и основные особенности алгоритма. Подход Геделя-Клини к формализации понятия алгоритма: Частично-рекурсивные функции (ЧРФ): операторы суперпозиции, примитивной рекурсии, минимизации для построения ЧРФ. Примеры рекурсивности (примитивно-рекурсивных и общерекурсивных функций) | Лекции | 4 | 2 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.8. | Подход А. Черча: Лямбда-исчисление. Его особенности. Лямбда-выражения и их вычисления. Определение лямбда-термов и лямбда-выражений. Редексы. Процесс редукции. Примеры редукций. Нормальные формы выражений и порядок редукций: аппликативный (АПР - стратегия энергичных вычислений) и нормальный (НПР - стратегия ленивых вычислений) порядок редукций. Следствие из теоремы Черча-Россера. Рекурсивные функции. Комбинатор неподвижной точки. Чистое лямбда-исчисление. | Лекции | 4 | 2 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.9. | Машины Тьюринга. Другие подходы к определению понятия алгоритма. Тезис Черча. Алгоритмически неразрешимые проблемы. | Лекции | 4 | 2 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.10. | Сложность алгоритмов: в наихудшем случае и поведения в среднем. Сложность задачи. Классификация задач по сложности: класс Р и класс Е. Класс NP. NP-трудные и NP-полные задачи. Теорема Кука. Эффективные алгоритмы. Основы нечеткой логики и элементы алгоритмической логики. Алгоритмическая логика Ч. Хоара. | Лекции | 4 | 2 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.11. | Система аксиом Пеано. | Сам. работа | 4 | 20 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.12. | Элементы теории моделей: Типы и основные классы моделей. | Сам. работа | 4 | 20 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.13. | Исчисление высказываний генценовского типа. Исчисление высказываний гильбертовского типа. Алгоритмы проверки общезначимости и противоречивости в ИВ. | Сам. работа | 4 | 10 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.14. | Пропозициональные логики. Алгоритмические логики | Сам. работа | 4 | 7 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.15. | Нестандартные модели арифметики. | Сам. работа | 4 | 4 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.16. | Примеры доказательства теорем ИВ по алгоритму АДТ «опровержение методом резолюций». | Сам. работа | 4 | 4 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.17. | Теория алгоритмов и конечные автоматы. Универсально частично рекурсивные функции. Теорема Райса. | Сам. работа | 4 | 4 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1 |
| 1.18. | Лямбда-абстракции. | Сам. работа | 4 | 4 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.19. | Алгоритмически неразрешимые проблемы. | Сам. работа | 4 | 4 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.20. | Переборные задачи. | Сам. работа | 4 | 4 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.21. | Упражнение 1.1. [Л2.1] Упражнение 1.2. [Л2.1] Упражнение 1.3. [Л2.1] Упражнение 1.4. [Л2.1] Упражнения к главе 1. [Л1.2] | Практические | 4 | 8 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.22. | Практическое занятие по теме «Булева алгебра» Примеры 3.1 и 3.2 из главы 3 [Л2.1] Упражнения к главе 3. [Л1.1] Практическое занятие по теме «Логика высказываний» Упражнения к главе 4. [Л1.1] Упражнения 2. [Л2.1] Задачи и упражнения к главе 1 [Л1.2] | Практические | 4 | 8 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.23. | Практическое занятие по теме «Логика предикатов» Упражнения к главе 4. [Л1.1] Упражнения 4. [Л2.1] Задачи и упражнения к главе 2 [Л1.2] | Практические | 4 | 8 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.24. | Практическое занятие по теме «Теория алгоритмов» Задачи из главы 6 и 7. [Л2.1] Задачи и упражнения к главе 4 [Л1.1] | Практические | 4 | 6 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 1.25. | Практическое занятие по теме «Теория алгоритмов» Задачи из главы 6 и 7. [Л2.1] Задачи и упражнения к главе 4 [Л1.1] | Практические | 4 | 6 | ОПК-8.1, ОПК-8.2, ОПК-8.3, ОПК-1.1, ОПК-1.2, ОПК-1.3 | Л1.1, Л2.1, Л2.2 |
| 5.1. Контрольные вопросы и задания для проведения текущего контроля и промежуточной аттестации по итогам освоения дисциплины |
| Оценочные материалы для текущего контроля размещены в онлайн-курсе на образовательном портале «Цифровой университет АлтГУ» https://portal.edu.asu.ru/course/view.php?id=4434. Вопросы закрытого типа: Вопросы к ОПК-1: 1. Как выглядит таблица истинности: (x → y) → y. 1. 0001; 2. 0001; 3. 0011; 4. 1100. Ответ: 1. 2. Как выглядит таблица истинности: (x ∨ y) → y. 1. 1101; 2. 0001; 3. 0011; 4. 1100. Ответ: 1. 3. Как выглядит таблица истинности: (x ∨ y) → (x ∨ y). 1. 1101; 2. 1111; 3. 0011; 4. 1100. Ответ: 2. 4. Как выглядит таблица истинности: (x → y) → (x ∨ y). 1. 0101; 2. 1111; 3. 0111; 4. 1100. Ответ: 3. 5. Булева функция «стрелка Пирса» представляется эквивалентной формулой: 1. Отрицание конъюнкции двух переменных; 2. Отрицание дизъюнкции двух переменных; 3. Отрицание «исключающего ИЛИ»; 4. Отрицание функции «штрих Шеффера». Ответ: 2. 6. Как связаны между собой две формы СДНФ и СКНФ для одной и той же булевой функции? 1. Обе формы являются отрицанием друг друга; 2. Обе формы являются «двойственными» по отношению к друг другу; 3. Каждая из них по отношению к другой является «самодвойственной»; 4. Не связаны между собой принципом «двойственности». Ответ: 2. 7. Что такое «минимальная» ДНФ для булевой функции? 1. Для булевой функции одна из эквивалентных ее ДНФ, которая содержит минимальное количество термов (конъюнктов); 2. Для булевой функции одна из эквивалентных ее ДНФ, которая состоит из конъюнктов (простых импликант), соответствующих «максимальным» интервалам; 3. Для булевой функции одна из эквивалентных ее ДНФ, которая содержит минимальное количество аргументов (переменных), т.е. ее ДНФ минимального ранга. Ответ: 3. 8. Что такое полная система булевых функций (базис)? 1. Класс (система) булевых функций, с помощью которого реализуема в виде формулы любая булева функция; 2. Класс булевых функций, являющихся самодвойственными и линейными функциями; 3. Класс булевых функций, являющийся «замкнутым» классом монотонных функций. Ответ: 1. 9. Каким символом обозначается логическое ИЛИ? 1. ∨; 2. +; 3. ||. Ответ: 1, 2, 3. 10. Каким символом обозначается логическое И? 1. ∧; 2. *; 3. &. Ответ: 1, 2, 3. 11. Что из перечисленного закон тождества: 1. A → A; 2. «Из A следует A»; 3. (A) ∨ (¬A); 4. «A или не-A». Ответ: 1 и 2. 12. Что из перечисленного закон исключённого третьего: 1. A → A; 2. «Из A следует A»; 3. (A) ∨ (¬A); 4. «A или не-A». Ответ: 3 и 4. 13. Каким символом обозначается логическое отрицание? 1. ∨; 2. +; 3. ||; 4. ¬. Ответ: 4. 14. Как записывается первый закон де Моргана? 1. a ∧ b = ¬(¬a ∨ ¬b); 2. a ∨ b = ¬(¬a ∧ ¬b). Ответ: 1. 15. Как записывается второй закон де Моргана? 1. a ∧ b = ¬(¬a ∨ ¬b); 2. a ∨ b = ¬(¬a ∧ ¬b). Ответ: 2. Вопросы к ОПК-8 1. UML является языком широкого профиля, это — открытый стандарт, использующий графические обозначения для создания абстрактной модели системы, называемой UML-моделью. Ответ: да. 2. Стек (англ. stack — стопка; читается стэк) — абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (англ. last in — first out, «последним пришёл — первым вышел»). Ответ: да. 3. Объе́ктно-ориенти́рованное программи́рование (ООП) — раздел дискретной математики и парадигма программирования, в которой процесс вычисления трактуется как вычисление значений функций в математическом понимании последних (в отличие от функций как подпрограмм в процедурном программировании). Ответ: нет. 4. Функциона́льное программи́рование — раздел дискретной математики и парадигма программирования, в которой процесс вычисления трактуется как вычисление значений функций в математическом понимании последних (в отличие от функций как подпрограмм в процедурном программировании). Ответ: да. 5. Условия Йоды (от англ. Yoda conditions), или нотация Йоды (англ. Yoda notation) в жаргоне программистов — «безопасный» стиль записи выражений сравнения при программировании на языках с Си-синтаксисом, заключающийся в написании константного члена выражения (константы или вызова функции) слева от оператора сравнения (то есть 5 \=\= a вместо привычного а \=\= 5). Ответ: да. 6. Станда́рт оформле́ния ко́да (станда́рт коди́рования, стиль программи́рования) (англ. coding standards, coding convention или programming style) — набор правил и соглашений, используемых при написании исходного кода на некотором языке программирования. Ответ: да. 7. Соотнесите определения и их описания: 1. Абстра́кция в ООП 2. Инкапсуляция 3. Наследование 4. Полиморфизм а. это использование только тех характеристик объекта, которые с достаточной точностью представляют его в данной системе. б. в информатике размещение в одном компоненте данных и методов, которые с ними работают. Также может означать скрытие внутренней реализации от других компонентов. в. концепция ООП, согласно которой абстрактный тип данных может наследовать данные и функциональность некоторого существующего типа, способствуя повторному использованию компонентов программного обеспечения. г. способность функции обрабатывать данные разных типов. Ответ: 1а, 2б, 3в, 4г. 8. Соотнесите три операции со стеком с их описанием: 1. push 2. pop 3. peek а. добавление элемента (иначе проталкивание). б. удаление элемента. в. чтение головного элемента. Ответ: 1а, 2б, 3в. 9. Процеду́рное программи́рование — методология программирования, основанная на представлении программы в виде совокупности объектов, каждый из которых является экземпляром определённого класса, а классы образуют иерархию наследования. Ответ: нет. 10. Верно ли следующее утверждение: «Go не предоставляет классы, но предоставляет структуры»? Ответ: да. 11. Если на языке программирования Ruby требуется написать каскад «if-else», то можно ли использовать «elsif»? Ответ: да. 12. Нужно ли закрывать блок «end»-ом в языке программирования Ruby? Ответ: да. 13. Разрешена ли в Python3 такая конструкция: x, y = y, x? Ответ: да. 14. Если «brace = 't'» выполнятся ли выражения стоящие за «if brace not in "()[]"\:»? Ответ: да. 15. Для языка программирования Python3, с помощью какой команды можно подключить математический модуль? 1. import math 2. import math as mh 3. include math 4. load math Ответ: 1, 2. Вопросы открытого типа: Вопросы к ОПК-1: 1. Каким символом обозначается логическое ИЛИ? Ответ: ∨ или + или ||. 2. Каким символом обозначается логическое И? Ответ: ∧ или * или &. 3. Тавтология это. Ответ: в логике, тождественно истинное высказывание, инвариантное относительно значений своих компонентов. 4. Запишите закон тождества. Ответ: A → A или «Из A следует A». 5. Как выглядит закон исключённого третьего. Ответ: (A) ∨ (¬A)или «A или не-A». 6. Что такое «булева» функция от n переменных? Ответ: Функция, зависящая от n аргументов, для которой каждый из аргументов и сама функция принимает только одно из двух «логических» значений: нуль или единица. 7. Сколько различных СДНФ (совершенных дизъюнктивных нормальных форм) имеет одна конкретная булева функция (неравная тождественно нулю)? Ответ: булева функция имеет одну СДНФ. 8. Что понимается под «элиминацией» логических операций в булевой функции? Ответ: Замена логической операции на другие операции с помощью перехода к эквивалентной (равносильной) формуле для этой же булевой функции. 9. Что такое «замкнутый» класс булевых функций? Ответ: Класс (множество) булевых функций F, который совпадает со своим замыканием, т.е. [F]=F. 10. Перечислить состав базиса Жегалкина. Ответ: 1. Функция-константа «ноль»; 2. Функция-константа «единица»; 3. Логическая операция «конъюнкция»; 4. Логическая операция «арифметическая сумма по модулю 2» (другое название «ИСКЛЮЧАЮЩЕЕ ИЛИ»). 11. Как выглядит результирующая функция: (x → y) → y. Ответ: 0001. 12. Как выглядит результирующая функция: (x ∨ y) → y. Ответ: 1101. 13. Как выглядит результирующая функция: (x ∨ y) → (x ∨ y). Ответ: 1111. 14. Как выглядит результирующая функция: (x → y) → (x ∨ y). Ответ: 0111. 15. Как записать «Истину которая следует из чего угодно»: Ответ: x → (y → x). 16. Как записывается первый закон де Моргана? Ответ: a ∧ b = ¬(¬a ∨ ¬b). 17. Как записывается второй закон де Моргана? Ответ: a ∨ b = ¬(¬a ∧ ¬b). 18. Как выглядит результирующая функция: (x ∧ y). Ответ: 0001. 19. Как выглядит результирующая функция: (x ∨ y). Ответ: 1110. 20. Как выглядит результирующая функция: (x ∧ y) → x. Ответ: 1111. Вопросы к ОПК-8: 1. Какой оператор нужно использовать цикле (например в языке программирования Python), если в какой-то момент нужно перейти к следующей итерации, не заканчиваю текущую? Ответ: continue. 2. Если требуется написать функцию «def fc()\:» заглушку (для языка программирования Python), то какое оператор нужно использовать? Напишите его. Ответ: pass. 3. Исправьте строчку «if _name__ == "__main":» (язык программирования Python). Напишите эту строку целиком. Ответ: if __name__ == "__main__":. 4. Напишите строчку для подключения «doctest» (самый простой вариант, язык программирования Python). Напишите эту строку целиком. Ответ: import doctest. 5. Исправьте строчку «with (fileName, 'r as fileCSV:» (язык программирования Python). Напишите эту строку целиком. Ответ: with open(fileName, 'r') as fileCSV:. 6. Исправьте синтаксическую ошибку «for i in range(1, 5)». Напишите эту строку целиком. Ответ: for i in range(1, 5):. 7. Дайте определение "подпись к рядам данных на графике, которая позволяет понять, к каким данным относится одна зависимость, а к каким - другая.": Ответ: Легенда. 8. Напишите команду для вывода легенды в нижнем левом углу графика (Gnuplot) Ответ: set key left bottom. 9. Сколько секунд будет показываться график экспоненты при запуске команды gnuplot -e "plot x; pause 10; plot exp(x); pause 5"?: Ответ: 5. 10. Какой командой задается формат выводного файла (Gnuplot)? Ответ: set terminal или set term. 11. Напишите сколько типов точек есть в gnuplot?: Ответ: 16. 12. Какой модификатор задает цвет точек, напишите его сокращённый вариант (Gnuplot)?: Ответ: lc. 13. Напишите команду, которая задает логарифмический формат графика по координате x (Gnuplot): Ответ: set logscale x. 14. Сколько точек содержит график, построенный приведенной далее командой? В файле 101 строка с данными. plot 'out.dat' every 2::::: using 1:2 with lines linewidth 3: Ответ: 51. 15. Для построения сечений массивов, расположенных в файлах в Gnuplot используют модификатор: Ответ: every. 16. Какая команда используется в Gnuplot для задания параметров: Ответ: set. 17. Со стеком возможны три операции (push, pop, peek) напишите ту, которая добавляет элемент: Ответ: push. 18. Со стеком возможны три операции (push, pop, peek) напишите ту, которая удаляет элемент: Ответ: pop. 19. Со стеком возможны три операции (push, pop, peek) напишите ту, которая читает элемент: Ответ: peek. 20. Напишите термин, который описывает способность функции обрабатывать данные разных типов: Ответ: полиморфизм. Критерии оценивания: «Отлично» (зачтено): студентом дан полный, в логической последовательности развернутый ответ на поставленные вопросы, где он продемонстрировал знания предмета в полном объеме учебной программы, достаточно глубоко осмысливает дисциплину, самостоятельно, и исчерпывающе отвечает на дополнительные вопросы, приводит собственные примеры по проблематике поставленного вопроса. «Хорошо» (зачтено): студентом дан развернутый ответ на поставленный вопрос, где студент демонстрирует знания, приобретенные на лекционных и семинарских занятиях, а также полученные посредством изучения обязательных учебных материалов по курсу, дает аргументированные ответы, приводит примеры, в ответе присутствует свободное владение монологической речью, логичность и последовательность ответа. Однако допускаются неточности в ответе. «Удовлетворительно» (зачтено): студентом дан ответ, свидетельствующий в основном о знании процессов изучаемой дисциплины, отличающийся недостаточной глубиной и полнотой раскрытия темы, знанием основных вопросов теории, слабо сформированными навыками анализа явлений, процессов, недостаточным умением давать аргументированные ответы и приводить примеры, недостаточно свободным владением монологической речью, логичностью и последовательностью ответа. Допускается несколько ошибок в содержании ответа. «Неудовлетворительно» (не зачтено): студентом дан ответ, который содержит ряд серьезных неточностей, обнаруживающий незнание процессов изучаемой предметной области, отличающийся неглубоким раскрытием темы, незнанием основных вопросов теории, неумением давать аргументированные ответы. Выводы поверхностны. Студент не способен ответить на вопросы даже при дополнительных наводящих вопросах преподавателя. |
| 5.2. Темы письменных работ для проведения текущего контроля (эссе, рефераты, курсовые работы и др.) |
| 1. Исчисление высказываний генценовского типа. 2. Исчисление высказываний гильбертовского типа. 3. Алгоритмы проверки общезначимости и противоречивости в ИВ. 4. Элементы теории моделей: Типы и основные классы моделей. 5. Система аксиом Пеано. 6. Нестандартные модели арифметики. |
| 5.3. Фонд оценочных средств для проведения промежуточной аттестации |
| Промежуточная аттестация заключается в проведении в конце семестра зачета/экзамена (для обучающихся, не получивших зачет по результатам текущей успеваемости) по всему изученному курсу. Зачет/экзамен проводится в устной форме по билетам. К зачёту/экзамену допускаются студенты, получившие допуск (сдавшие все лабораторные работы). Теоретические вопросы к зачету/экзамену: 1. Что изучает логика и математическая логика? Компоненты формальных теорий. Что такое высказывание? Логические операции (связки: отрицание, конъюнкция, дизъюнкция, импликация, эквиваленция). 2. Формулы логики высказываний (подформулы). Интерпретация формул. Таблицы истинности для формул. 3. Выполнимые и опровержимые формулы. Тождественно-истинные и тождественно-ложные формулы (тавтологии и противоречия). Теоремы 1 и 2 «о тавтологиях». Наиболее важные тавтологии. Примеры тавтологий и противоречий. 4. Логическая эквивалентность – равносильность формул. Основные равносильности (правила равносильных преобразований). Правило подстановки. Теоремы 1,2,3 «о равносильностях». 5. Формальные теории (ФТ). Состав формальной теории Γ. Выводимость формул: определения «выводимой формулы», «вывода», «теоремы», свойства «сохранения выводимости при добавлении лишних гипотез», интерпретации и «модели множества формул», «модели ФТ». 6. Общезначимость, непротиворечивость, полнота, независимость и разрешимость теории Г: определения общезначимой (тавтологии) и противоречивой формул, формулы «логического следствия» множества формул Г, определения «семантически и формально непротиворечивых» теории Г. Формулировки «метатеорем» о «семантически и формально непротиворечивых» теориях Г (без доказательства). Определения «полной» теории Г, «аксиоматизируемого» множества формул F, «независимой» системы аксиом, «разрешимой и полуразрешимой» теории Г. 7. Исчисление высказываний – формальная теория L: определение ИВ (ее состав). Определения: «формула В - частный случай формулы А», унификатор, «формула С - совместный частный случай формул А и В», унифицируемые формулы и наиболее общий унификатор, частный случай набора формул и совместный частный случай набора формул. 8. Различные аксиоматизации ИВ: Аксиомы Клини. Доказательство Теоремы 1: А->A. Доказательство Теоремы 2: А->(B->A) и ее смысл (производное правило – правило «введения импликации»). 9. Доказательство Теоремы «дедукции». 10. Применимость правила дедукции для более широкого класса ФТ. Следствие 1,Следствие 2 - правило «транзитивности». Следствие 3 - правило «сечения». Доказательство следствий. 11. Некоторые важные теоремы ИВ: ТЕОРЕМЫ (с доказательством): а) теорема «удаления двойного отрицания», б) теорема «введения двойного отрицания», в), г) 1-ая теорема контрапозиции, д) 2-ая теорема контрапозиции, е) , ж). 12. Множество теорем ИВ: доказательство леммы. 13. Множество теорем ИВ: доказательство теоремы полноты и Следствия: Теория L – формально непротиворечива. 14. Исчисление предикатов (ИП) – формальная теория К: определение и состав ИП. Свободное и связанное вхождение переменных в формулы. Контрарные литералы. Определение «свободного терма» в формуле, «чистого и прикладного ИП (ЧИП и ПИП)» 15. Интерпретация ИП: определение, свойства интерпретации (11 свойств, в том числе определения истинной и открытой формул, модели множества формул). 16. Общезначимость: определение и две теоремы "общезначимости". Метатеоремы 1, 2 о полноте ЧИП (без доказательства). 17. Определения «логического следования» и «логической эквивалентности». Некоторые следствия и эквивалентности. 18. Теория равенства: определение и 3 теоремы (с доказательством): 1) рефлексивность; 2) симметричность; 3) транзитивность. Вывод из теории равенства. 19. Формальная арифметика (аксиоматика). 20. Теория абелевых групп (АГ): определения АГ конечного порядка, полной АГ, периодической АГ. Формулировки 2-х Метатеорем Геделя о «неполноте» ПИП 1-го порядка. Вывод из теорем. 21. Автоматическое доказательство теорем (АДТ): постановка задачи, теорема «доказательство от противного» (как основа метода «резолюции»). 22. Сведение формул ИП к предложениям. Теорема «о невыполнимости множества предложений, полученных из противоречия». 23. Правило резолюции (ПР) для ИВ. Теорема (с доказательством): «ПР логично, т.е. резольвента – логическое следствие резольвируемых предложений». 24. Правило резолюции для ИП. 25. Алгоритм АДТ: «опровержение методом резолюций» (3 возможных случая). Вывод в отношении ИП на основании 3-го случая. Пример доказательства (из семинарского занятия) теорем ИВ по алгоритму АДТ «опровержение методом резолюций». Критерии оценивания: «Отлично» (зачтено): студентом дан полный, в логической последовательности развернутый ответ на поставленные вопросы, где он продемонстрировал знания предмета в полном объеме учебной программы, достаточно глубоко осмысливает дисциплину, самостоятельно, и исчерпывающе отвечает на дополнительные вопросы, приводит собственные примеры по проблематике поставленного вопроса. «Хорошо» (зачтено): студентом дан развернутый ответ на поставленный вопрос, где студент демонстрирует знания, приобретенные на лекционных и семинарских занятиях, а также полученные посредством изучения обязательных учебных материалов по курсу, дает аргументированные ответы, приводит примеры, в ответе присутствует свободное владение монологической речью, логичность и последовательность ответа. Однако допускаются неточности в ответе. «Удовлетворительно» (зачтено): студентом дан ответ, свидетельствующий в основном о знании процессов изучаемой дисциплины, отличающийся недостаточной глубиной и полнотой раскрытия темы, знанием основных вопросов теории, слабо сформированными навыками анализа явлений, процессов, недостаточным умением давать аргументированные ответы и приводить примеры, недостаточно свободным владением монологической речью, логичностью и последовательностью ответа. Допускается несколько ошибок в содержании ответа. «Неудовлетворительно» (не зачтено): студентом дан ответ, который содержит ряд серьезных неточностей, обнаруживающий незнание процессов изучаемой предметной области, отличающийся неглубоким раскрытием темы, незнанием основных вопросов теории, неумением давать аргументированные ответы. Выводы поверхностны. Студент не способен ответить на вопросы даже при дополнительных наводящих вопросах преподавателя. |
| 6.1. Рекомендуемая литература | ||||
| 6.1.1. Основная литература | ||||
| Авторы | Заглавие | Издательство, год | Эл. адрес | |
| Л1.1 | Глухов М.М., Шишков А.Б. | Математическая логика. Дискретные функции. Теория алгоритмов: для бакалавров и магистров | СПб.: Лань // ЭБС "Лань", 2012 | e.lanbook.com |
| 6.1.2. Дополнительная литература | ||||
| Авторы | Заглавие | Издательство, год | Эл. адрес | |
| Л2.1 | Лавров И.А., Максимова Л.Л. | Задачи по теории множеств, математической логике и теории алгоритмов.: для бакалавров и магистров | Физматлит, 2002 | biblioclub.ru |
| Л2.2 | Лавров И. А. , Максимова Л. Л. | Задачи и упражнения по математической логике, дискретным функциям и теории алгоритмов.: для бакалавров и магистров | Лань, 2002 | biblioclub.ru |
| 6.2. Перечень ресурсов информационно-телекоммуникационной сети "Интернет" | ||||
| Название | Эл. адрес | |||
| Э1 | МЛТА | portal.edu.asu.ru | ||
| Э2 | Вычислительная математика | portal.edu.asu.ru | ||
| 6.3. Перечень программного обеспечения | ||||
| Для проведения лабораторных занятий необходимо использование компьютерного класса. На компьютерах должны быть установлены программные средства, поддерживающие работу с алгоритмическими языками С/C++, Pascal и т.п. Условия использования: http://www.openoffice.org/license.html LibreOffice Условия использования: https://ru.libreoffice.org/about-us/license/ 7-zip Условия использования: https://www.7-zip.org/license.txt Visual Studio Условия использования: https://code.visualstudio.com/license Python с расширениями PIL, Py OpenGL Условия использования: https://docs.python.org/3/license.html FAR Условия использования: http://www.farmanager.com/license.php?l=ru Acrobat Reader Условия использования: http://wwwimages.adobe.com/content/dam/Adobe/en/legal/servicetou/Acrobat_com_Additional_TOU-en_US-20140618_1200.pdf Mozila FireFox Условия использования: https://www.mozilla.org/en-US/about/legal/eula/ ChromeMicrosoft Office 2010 (Office 2010 Professional, № 4065231 от 08.12.2010), (бессрочно); Microsoft Windows 7 (Windows 7 Professional, № 61834699 от 22.04.2013), (бессрочно); Chrome (http://www.chromium.org/chromium-os/licenses), (бессрочно); 7-Zip (http://www.7-zip.org/license.txt), (бессрочно); AcrobatReader (http://wwwimages.adobe.com/content/dam/Adobe/en/legal/servicetou/Acrobat_com_Additional_TOU-en_US-20140618_1200.pdf), (бессрочно); ASTRA LINUX SPECIAL EDITION (https://astralinux.ru/products/astra-linux-special-edition/), (бессрочно); LibreOffice (https://ru.libreoffice.org/), (бессрочно); Веб-браузер Chromium (https://www.chromium.org/Home/), (бессрочно); Антивирус Касперский (https://www.kaspersky.ru/), (до 23 июня 2024); Архиватор Ark (https://apps.kde.org/ark/), (бессрочно); Okular (https://okular.kde.org/ru/download/), (бессрочно); Редактор изображений Gimp (https://www.gimp.org/), (бессрочно) | ||||
| 6.4. Перечень информационных справочных систем | ||||
| Электронная библиотечная система Алтайского государственного университета (http://elibrary.asu.ru/); Научная электронная библиотека elibrary (http://elibrary.ru | ||||
| Аудитория | Назначение | Оборудование |
|---|---|---|
| 419К | лаборатория информационных технологий - компьютерный класс - учебная аудитория для проведения занятий семинарского типа (лабораторных и(или) практических); проведения групповых и индивидуальных консультаций, текущего контроля и промежуточной аттестации; | Учебная мебель на 17 посадочных мест; рабочее место преподавателя; доска маркерная - 1 шт.; компьютеры: NAIO Corp Z520, НЭТА - 4 in - 13 ед. |
| 001вК | склад экспериментальной мастерской - помещение для хранения и профилактического обслуживания учебного оборудования | Акустический прибор 01021; виброизмеритель 00032; вольтметр Q1202 Э-500; вольтметр универсальный В7-34А; камера ВФУ -1; компьютер Турбо 86М; масспектрометр МРС -1; осциллограф ЕО -213- 2 ед.; осциллограф С1-91; осциллограф С7-19; программатор С-815; самописец 02060 – 2 ед.; стабилизатор 3218; терц-октавный фильтр 01023; шкаф вытяжной; шумомер 00026; анализатор АС-817; блок 23 Г-51; блок питания "Статрон" – 2 ед.; блок питания Ф 5075; вакуумный агрегат; весы; вольтметр VM -70; вольтметр В7-15; вольтметр В7-16; вольтметр ВУ-15; генератор Г-5-6А; генератор Г4-76А; генератор Г4-79; генератор Г5-48; датчик колебаний КВ -11/01; датчик колебаний КР -45/01; делитель Ф5093; измеритель ИМП -2; измеритель параметров Л2-12; интерферометр ИТ 51-30; источник "Агат" – 3 ед.; источник питания; источник питания 3222; источник питания ЭСВ -4; лабораторная установка для настройки газовых лазеров; лазер ЛГИ -21; М-кальк-р МК-44; М-калькул-р "Электроника"; магазин сопротивления Р4075; магазин сопротивления Р4077; микроскоп МБС -9; модулятор МДЕ; монохроматор СДМС -97; мост переменного тока Р5066; набор цветных стекол; насос вакумный; насос вакуумный ВН-01; осциллограф С1-31; осциллограф С1-67; осциллограф С1-70; осциллограф С1-81; осциллоскоп ЕО -174В – 2 ед.; пентакта L-100; пирометр "Промень"; пистонфон 05001; преобразователь В9-1; прибор УЗДН -2Т; скамья оптическая СО 1м; спектограф ДФС -452; спектограф ИСП -51; стабилизатор 1202; стабилизатор 3217 – 4 ед.; стабилизатор 3218; стабилизатор 3222 – 3 ед.; станок токарный ТВ-4; усилитель мощности ЛВ -103 – 4 ед.; усилитель У5-9; центрифуга ВЛ-15; частотомер Ч3-54А; шкаф металлический; эл.двигатель; электродинамический калибратор 11032 |
| Для освоения лекционного материала дисциплины в библиотеке университета имеется в наличии достаточное количество учебников по математической логике и теории алгоритмов. Кроме того, учебное пособие: Шелупанов А.А., Зюзьков В.М. "Математическая логика и теория алгоритмов". Томск: SST, 2001.- 176 c. в электронном варианте, доступное для студентов, имеется на кафедре ВТиЭ (на компьютере)и у преподавателей, ведущих дисциплину "Математическая логика и теория алгоритмов". Задания к семинарским практическим занятиям по курсу "Математическая логика и теория алгоритмов" содержатся в приложении ФОС, в котором приведены тесты для проверки текущих знаний и на образовательном портале по ссылке https://portal.edu.asu.ru/course/view.php?id=4434. Для освоения лекционного материала дисциплины в библиотеке университета имеется в наличии достаточное количество учебников по численным методам и вычислительной математике. Кроме того, учебники: 1. Волков Е.А. Численные методы. – М.: Наука, 1982. – 254 с., 2. Калиткин Н.Н. Численные методы. – М.: Наука; 1978. в электронном варианте, доступные для студентов, имеются на кафедре ВТиЭ (на компьютере)и у преподавателей, ведущих дисциплину "Вычислительная математика". Задания к лабораторным работам по курсу "Вычислительная математика" содержатся в приложении ФОС, а образцы оформления отчетов по выполненным лабораторным работам (в электронном и бумажном вариантах) имеются на кафедре и у преподавателей, ведущих лабораторные занятия. |