Понятие двоичной функции и способа ее задания.
Стр 1 из 7Следующая ⇒ МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ для студентов факультета повышения квалификации
Москва 2016 План УМД 2015/2016 уч. г. Методические указания и контрольные задания по курсу МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ Составители: В.О. Мелихов, доцент А.Н Кироев, аспирант. В данной методической разработке приведены бюджет времени студента, рабочая программа, содержание лекций и упражнений, методические указания по разделам курса, задания на контрольные работы. Издание утверждено на заседании кафедры. Отв.редактор В.Н.Шакин, доцент Рецензент д.т.н. И.П Кузнецов. Содержание Введение.................................................................................................................................... 4 1. Математическая логика....................................................................................................... 6 1.1. Понятие двоичной функции и способа ее задания.................................................... 6 1.2. Одноместные и двухместные двоичные функции..................................................... 7 1.3. Алгебра двоичных функций......................................................................................... 9 1.4. Совершенная дизъюнктивная нормальная форма.................................................... 11 1.5. Совершенная конъюнктивная нормальная форма.................................................... 12 1.6. Базисы функций алгебры логики............................................................................... 12 1.7. Полином Жегалкина.................................................................................................... 13 1.8. Существенные и несущественные переменные....................................................... 14 1.9. Минимизация функций алгебры логики................................................................... 15 1.9.1. Структурный метод карт Карно........................................................................... 15 1.9.2. Метод Блейка......................................................................................................... 18
2. Основы теории алгоритмов.............................................................................................. 22 2.1. Понятие алгоритма и связанных с ним категорий................................................... 22 2.2. Машина Тьюринга....................................................................................................... 22 2.3. Тезис Тьюринга............................................................................................................ 25 2.3.1. Композиция МТ..................................................................................................... 25 2.3.2. Разветвление МТ.................................................................................................... 25 2.4. Вычислительная сложность алгоритмических проблем.......................................... 26 Список рекомендуемой литературы.................................................................................... 28 Правило выбора варианта Контрольных работ и пример выполнения........................... 29 Контрольная работа................................................................................................................ 31 Введение Целью данного курса является освоение теоретических основ таких разделов дискретной математики как Математическая логика и Теория алгоритмов. Курс "Математическая логика и Теория алгоритмов" посвящен изучению элементов математического аппарата, предназначенного для описания дискретно изменяющихся величин, объектов, систем и процессов таких, например, как вычислительные системы и процессы. Изучение курса включает освоение фундаментальных понятий алгебры логики, теории формальных алгоритмов и вычислительной сложности. В соответствии с содержанием курса данный сборник включает две части, посвященные соответственно изучению функций алгебры логики и теоретических основ формальных алгоритмов. Организация учебного материала, представленного в сборнике, полностью соответствует стандарту изложения математических дисциплин для инженерно-технических и вычислительных специальностей и направлений подготовки. Объем учебных задач и требования к их выполнению позволяют получить необходимые практические навыки в работе с функциями алгебры логики, а также изучить свойства формальных алгоритмов.
Постановке контрольных заданий предшествует краткое изложение теоретического материала. По каждому из разделов приводятся ссылки на рекомендуемые для изучения литературные источники. Изучение Математической логики в рамках дисциплины включает определение функций алгебры логики (ФАЛ) и способов их задания. Устанавливается связь ФАЛ с импульсными схемами. Учащиеся осваивают алгоритмы построения ФАЛ в виде совершенных формы и полинома Жегалкина. Определяется понятие базисного набора ФАЛ, доказывается эквивалентность базисов. Исследуется существенность двоичных переменных. Подробно рассматриваются вопросы структурной и аналитической минимизации ФАЛ. На основе полученных представлений фундаментальное понятие алгоритма характеризуется с позиций теории формальных алгоритмических моделей и вычислительной сложности. В рамках дисциплины студенты знакомятся с возможностями описания алгоритмов по Тьюрингу, по Черчу и по Маркову, раскрывающими соответственно аппаратные и функциональные и лингвистические аспекты понятия алгоритма. С помощью понятий недетерминированной машины Тьюринга проводится разделение алгоритмических проблем по трудоемкости. В результате освоения материалов курса студенты обучаются основным приемам представления и исследования функций алгебры логики приобретают практические навыки построения формальных алгоритмических моделей. Учащиеся должны уметь выделять основные элементы описания алгоритмической проблемы, правильно ориентироваться в вопросах вычислительной сложности алгоритмов. Изучаемый курс закладывает математические основы, необходимые при освоении теории кодирования, теории автоматов, методов структурного синтеза импульсных устройств, а также методов автоматизации проектирования вычислительных систем
Студенты технических факультетов МТУСИ в течение третьего семестра выполняют одну контрольную работу, в которой должны быть выполнены задания 1-3 и сдают экзамен. Бюджет времени (в часах)
Рабочая программа
Математическая логика Понятие двоичной функции и способа ее задания. Математической логикой называется раздел математики занимающийся изучением общих законов построения и применения двоичных функций. Двоичной функцией
Совокупность переменных
Ясно, что двоичная функция от n - переменных будет определена на Можно сказать, что набор переменных представляет свой номер в виде двоичного числа. А естественный порядок наборов соответствует расстановке наборов по возрастанию их номеров. Таблица 1
Функциональность соответствия Т.к. значениями
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|