Методические указания по дисциплине \"дискретная математика\" ( для студентов специальности 22. 01 ) icon

Методические указания по дисциплине "дискретная математика" ( для студентов специальности 22. 01 )



НазваниеМетодические указания по дисциплине "дискретная математика" ( для студентов специальности 22. 01 )
Дата конвертации26.09.2012
Размер50.97 Kb.
ТипМетодические указания
1. /Методичка по ДМ теория/DISKR_01.DOC
2. /Методичка по ДМ теория/DISKR_02.DOC
3. /Методичка по ДМ теория/DISKR_03.DOC
4. /Методичка по ДМ теория/DISKR_04.DOC
5. /Методичка по ДМ теория/DISKR_05.DOC
6. /Методичка по ДМ теория/DISKR_07.DOC
7. /Методичка по ДМ теория/DISKR_08.DOC
8. /Методичка по ДМ теория/DISKR_09.DOC
9. /Методичка по ДМ теория/DISKR_11.DOC
10. /Методичка по ДМ теория/DISKR_13.DOC
11. /Методичка по ДМ теория/DISKR_14.DOC
12. /Методичка по ДМ теория/DISKR_15.DOC
13. /Методичка по ДМ теория/DISKR_16.DOC
14. /Методичка по ДМ теория/DISKR_17.DOC
15. /Методичка по ДМ теория/DISKR_18.DOC
16. /Методичка по ДМ теория/DISKR_19.DOC
17. /Методичка по ДМ теория/DISKR_20.DOC
18. /Методичка по ДМ теория/DISKR_21.DOC
19. /Методичка по ДМ теория/DISKR_22.DOC
20. /Методичка по ДМ теория/DISKR_23.DOC
21. /Методичка по ДМ теория/DISKR_24.DOC
22. /Методичка по ДМ теория/DISKR_25.DOC
23. /Методичка по ДМ теория/Diskr_26.DOC
24. /Методичка по ДМ теория/Diskr_27.DOC
25. /Методичка по ДМ теория/Diskr_28.doc
Методические указания по дисциплине "дискретная математика" ( для студентов специальности 22. 01 )
Операции над множествами
B множество чисел вида; c множество квадратов; это же часть натуральных
Осhовhой приhцип комбиhаторики
Бином Ньютона и полиминальная формула
Число перестановок(соединений) с повторениями
Метод рекуррентных соотношений
html">Принцип включения и исключения
Распределения, разбиения, композиции. Распределение по ячейкам
Графы. Неориентированные графы
Изоморфные графы
Задача о графопостроителе
Игры и графы. Графы используются для записи беспроигрышных стратегий в играх. Игра "побеждает чет", выигрывает тот, кто пользуется графом. Пусть можно брать по 1,2,3,4 предмета из общей суммы 25
Представление графов
Число вершин и ребер графа
Эйлеровы графы
Гамильтоновы цепи и циклы
Называется: 1 связный неограф
Раскраска графов
Сети и потоки. Пусть g = G(X,Г) ориентированный граф без петель, причем каждой его дуге u приписано значение C(U). Если: 1)
Теория информации
Связь теории графов и теории отношений
Соответствие между операциями над отношениями, предикатами и их матрицами
Абстрактная алгебра
Теория формальных грамматик Теория формальных грамматик


МИНИСТЕРСТВО ОБРАЗОВАНИЯ УКРАИНЫ

ДОНЕЦКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ


МЕТОДИЧЕСКИЕ УКАЗАНИЯ

ПО ДИСЦИПЛИНЕ

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

( для студентов специальности 22.01 )


Утверждено

на заседании кафедры ЭВМ

протокол № 6

от ХХ.ХХ.ХХХХ


Донецк ХХХХ

УДК 681.973


МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ДИСЦИПЛИНЕ «ДИСКРЕТНАЯ МАТЕМАТИКА»(для студентов специальности 22.01) в 2-х частях.


Составители : А.Ю.Иванов

А.Г.Кравченко

Ответственный

за выпуск: В.В.Лапко

ЧАСТЬ 1. ТЕОРЕТИЧЕСКИЕ СВЕДЕНИЯ


===================================================

ТЕОРИЯ МНОЖЕСТВ.



Понятию множества нельзя дать строгого определения. Более общего понятия чем множество в математике не существует. Это - "совокупность, собрание, класс, семейство". Часто множество - несколько обьектов, обьедененных общим признаком.

Например:

- множество стульев в комнате;

- множество атомов на Луне;

- множество точек на данной окружности.


