ВУЗ: Украинский Государственный химико-технологический Университет
Категория: Методичка
Дисциплина: Математика
Добавлен: 29.10.2019
Просмотров: 2200
Скачиваний: 5
СОДЕРЖАНИЕ
Лабораторная работа № 1 Операции над множествами
Лабораторная работа № 2 Отношения и функции.
Цель работы: Изучить основные определения отношений и функций и научиться определять их свойства
Лабораторная работа № 4 Алгебраические структуры
Лабораторная работа № 5 Элементы комбинаторики
Лабораторная работа №6 Основные понятия теории графов
Лабораторная работа № 7 Кратчайшие пути в графе
Лабораторная работа № 9 Определение максимального течение в транспортной сети
Теперь перейдем к рассмотрению структур , которые имеют более, чем одну операцию.
1. Кольцом называется множество F с двумя определенными на нем бинарными операциями Ä и Å такими что:
Ä ассоциативна ; x Ä (y Ä z) = (x Ä y) Ä z " x,y,z Î F
Å ассоциативна ; x Å (x Å y) = ( x Å y) Å z "x,y,z Î F
Å коммутативна; x Å y = y Å x " x,y Î F
Å имеет единицу, которая называется нулем и обозначается 0; x Å 0 = x " xÎF
существуют обратные элементы относительно Å; –x x Å (- x) = 0
Ä дистрибутивна по отношению к Å.
x Ä (y Å z) = (x Ä y) Å (x Ä z) " x,y,z ÎF
Можно утверждать, что структура (Zn , * , +) " n Î N является кольцом .
Будем говорить , что кольцо коммутативно, если Ä коммутативна , и является кольцом с единицей, если существует единица относительно Ä .
(Zn , * ,+) – коммутативное кольцо с единицей " nÎN.
2. Полем называется множество F с двумя определенными на нем бинарными операциями Ä и Å такими что:
Å ассоциативна: x Å (x Å y) = ( x Å y) Å z "x,y,z Î F
Å коммутативна: x Å y = y Å x " x,y Î F
существует единица по отношению к Å , обозначаемая 0 x Å 0 = x " xÎF
существуют обратные элементы –x по отношению к Å x Å (- x) = 0
Ä ассоциативна: x Ä (y Ä z) = (x Ä y) Ä z " x,y,z Î F
Ä коммутативна: x Ä y = y Ä x " x,y Î F
существует единица по Ä обозначаемая 1 x Ä 1 = x¢ " xÎF
Ä дистрибутивна по отношению к Å: x Ä (y Å z) = (x Ä y) Å (x Ä z) " x,y,z Î F
существуют обратные элементы по Ä: " xÎF \ {0} $ y Î F: x Ä y = 1 обозначается y = x-1.
Например множество вещественных чисел с операциями сложения и умножения - (R, * , +) является полем.
3. Решеткой называется множество F с двумя определенными на нем бинарными операциями Ä и Å такими что:
Ä и Å - коммутативны: x Ä y = y Ä x x Å y = y Å x " x,y Î F
Ä и Å - ассоциативны: x Ä (y Ä z) = (x Ä y) Ä z x Å (x Å y) = ( x Å y) Å z "x,y,z Î F
Ä и Å - идемпотентны: x Ä x = x x Å x = x " x Î F
Ä и Å обладают свойствами поглощения: x Ä (x Å y) = x x Å (x Ä y) = x " x,y Î F
Примером решетки может служить множество целых чисел с операциями максимума и минимума из двух чисел.
Решетка называется дистрибутивной, если операции Ä и Å дистрибутивны относительно друг друга: x Ä (y Å z) = (x Ä y) Å (x Ä z) x Å (y Å z) = (x Å y) Ä (x Å z) " x,y,z Î F
Решетка называется ограниченной, если в ней существует точная верхняя (sup) и точная нижняя грань (inf): x Ä inf = inf x Å sup = sup " x Î F
Ограниченная решетка называется решеткой с дополнениями, если для всех элементов из F существуют дополнения x’Î F: x Ä x’ =inf x Å x’ = sup " x Î F.
Дистрибутивная ограниченная решетка с доплолнениями называется Булевой алгеброй. Примером Булевой алгебры служит булеан любого множества с определенными на нем операциями пересечения, объединения и дополнения.
Задания
-
На множестве Т задать операцию так, чтобы алгебра ( T,* ) была полугруппой
-
На множестве Т задать операцию так, чтобы алгебра ( T,* ) была моноидом.
-
На множестве Т задать операцию так, чтобы алгебра ( T,* ) была группой.
Варианты заданий:
-
T = { t1, t2, t3 }
-
T = { s1, s2, s3, s4 }
-
T = {1, 2, 3, 4}
-
T = {a, b, c, d}
-
T = {@, #, $, %}
-
T = {begin, end, do, for}
-
T = {куб, шар, конус, сфера}
-
T = {кот, собака, корова, курица}
-
T = { aa, ab, ba, bb}
-
T = {11, 12, 21, 22}
-
T = {s, ss, sss, ssss}
-
T = {+, -, *, /}
-
T = {<, >, <=, >=}
-
T = {1, 10, 100, 1000}
-
T = {, , , }
-
T = {кот, собака, корова, курица}
-
T = { aa, ab, ba, bb}
-
T = {11, 12, 21, 22}
-
T = {s, ss, sss, ssss}
-
T = {+, -, *, /}
-
Пусть задано множество T = { 1, 2, 3, 4 }. Установить тип алгебраической системы ( T,* ), где * - операция на множестве Т, задана следующей таблицей:
|
1) |
|
|
|
|
|
|
2) |
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
2 |
3 |
4 |
1 |
|
|
1 |
1 |
2 |
3 |
4 |
|
|
|
2 |
3 |
4 |
1 |
2 |
|
|
2 |
2 |
2 |
3 |
4 |
|
|
|
3 |
4 |
1 |
2 |
3 |
|
|
3 |
3 |
3 |
3 |
3 |
|
|
|
4 |
1 |
2 |
3 |
4 |
|
|
4 |
4 |
2 |
3 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3) |
|
|
|
|
|
|
4) |
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
2 |
2 |
3 |
1 |
|
|
1 |
1 |
2 |
3 |
4 |
|
|
|
2 |
1 |
3 |
3 |
2 |
|
|
2 |
2 |
3 |
1 |
4 |
|
|
|
3 |
1 |
2 |
1 |
3 |
|
|
3 |
3 |
1 |
4 |
1 |
|
|
|
4 |
1 |
2 |
3 |
4 |
|
|
4 |
4 |
2 |
1 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
5) |
|
|
|
|
|
|
6) |
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
1 |
2 |
3 |
4 |
|
|
1 |
4 |
2 |
1 |
2 |
|
|
|
2 |
1 |
2 |
1 |
3 |
|
|
2 |
3 |
1 |
4 |
1 |
|
|
|
3 |
1 |
3 |
3 |
2 |
|
|
3 |
2 |
3 |
1 |
4 |
|
|
|
4 |
2 |
2 |
3 |
1 |
|
|
4 |
1 |
2 |
3 |
4 |
|
|
7) |
|
|
|
|
|
|
8) |
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
1 |
2 |
3 |
4 |
|
|
1 |
1 |
2 |
3 |
4 |
|
|
|
2 |
1 |
2 |
3 |
4 |
|
|
2 |
2 |
2 |
3 |
4 |
|
|
|
3 |
1 |
2 |
3 |
4 |
|
|
3 |
3 |
3 |
3 |
3 |
|
|
|
4 |
1 |
2 |
3 |
4 |
|
|
4 |
4 |
2 |
3 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
9) |
|
|
|
|
|
|
10) |
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
1 |
1 |
1 |
1 |
|
|
1 |
1 |
2 |
3 |
4 |
|
|
|
2 |
2 |
2 |
2 |
2 |
|
|
2 |
2 |
3 |
1 |
4 |
|
|
|
3 |
3 |
3 |
3 |
3 |
|
|
3 |
3 |
1 |
4 |
1 |
|
|
|
4 |
4 |
4 |
4 |
4 |
|
|
4 |
4 |
2 |
1 |
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
11) |
|
|
|
|
|
|
12) |
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
4 |
4 |
4 |
4 |
|
|
1 |
1 |
2 |
3 |
4 |
|
|
|
2 |
3 |
3 |
3 |
3 |
|
|
2 |
2 |
2 |
3 |
4 |
|
|
|
3 |
2 |
2 |
2 |
2 |
|
|
3 |
3 |
3 |
3 |
3 |
|
|
|
4 |
1 |
1 |
1 |
1 |
|
|
4 |
4 |
2 |
3 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
13) |
|
|
|
|
|
|
14) |
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
4 |
3 |
2 |
1 |
|
|
1 |
1 |
2 |
3 |
4 |
|
|
|
2 |
4 |
3 |
2 |
1 |
|
|
2 |
2 |
3 |
1 |
4 |
|
|
|
3 |
4 |
3 |
2 |
1 |
|
|
3 |
3 |
1 |
4 |
1 |
|
|
|
4 |
4 |
3 |
2 |
1 |
|
|
4 |
4 |
2 |
1 |
2 |
|
|
15) |
|
|
|
|
|
|
16) |
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
2 |
3 |
4 |
1 |
|
|
1 |
1 |
2 |
3 |
4 |
|
|
|
2 |
3 |
4 |
1 |
2 |
|
|
2 |
2 |
2 |
3 |
4 |
|
|
|
3 |
4 |
1 |
2 |
3 |
|
|
3 |
3 |
3 |
3 |
3 |
|
|
|
4 |
1 |
2 |
3 |
4 |
|
|
4 |
4 |
2 |
3 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
17) |
|
|
|
|
|
|
18) |
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
2 |
2 |
3 |
1 |
|
|
1 |
1 |
2 |
3 |
4 |
|
|
|
2 |
1 |
3 |
3 |
2 |
|
|
2 |
2 |
3 |
1 |
4 |
|
|
|
3 |
1 |
2 |
1 |
3 |
|
|
3 |
3 |
1 |
4 |
1 |
|
|
|
4 |
1 |
2 |
3 |
4 |
|
|
4 |
4 |
2 |
1 |
2 |
|
|
19) |
|
|
|
|
|
|
20) |
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
1 |
2 |
3 |
4 |
|
|
1 |
1 |
2 |
3 |
4 |
|
|
|
2 |
1 |
2 |
3 |
4 |
|
|
2 |
2 |
2 |
3 |
4 |
|
|
|
3 |
1 |
2 |
3 |
4 |
|
|
3 |
3 |
3 |
3 |
3 |
|
|
|
4 |
1 |
2 |
3 |
4 |
|
|
4 |
4 |
2 |
3 |
4 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
-
Установить свойства операций и тип алгебраической системы
N - множество натуральных чисел; Z - множество целых чисел; R – множество действительных чисел; Q - множество рациональных чисел; + - сложение; * - умножение; - -вычитание; / - деление
-
{N, + ,*}
-
{N, + }
-
{N, +,*}
-
{Z, + ,*}
-
{Z, + }
-
{Z,*}
-
{Q, + ,*}
-
{Q, + }
-
{Q, *}
-
{R, + ,*}
-
{R, + }
-
{R, *}
-
{Q, - ,*}
-
{Z, - ,*}
-
{N, + ,-}
-
{N, - ,*}
-
{N, - }
-
{N, -,*}
-
{R, - ,*}
-
{Q, - ,*}
Контрольный тест
-
1. Определить, является ли операция x°y=y/(x-1) замкнутой на множестве Z:
-
да
-
нет
2. Определить свойства операции x°y=2xy-5, заданной на множестве Z:
а) коммутативность +
ассоциативность -
единица -
обратный элемент -
б) коммутативность +
ассоциативность -
единица +
обратный элемент +
в) коммутативность -
ассоциативность +
единица -
обратный элемент -
г) коммутативность -
ассоциативность -
единица -
обратный элемент -
3. Определить свойства операции x°y=min(x,x-y), заданной на множестве Z:
а) коммутативность +
ассоциативность -
единица -
обратный элемент -
б) коммутативность -
ассоциативность +
единица -
обратный элемент -
в) коммутативность -
ассоциативность -
единица +
обратный элемент +
г) коммутативность -
ассоциативность -
единица -
обратный элемент -
4. Определить свойства операций, заданной
на множестве {a,b,c}
а) коммутативность +
ассоциативность +
единица +
обратный элемент +
б) коммутативность +
ассоциативность +
единица +
обратный элемент -
в) коммутативность +
ассоциативность +
единица -
обратный элемент -
г) коммутативность -
ассоциативность -
единица -
обратный элемент -
5. Определить тип алгебры ({a,b,c}, °) где ° задано таблицей ;
-
полугруппа
-
моноид
-
группа
-
абелева группа
6. Определить тип алгебры (N, min(x,y)) ;
-
полугруппа
-
моноид
-
группа
-
абелева группа
7. Определить тип алгебры ({истина, ложь}, and, or);
-
кольцо
-
поле
-
решетка
-
булева алгебра
8. Найти единицу для операции x°y=2x-5y+1, заданной на множестве Z ;
-
1
-
x+1
-
нет
-
5
9. Определить тип алгебры ({0, 1}, min (x, y), max (x, y)) ;
-
кольцо
-
поле
-
решетка
-
булева алгебра
10. Определить тип алгебры ({0, 1, 2}*, +)
-
кольцо
-
поле
-
решетка
-
булева алгебра
11.Определить тип алгебры ( С, +,*), где С – множество комплексных чисел;
-
кольцо
-
поле
-
решетка
-
булева алгебра
12. Найти единицу для операции
,
(x,y)€{x:x>=0,x€R}
;
-
правая единица
-
левая единица
-
единица 0
-
нет единиц
13. Определить тип алгебры ({1, 2, 3}, min(x, y));
-
полугруппа
-
моноид
-
группа
-
абелева группа
14. Определить свойства операции сложения квадратных матриц, элементами которых являются целые числа;
а) коммутативность +
ассоциативность +
единица +
обратный элемент +
б) коммутативность +
ассоциативность +
единица -
обратный элемент -
в) коммутативность -
ассоциативность +
единица +
обратный элемент -
г) коммутативность -
ассоциативность -
единица -
обратный элемент -
15. Определить свойства операции умножения квадратных матриц, элементами которых являются целые числа;
а) коммутативность +
ассоциативность +
единица +
обратный элемент +
б) коммутативность +
ассоциативность +
единица -
обратный элемент -
в) коммутативность -
ассоциативность +
единица +
обратный элемент -
г) коммутативность -
ассоциативность -
единица -
обратный элемент -
Лабораторная работа № 5 Элементы комбинаторики
Цель работы:
Теоретические сведения
Комбинаторика изучает вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов.
Комбинаторные задачи бывают самых различных видов. Но большинство задач решается с помощью двух основных правил – правила суммы и произведения.
Если некоторый объект a можно выбрать m способами, а другой объект b можно выбрать n способами, то выбор одного из этих объектов (либо a, либо b) можно осуществить
N = m + n способами.
При использовании правила суммы следует иметь ввиду, что ни один из способов выбора объекта a не должен совпадать с каким-либо способом выбора объекта b. Если же совпадение имеют место, то правило суммы теряет силу, и из суммарного числа (m + n) выборов следует вычесть число k таких совпадений:
N = m + n – k.
Если некоторый объект a можно выбрать m способами, а другой объект b можно выбрать n способами, причем ни один из способов выбора объекта b не зависит от того, как выбран объект a, то выбор этих двух объектов (a и b) можно осуществить
N = m * n способами.
Правило суммы и произведения обобщаются на произвольное число.
Пусть
- множество из n элементов.
Размещениями из n элементов по m
называют упорядоченные m – элементные
подмножества множества
из
n элементов.
Два различных размещения из данных n
элементов, взятых по m, различаются либо
составом входящих в них элементов, либо
(при одном и том же составе элементов)
порядком их расположения. Число всех
размещений из n элементов по m обозначают
A
и вычисляют по формуле:
A
=
Различные упорядоченные множества,
полученные из
,
которые отличаются лишь порядком
элементов, называются перестановками
множества
.
Число всех перестановок из n элементов
обозначают P
и вычисляют по формуле:
P
= n!.
Сочетанием
из n элементов по m называется произвольное
m - элементное подмножество множества
из n элементов. Два различных сочетания
из данных n элементов, взятых по m,
отличаются составом входящих в них
элементов: если два сочетания различны,
то в одном из них содержится хотя бы
один элемент, не содержащийся в другом.
Порядок элементов в подмножестве не
существенен. Число сочетаний (m –
элементных подмножеств множества из n
элементов, где 0
m
n) обозначают C
и вычисляют по формуле:
C
=
A
=
.
Число
различных перестановок, которые можно
составить из n элементов, среди которых
имеются n
элементов 1-го типа, n
элементов 2-го типа и т.д., n
элементов k-го типа, равно
P
(n
,
…, n
)
=
, (n
+ n
+…+
n
= n).
Сочетаниями из n элементов по m с повторениями называются группы, содержащие m элементов, причем каждый элемент принадлежит одному из n типов.
Число сочетаний с повторениями
обозначается
и вычисляется по формуле:
= C
= C
=
Число размещений с повторениями
обозначается
и вычисляется по формуле:
= n
Задания
-
Определить количество размещений с неограниченными повторениями объема m из n различных элементов.
-
Определить количество m-перестановок из n различных элементов
-
Определить количество перестановок из n различных элементов.
-
Определить число заполнений m предметов в n различных ячейках.
Варианты заданий:
-
n=10, m=2;
-
n=10, m=3;
-
n=10, m=4;
-
n=10, m=5;
-
n=9, m=2;
-
n=9, m=3;
-
n=9, m=4;
-
n=9, m=5;
-
n=8, m=2;
-
n=8, m=3;
-
n=8, m=4;
-
n=8, m=5;
-
n=11, m=2;
-
n=11, m=3;
-
n=11, m=4;
-
n=11, m=5;
-
n=9, m=5;
-
n=8, m=2;
-
n=8, m=3;
-
n=8, m=4;
-
n=8, m=5;
-
n=11, m=2;
-
n=11, m=3;
-
n=11, m=4
-
n=11, m=5;
Решить 4 задачи по индивидуальному заданию
Контрольный тест
1. Для записи целого числа в компьютере используется 2 байта - 16 двоичных знаков. Первый из них отведен на знак числа (+ или -), а остальные содержат модуль числа. Сколько различных целых чисел может использовать компьютер?
-
512
-
65536
-
256
-
1024
2. Сколько различных вариантов можно получить бросая пять игральных костей?
-
288
-
638
-
1252
-
36
3. Сколько существует различных шестизначных номеров, начинающихся на 38?
-
531441
-
1000000
-
10000
-
6561
4. Сколько существует различных трехзначных чисел, сумма цифр которых равна 3?
-
3
-
6
-
9
-
12
5. В парламентскую комиссию необходимо выбрать пять человек. Среди кандидатов 5 представителей партии №1, 3 представителя партии №2, и 4 партии №3. Сколько разных комиссий можно составить, если представители партии №1 и №2 не могут быть ее членами одновременно.
-
115
-
164
-
220
-
140
6. В парламентскую комиссию необходимо выбрать пять человек. Среди кандидатов 5 представителей партии №1, 3 представителя партии №2, и 4 партии №3. Сколько разных комиссий можно составить, если в нее должен входить по крайней мере один представитель партии №3.
-
115
-
164
-
330
-
105
7. Сколькими способами можно расставить 8 черных шашек на белых полях шахматной доски..
-
10518300
-
1642738
-
27352000
-
951730
8. Сколько различных слов можно получить из слова АБРАКАДАБРА.
-
123350
-
7650
-
83160
-
15120
9. Сколько различных слов можно получить из слова АБРАКАДАБРА, если обе буквы ББ будут стоять рядом?
-
123350
-
15120
-
7650
-
83160
10. Вычислить число размещений из 8 по 5 без повторений.
-
6719
-
6720
-
6721
-
6722
11. Вычислить число сочетаний из 9 по 2 без повторений.
-
16
-
25
-
36
-
40
12. Вычислить число размещений из 7 по 2 с повторениями.
-
128
-
96
-
64
-
49
13. Вычислить число сочетаний из 6 по 5 с повторениями.
-
288
-
256
-
512
-
200
14. Вычислить число перестановок из 8 предметов.
-
8
-
128
-
256
-
40320
15. Сколько существует различных нечетных четырехзначных чисел, читающихся одинаково слева и справа.
-
40
-
50
-
90
-
45