Тема 1. Введение.

План:

1.      Определение и роль дискретной математики.

2.      Связь дискретной математики с другими науками

Цель:   Знакомство понятием "Дискретная математика". Установление роли дискретной математики как составляющего элемента в математической подготовке специалистов в области информатики и компьютерных технологий.

1. Определение и роль дискретной математики.

Дискретная математика - совокупность математиче­ских дисциплин, изучающих свойства абстрактных дискретных объектов, т.е. свойства математических моделей объектов, про­цессов, зависимостей, существующих в реальном мире, которы­ми оперируют в различных областях знаний. Таким образом, дис­кретный анализ - самостоятельный раздел современной мате­матики, изучающий свойства различных структур, имеющих ко­нечный характер. Они могут возникать как в самой математике, так и в ее приложениях. К их числу принято относить объекты, имеющие прерывный (дискретный) характер в отличие от объек­тов, изучаемых классической математикой и носящих непрерыв­ный характер.

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

Дискретная математика или дискретный анализ -сравнитель­но новое направление в математике, объединяющее отдельные ее разделы, ранее сформированные как самостоятельные теории. К ним относятся математическая логика и теории множеств, гра­фов, кодирования, автоматов.

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

Деление математики на дискретную и класси­ческую математику достаточно условно. Например, аппарат теории множеств и теории графов используется при изучении не только дискретных, но и непрерывных объектов. С другой стороны, сама дискретная математика использует средства, разработанные в классической математике. Однако характер объектов, исследуемых дискретной математикой, настолько своеобразен, что методов классической математики не всегда достаточно для их изучения.

Несмотря на то, что отдельные направления дискретной мате­матики зародились в глубокой древности и совершенствовались параллельно с классической математикой, наиболее интенсив­но дискретная математика стала развиваться в последнее столе­тие. В настоящее время знание дискретной математики необхо­димо специалистам в различных областях деятельности.

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

Стимулом для развития многих направлений дискретной мате­матики явились запросы теоретической кибернетики, непосред­ственно связанной с развитием ЭВМ.

Теоретическая кибернетика занимается изучением разнообраз­ных практических проблем средствами дискретной математики:

~  Растущий поток информации и проблемы ее передачи, обра­ботки и хранения привели к возникновению и развитию теории кодирования;

~  Различные экономические задачи, задачи электротехники сти­мулировали создание и развитие теории графов;

~  Связь релейно-контактных схем с формулами алгебры логики и их использование для описания функционирования автоматов дали начало развитию и применению математической логики и теории автоматов. Математическая логика в широком смысле изучает основания математики, принципы построения матема­тических теорий.

Дискретная математика изучает объекты, которые порой не имеют ни физической, ни числовой интерпретации. В классиче­ской математике характеристики реальных объектов можно представить в виде чисел, а закономерности - в виде соотношений. В отличие от реальных характеристиками информационных объек­тов могут служить понятия "структура", "отношение", "связь". Обычно объекты информатики рассматривают как комбинации некоторых абстрактных символов, над которыми производятся некие манипуляции.

Тема 2. Множества

План:

1.            Общие понятия теории множеств.

2.            Основные операции над множествами 

3.            Кортежи

4.            Декартово произведение множеств

5.            Соответствия между множествами.

6.            Отображения

7.            Бинарные отношения

8.            Элементы комбинаторики

9.            Подстановки

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

Теоретические сведения

1. Общие понятия теории множеств.

Понятие "Множество " является одним из  основных понятий математики. Это понятие в явном виде не определяется, хотя на интуитивном уровне его можно описать, задать. Над множествами можно  выполнять многие операции, которые будут рассмотрены при изучении этой темы. 

Под множеством можно понимать - неупорядоченную совокупность элементов, набор объектов.

Задание 3. Выписать все подмножества трехэлементного множества S={a,b,c}

Решение. a, b, c, ab, ac, bc, abc, Æ. Всего  k=2³=8 подмножеств.

Задание 4. Запишите несколько подмножеств для множеств:

D= {10, 11, 12 …98, 99} – множество натуральных двузначных чисел,

F= {10, 20… 90} - множество чисел, оканчивающихся нулем.

Установите число подмножеств каждого множества

Решение.  Всего 90 двузначных чисел, значит k₁=2⁹⁰ количество возможных подмножеств. Чисел, оканчивающихся нулем – 9 штук, значит k₂=2⁹=512 возможных подмножеств