Георг Кантор определил: "Множество - многое, мыслимое нами как единое". Предметы, составляющие множeство, называются элементами. Для указания того, что множeство А состоит из элементов х, у ...z пишут А={ х,у.... }. Например: множество арифметических действий состоит из элементов { сложения, вычитания, умножения, деления }. Tо, что элемент х принадлежит множеству А, записывают x  A. Если не принадлежит  x  A.

Например: если А - множество натуральных чисел, то 6  А, а вот 1.3  А.

Если нужно символически записать фразу «множество A состоит из элементов a, обладающих свойством f», то принято писать:.

Символ |A| обозначает количество элементов во множестве A.

Если множество содержит конечное число элементов, то оно конечно. Если множество содержит бесконечное число элементов - оно бесконечно (множество точек на окружности).

Существует 2 способа задания множеств :

1) перечисление всех элементов множества (полный список элементов). Множество студентов группы. Этот способ применим только к конечным множествам.

Первый способ основывается на аксиоме, называемой принципом обьемности (экстенсиональности): всякое множество определяется своими элементами, т.е. два множесва равны в том случае если они состоят из одних и тех же элементом.

Например:

1)А={ 2,4,6 }

В={ 2,4,6 }  А=В

2)Пусть А - множество четных чисел, В - множество всех чисел равных сумме двух нечетных чисел. А и В - бесконечны.

Если из x принадлежит А  x принадлежит В и наоборот то А=В.

Докажем это:

x  A x  B x  B x  A

   

x=2m=(2m-1)+1 x  (2p-1)+(2z-1)=2(p+z-1)

Следовательно: А=В.

1) Если нельзя указать множество с помощью списка - задается характеристическое свойство справедливое для всех элементов множества и только для них. Второй способ задания множеств основан на аксиоме, называемой принципом абстрактности(свертывания). Задание характеристических свойств иногда приводит к сложностям: - когда различные характеристические свойства задают одно и то же множество. Например: множество толстокожих животных, имеющих 2 бивня, совпадает с множеством толстокожих животных, имеющих хобот (слон). - из-за недостаточной четкости языка, неоднозначности человеческой речи. Например, не слишком четко определено множество лиц бесплатно проезжащих в ж/д транспорте. К этому множеству относятся дети до 7 лет. А если 7 лет исполнится в пути ? Множество не содержащее ни одного элемента называется пустым и обозначается 0 ( множество лошадей на Луне, множество действительных корней уравнения .

Оно нужно, когда множество задано своим характеристическим свойством и не известно зарание есть хоть один элемент с этим свойством. До сих пор неизвестно: пусто ли множество всех натуральных n, таких, что для n>2 имеет положительное целочисленные решения (теорема Ферма ). Если в пределах проблемы расматриваются только множества, составленные из элементов некоторого множества, то множество U называется универсальным.

В случае, если приходится рассматривать некоторое множество не самостоятельно, а как часть другого, более широкого множeства, говорят о подмножестве. Множество В является подмножеством А, если каждый элемент х из В является и элементом множества А. Записывается В  А или А  В. Можно говорить также, что B включено в А. Тогда В А.

- Если А В и А  В, то говорят что А строго включено в В, или А - собственное подмножество В.

Для включения нестрогого выполнимы следующие свойства:

1) А  А (рефлексивность);

2) А  В, В  С  А  С (транзитивность);

3) А  В, В  А  А = В (антисиметричность).


Строгое включение обладает только свойством транзитивности. Нельзя смешивать отношения включения и принадлежности, т.к.отношение принадлежности не обладает свойствами рефлексивности и транзитивности. Справедливо: 0  A  U; 0  A  A.

Определим, сколько подмножеств имеет конечное множество (в число подмножеств включим и пустое множество и само множество)?

Множество состоящее из одного элемента а, имеет два подмножества О и { а }.

Множество состоящее из 2-х элементов а и в имеет уже четыре подмножества: О, { а },{ в },{ а,в }.

Множество из 3-х элементов кроме четырёх названых имеет еще 4 подмножества { с },{ а,с },{ в,с },{ а,в,с }.

Поэтому множество, состоящее из n элементов, имеет всего подмножеств. Подмножества можно классифицировать по числу входящих в них элементов.

Если множества содержат n элементов то его подмножества состоящие из к элементов называются сочетаниями из n по к

Так как общее число подмножеств равно то



Если предположить 1  К n, то



Поэтому число выбраных сочетаний равно .

Теперь подсчитаем сколько сочетаний из элементов a1, ... an по к не содержит элемент an. Эти сочетания из элементов a1, ... an-1 .

