ВВЕДЕНИЕ. Дисциплина “Дискретная математика” является составной частью подготовки студентов в области компьютерных технологий

Дисциплина “Дискретная математика” является составной частью подготовки студентов в области компьютерных технологий.

Изучение дисциплины способствует овладению математическими основами профилирующих дисциплин в области синтеза устройств ЭВМ.

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

В первом разделе рассматриваются основные положения теории множеств. Базисом математики служит понятие множества. Оно является универсальным, так как под него можно подвести любую совокупность предметов. С него начинается изложение традиционных математических дисциплин и построение новых математических теорий по мере расширения сферы применения математики.. Кроме того теория множеств служит прочным фундаментом не только математики, но и средством математизации разнообразнейших наук: экономики, биологии, лингвистики и т.д.

Легко определить какое-либо конкретное множество. Определить его – значит относительно любого предмета уметь ответить на вопрос, принадлежит он данному множеству или нет.

Основатель теории множеств немецкий математик Георг Кантор (Cantor) (1845-1918) дал такое определение множества:

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

Т.е. всякое множество однозначно и полностью определяется своими элементами.

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

Когда к формальной логике применили математические методы - появилась математическая логика.

Математическая логика – наука о рассуждениях или доказательствах, проводимых в той или иной формальной теории.

Математическая или формальная логика делится на три подраздела: логику Буля, логику высказываний и логику предикатов.

Логика Буля основывается на отношении эквивалентности, при котором правая часть равенства всегда содержит ровно столько же «истины», сколько и левая.

Третий раздел посвящен формальным теориям, в определении которых, понятия базируются на отношении порядка, при котором правая часть выражения (заключение) содержит больше «истины», чем левая (посылки), т.е. «истинность» заключения оказывается выше «истинности» посылок, о чем можно судить, в частности, по количеству единиц в таблицах истинности.

В четвертом разделе рассматриваются основы теории графов. Граф является важнейшим математическим понятием. На основе теории графов строятся модели разнообразных задач: маршрутизации, распределения ресурсов, дискретной оптимизации и управления, минимизации автоматов и алгоритмов. Стройная система специальных терминов и обозначений теории графов позволяют просто и доступно описывать сложные процессы. Особенно важно наличие наглядной графической интерпретации. Картинки позволяют сразу “усмотреть” суть дела на интуитивном уровне, дополняя и украшая утомительные рациональные текстовые доказательства и сложные формулы.

Пятый раздел посвящен изучению основ кодирования и защиты информации. Ранее средства кодирования играли вспомогательную роль и не рассматривались как отдельный предмет математического изучения. Но с появлением компьютеров ситуация радикально изменилась. Кодирование буквально пронизывает информационные технологии и является центральным вопросом при решении самых разных задач программирования:

- представление данных проищвольной формы в памяти компьютера;

- обеспечение помехоустойчивости при передаче информации по каналам связи;

- сжатие информации в базах данных;

- защита информации от несанкционированного доступа.

В алгоритмах защиты информации широко используется модулярная арифметика. А при кодировании для обеспечения помехоустойчивости – вычисления в конечных полях. Данные вопросы рассматриваются в теории чисел.

В шестом разделе рассматриваются основные элементы теории алгоритмов. Знание основной проблематики данной теории и принципов организации формальных исчислений дает понимание того, что можно и чего нельзя сделать с помощью вычислительной машины.

Дата добавления: 2014-01-06