ПРАВИЛА ВЫПОЛНЕНИЯ И ОФОРМЛЕНИЯ

А. Н. Картёжникова

 

ДИСКРЕТНАЯ МАТЕМАТИКА

 

Методические указания и задания

к выполнению контрольной работы

для студентов заочной формы обучения

Направление 230700.62 Прикладная информатика

Профиль «Прикладная информатика в информационной сфере»

 

 

Чита

УДК 519.1

ББК 22.176

К 27

 

Методические указания и задания к выполнению контрольной работы для студентов заочной формы обучения направления 230700.62 Прикладная информатика профиль «Прикладная информатика в информационной сфере» разработаны доцентом кафедры прикладной информатики ЗИП СибУПКА. Н. Картёжниковой в соответствии с требованиями Федерального государственного образовательного стандарта высшего профессионального образования.

 

Рецензент: к.ф.-м.н., доцент кафедры прикладной информатики ЗИП СибУПКЛ. Г. Гомбоев.

 

Методические указания и задания к выполнению контрольной работы для студентов заочной формы обучения направления 230700.62 Прикладная информатика профиль «Прикладная информатика в информационной сфере» обсуждены на заседании кафедры прикладной информатики ЗИП СибУПК. Протокол № 5 от 20.01.2012.

 

Методические указания и задания к выполнению контрольной работы обсуждены и рекомендованы к изданию методическим советом по циклу естественнонаучных дисциплин ЗИП СибУПК. Протокол 7 от 03.03.2012.

Картёжникова, А. Н.

К 27Дискретная математика[Текст] : методические указания и задания к выполнению контрольной работы для студентов заочной формы обучения : направление 230700.62 Прикладная информатика : профиль «Прикладная информатика в информационной сфере»/ А. Н. Картёжникова. – Чита : ЗИП СибУПК, 2012. – 15 с.

УДК 519.1

ББК 22.176

 

 

© Картёжникова А. Н., 2012

© ЗИП СибУПК, 2012

СОДЕРЖАНИЕ

 

 

ВВЕДЕНИЕ 4

1. Содержание курса5

2. Правила выполнения и оформления контрольной

работы8

3. Правила выбора варианта10

4. Методические указания по выполнению контрольной

работы 10

5. Таблица выбора варианта контрольной работы11

6. Задания контрольной работы12

БИБЛИОГРАФИЧЕСКИЙ СПИСОК14

 

ВВЕДЕНИЕ

 

 

Цель изучения дисциплины «Дискретная математика» –вооружить студентов математическим аппаратом, необходимым для создания и эксплуатации современных ЭВМ, средств передачи и обработки информации, автоматизированных систем управления и проектирования.

Задачи дисциплины:

– формирование теоретических знаний по основным разделам курса;

– развитие логического и алгоритмического мышления студентов;

– овладение методами дискретной математики, применяемыми в области информатики и вычислительной техники;

– развитие умения использовать знание основных понятий и предложений дискретной математики при изучении основ алгоритмизации и программирования, информационных технологий, архитектуры ЭВМ и вычислительных систем, компьютерных сетей и других общепрофессиональных и специальных дисциплин;

– выработка умения у студентов самостоятельно расширять математические знания и проводить математический анализ прикладных задач.

 

 

СОДЕРЖАНИЕ КУРСА

Тема 1. Формулы логики. Законы логики

Предмет дискретной математики. Базовые понятия математики, на которые опирается дискретная математика, история развития математики, предпосылки возникновения и истоки развития дискретной математики.

Высказывания и операции над ними. Формулы алгебры высказываний. Истинное и ложное высказывания. Логические операции: отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность.

Понятие формулы логики. Таблица истинности и методика ее построения. Тавтология и противоречие.

Законы алгебры логики. Равносильные формулы. Законы логики. Упрощение формул логики с помощью равносильных преобразований.

Тема 2. Функции алгебры логики

Понятие функции алгебры логики (булева функция). Способы задания булевой функции. Проблема представления булевой функции в виде формулы логики.

Понятие совершенных дизъюнктивной и конъюнктивной нормальных форм. Алгоритмы представления функции в совершенных нормальных формах.