Так как в сочетание входят к элементов, то число таких сочетаний равно

Т.к. в каждое из сочетаний элемент An либо входит,либо не входит, то утверждение доказано.

Отметим, что при любом n  0, т.к. каждое множество имеет лишь одно пустое подмножество; аналогично,



Пользуясь формулой можно подсчитать при n = 0, 1, 2, ...Такая таблица записывается в виде треугольника Паскаля.













Т.к. =1, то на сторонах треугольника стоят 1. Остальные числа вычисляем по формуле, учитывая, что каждое число равно сумме чисел стоящих в предыдущей строке слева и справа от него. В результате получаем :

1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1









Похожие:

Методические указания по дисциплине \"дискретная математика\" ( для студентов специальности 22. 01 ) iconМетодические указания для студентов специальности Э. 01. 03. 00 «Экономика и управление на предприятии»
Вычислительная техника и программирование. Методические указания для студентов-заочников специальности А. 29. 10. 00 «Строительство...
Методические указания по дисциплине \"дискретная математика\" ( для студентов специальности 22. 01 ) iconМетодические указания к практическим занятиям по дисциплине «бухгалтерский учет» для студентов специальности
Методические указания к практическим занятиям по дисциплине «Бухгалтерский учет» / Сост.: Н. А. Адамов, Г. А. Амучиева; гуу. – М.,...
Методические указания по дисциплине \"дискретная математика\" ( для студентов специальности 22. 01 ) iconМетодические указания и контрольные задания по курсу «Бухгалтерская финансовая отчетность» для студентов специальности 080109 «Бухгалтерский учет, анализ и аудит»
Методические указания предназначены для студентов дневной и вечерней форм обучения
Методические указания по дисциплине \"дискретная математика\" ( для студентов специальности 22. 01 ) iconМетодические указания к курсовому проектированию по дисциплине "инновационный менеджмент" для студентов специальности "Менеджмент организации" 061100
Выполнение курсового проекта по дисциплине “Инновационный менеджмент” является важнейшим практическим этапом изучения дисциплины...
Методические указания по дисциплине \"дискретная математика\" ( для студентов специальности 22. 01 ) iconМетодические указания по подготовке курсовых работ Москва 2002 утверждено
Методические указания подготовлены для студентов, обучающихся по специальности 350 800 "Документоведение и документационное обеспечение...
Методические указания по дисциплине \"дискретная математика\" ( для студентов специальности 22. 01 ) iconМетодические указания для самостоятельной работы студентов по курсу
Методические указания для самостоятельной работы по курсу «Бухгалтерский финансовый учет» тема «Учет операций по налогообложению...
Методические указания по дисциплине \"дискретная математика\" ( для студентов специальности 22. 01 ) iconЮжно-Российский государственный технический университет (Новочеркасский политехнический институт) Шахтинский институт (филиал)
Методические указания предназначены для студентов специальности 071900 «Информационные системы в технике и технологии». Методические...
Методические указания по дисциплине \"дискретная математика\" ( для студентов специальности 22. 01 ) iconМетодические указания к выполнению курсовой работы для студентов специальности 100110. 65 «Домоведение»
Экономика домашнего хозяйства и окружающего социума: методические указания к выполнению курсовой работы / сост.: к филос н., доцент...
Методические указания по дисциплине \"дискретная математика\" ( для студентов специальности 22. 01 ) iconМетодические указания по выполнению лабораторных работ для студентов специальности 220100 «эвм, системы, комплексы и сети» по дисциплине «организация ЭВМ и систем»
Целью лабораторных работ является изучение структуры и принципов функционирования 8 разрядного процессора типа кр580ВМ80
Методические указания по дисциплине \"дискретная математика\" ( для студентов специальности 22. 01 ) iconМолчанов Сергей Валентинович, ст преподаватель каф. «ФиХ»; Волкова Валентина Константиновна, ст преподаватель каф. «ФиХ»; Молчанова Наталья Александровна, врач-биолог муз гбсмп. М 54 методические указания
Методические указания предназначены для студентов дневной формы обучения, изучающих общую химию, в особенности для студентов I курса...
Методические указания по дисциплине \"дискретная математика\" ( для студентов специальности 22. 01 ) iconФедеральное агентство по образованию Российской Федерации южно-российский государственный технический университет
Методические указания предназначены для студентов Шахтинского института (филиала) юргу (нпи) обучающихся по специальности «Триботехника»...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©podelise.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы

Разработка сайта — Веб студия Адаманов