Материал: Лабораторные работы по ДМ

Скачать

Заказать новую работу

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

Теперь перейдем к рассмотрению структур , которые имеют более, чем одну операцию.

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.

Дистрибутивная ограниченная решетка с доплолнениями называется Булевой алгеброй. Примером Булевой алгебры служит булеан любого множества с определенными на нем операциями пересечения, объединения и дополнения.



Задания

  1. На множестве Т задать операцию так, чтобы алгебра ( T,* ) была полугруппой


  1. На множестве Т задать операцию так, чтобы алгебра ( T,* ) была моноидом.


  1. На множестве Т задать операцию так, чтобы алгебра ( T,* ) была группой.


Варианты заданий:

  1. T = { t1, t2, t3 }

  2. T = { s1, s2, s3, s4 }

  3. T = {1, 2, 3, 4}

  4. T = {a, b, c, d}

  5. T = {@, #, $, %}

  6. T = {begin, end, do, for}

  7. T = {куб, шар, конус, сфера}

  8. T = {кот, собака, корова, курица}

  9. T = { aa, ab, ba, bb}

  10. T = {11, 12, 21, 22}

  11. T = {s, ss, sss, ssss}

  12. T = {+, -, *, /}

  13. T = {<, >, <=, >=}

  14. T = {1, 10, 100, 1000}

  15. T = {, , , }

  16. T = {кот, собака, корова, курица}

  17. T = { aa, ab, ba, bb}

  18. T = {11, 12, 21, 22}

  19. T = {s, ss, sss, ssss}

  20. T = {+, -, *, /}



  1. Пусть задано множество 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

















  1. Установить свойства операций и тип алгебраической системы

N - множество натуральных чисел; Z - множество целых чисел; R – множество действительных чисел; Q - множество рациональных чисел; + - сложение; * - умножение; - -вычитание; / - деление


  1. {N, + ,*}

  2. {N, + }

  3. {N, +,*}

  4. {Z, + ,*}

  5. {Z, + }

  6. {Z,*}

  7. {Q, + ,*}

  8. {Q, + }

  9. {Q, *}

  10. {R, + ,*}

  11. {R, + }

  12. {R, *}

  13. {Q, - ,*}

  14. {Z, - ,*}

  15. {N, + ,-}

  16. {N, - ,*}

  17. {N, - }

  18. {N, -,*}

  19. {R, - ,*}

  20. {Q, - ,*}





Контрольный тест



  1. 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


Задания


  1. Определить количество размещений с неограниченными повторениями объема m из n различных элементов.


  1. Определить количество m-перестановок из n различных элементов


  1. Определить количество перестановок из n различных элементов.


  1. Определить число заполнений m предметов в n различных ячейках.


Варианты заданий:

  1. n=10, m=2;

  2. n=10, m=3;

  3. n=10, m=4;

  4. n=10, m=5;

  5. n=9, m=2;

  6. n=9, m=3;

  7. n=9, m=4;

  8. n=9, m=5;

  9. n=8, m=2;

  10. n=8, m=3;

  11. n=8, m=4;

  12. n=8, m=5;

  13. n=11, m=2;

  14. n=11, m=3;

  15. n=11, m=4;

  16. n=11, m=5;

  17. n=9, m=5;

  18. n=8, m=2;

  19. n=8, m=3;

  20. n=8, m=4;

  21. n=8, m=5;

  22. n=11, m=2;

  23. n=11, m=3;

  24. n=11, m=4

  25. 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



Источник: https://files.student-it.ru/previewfile/6018

Смотрите также:

Анализ эффективности инвестиций предприятия на примере ООО «СпецПримСтрой»
Изложение содержания дела, по которому приняты судебные постановления