Операция двоичного сложения и ее свойства. Многочлен Жегалкина. Методика представления булевой функции в виде многочлена Жегалкина. Применение булевых функций к релейно-контактным схемам.

 

Тема 3. Теоретико-множественные операции

Множество. Подмножество. Элемент множества. Равные множества. Пустое множество. Конечные, счетные, континуальные множества. Способы представления множеств.

Операции над множествами: объединение, пересечение, дополнение (разность). Абсолютное дополнение.

Диаграммы Эйлера - Венна. Изображение операций над множествами с помощью диаграмм Эйлера - Венна. Свойства операций над множествами. Прямое произведение множеств.

Соответствие между теоретико-множественными и логическими операциями.

 

Тема 4. Метод математической индукции

Дедукция и индукция. Понятие математической (полной) индукции. Доказательство методом математической индукции (теорема). Доказательства тождеств методом математической индукции. Задачи на доказательство неравенств. Доказательство теорем методом математической индукции.

Тема 5. Предикаты и бинарные отношения

Понятие предиката. Логика предикатов. Кванторные опера­ции над предикатами. Формализация предложений с помощью логики предикатов.

Бинарные отношения, их виды. Примеры бинарных отношений. Рефлексивные бинарные отношения. Симметричные бинарные отношения. Транзитивные бинарные отношения. Отношение эквивалентности. Классы эквивалентности. Фактор-множество.

 

Тема 6. Простейшие криптографические шифры

Проблема криптографической защиты информации; понятие шифрования. Примеры простейших криптографических шифров. Приложения алгебры вычетов к простейшим криптографическим шифрам.

 

Тема 7. Графы

Понятие неориентированного графа. Способы задания неориентированного графа. Путь в графе. Цикл в графе. Связный граф. Эйлеровы графы. Гамильтоновы графы. Плоские графы. Деревья и их свойства.

Понятие ориентированного графа (орграфа). Способы задания орграфа. Источник. Сток. Ориентированный путь. Эйлеровы орграфы. Гамильтоновы орграфы.

Понятие ориентированного дерева. Бинарные деревья. Кодирование бинарных деревьев.

 

Тема 8. Элементы теории автоматов

Входной алфавит. Выходной алфавит. Множество состояний.

Таблица автомата. Диаграмма автомата. Словарная функция. Финальная функция автомата.

 

Тема 9. Элементы теории алгоритмов

Вычислимые функции и алгоритмы. Нормальный алгоритм Маркова. Машины Тьюринга.

 

Тема 10. Аксиоматические теории

Понятие аксиоматической теории, примеры, свойства. Понятия формальной и неформальной аксиоматических теорий. Язык и метаязык, теоремы и метатеоремы формальной теории. Интерпретации и модели формальной теории. Семантическая выводимость. Свойства формальных аксиоматических теорий. Формализованное исчисление высказываний как формальная аксиоматическая теория.

ПРАВИЛА ВЫПОЛНЕНИЯ И ОФОРМЛЕНИЯ

КОНТРОЛЬНОЙ РАБОТЫ

При выполнении контрольной работы надо строго придерживаться указанных ниже правил. Работа, выполненная без соблюдения этих правил, не зачитывается и возвращается студенту для переработки.

1. Контрольную работу следует выполнять в тетради чернилами любого цвета, кроме красного, оставляя поля для замечаний рецензента.

2. На обложке тетради должны быть ясно написаны фамилия студента, его инициалы, учебный номер (шифр), номер контрольной работы, название дисциплины. Здесь же следует указать дату отсылки работы в институт и адрес студента. В конце работы следует поставить дату ее выполнения и расписаться.

3. В работу должны быть включены задачи, указанные в задании, строго по своему варианту. Контрольные работы, содержащие не все задания, а также содержащие задачи не своего варианта, не зачитываются.

4. Решения задач надо располагать в порядке номеров, указанных в заданиях, сохраняя номера задач.

5. Перед решением каждой задачи надо записать полностью ее условие.

6. Решения задач следует излагать подробно и аккуратно, объясняя и мотивируя все действия по ходу решения и делая необходимые чертежи.

7. После получения прорецензированной работы как незачтенной, так и зачтенной, студент должен исправить все отмеченные ошибки и недочеты и выполнить все рекомендации рецензента.