DiM 2203 дискретті математика

2. n =6, m =4 
7. n =5, m =3 
12. n =4, m =2 
17. n =8, m =2 
3. n =5, m =4 
8. n =5, m =3 
13. n =8, m =6 
18. n =4, m =3 
4. n =6, m =2 
9. n =5, m =3 
14. n =7, m =5 
19. n =7, m =2 
5. n =5, m =2 
10. n =6, m =5 
15. n =7, m =4 
20. n =8, m =3 
 
7-өзіндік жұмыс. Графтар, берілу тәсілдері.  
а) Төбелер жиыны Х-тен берілген G бинарлы қатынас бойынша граф, 
оның  толықтауышын,  және  екі  графтың  да  инциндентті  және  сыбайлас 
матрицаларын құрыңыз. 
1. X={0,1,2,3,4,5};  G: |x-y|>=3; 
2. X={0,1,2,3,4,5};  G: |x-y|=2; 
3. X={0,1,2,3,4};  G: |x+y|>=3, x y; 
4. X={0,1,2,3,4,5};  G: |x-y|>=2;   
5. X={1,2,3,4,5,6};  G: |x+y|>=2; 
6. X={1,2,3,4,5};  G: 5<=|x+y|<=8 
7. X={1,2,3,4,5,6};  G: 2y<=x, 2x<=y; 
8. X={1,2,3,4,5};  G: |x-y|=3; 
9. X={1,2,3,4,5,6};  G: |x-y|=1, |x-y|=4; 
10. X={1,2,3,4,5};  G: 1<=|x-y|<=3; 
11. X={1,2,3,4,5};  G: 3<=x+y<=5; 
12. X={1,2,3,4,5};  G: 3<=x+y<=4; 
13. X={0,1,2,3,4,5}; G: |x+y|>=2; 
14. X={1,2,3,4,5,6};  G: |x-y|<3; 
15. X={1,2,3,4,5};  G: 5<=|x+y|<=8; 
16. X={0,1,2,3,4};  G: |x+y|>=3, x y; 
17. X={0,1,2,3,4,5};  G: |x-y|>=2; 
18. X={1,2,3,4,5,6};  G: |x+y|>=2; 
19. X={0,1,2,3,4,5};  G: 2<=|x-y|<=4; 
20. X={1,2,3,4,5};  G: 4<=x+y<=5. 
 
б) Графтармен операциялар. 
G1 және G2 графтары берілген. 
2
1
G
G 
, 
2
1
G
G 
,
2
1
G
G
, 
2
1
G
G
, табыңыз. 
Тапсырмалар нұсқалары: 
1 
 
 
2 
 
3 
 
 
4 
 
 
5 
 
 
6 
 
7 
 
 
8 
 
 
9 
 
 
10 
 
 
11 
 
 
12 
 
 
13 
 
 
14 
 
 
15 
 
 
16 
17 
18 

 
 
 
 
 
 
19 
 
 
20 
 
 
21 
 
 
 
8-өзіндік жұмыс. Граф сандары. Графтардағы маршруттар. 
а) Семестрлік жұмыста құрылған G
1
U G
2 
жәнеG
1
хG
2
 графтары үшін: 
 
Цикломатикалық санды; 
 
Хроматикалық санды; 
 
Диаметр, радиус, центрді табыңыз. 
Бұл графтардың планарлы және эйлер графы болуын тексеріңіз.Барлық 
қаңқалы ағаштарды белгілеңіз. 
б) 7 Семестрлік жұмыстағы графы үшін төмендегілерді көрсетіңіз: 
 
Тұйық емес маршрут, бірақ шынжыр емес; 
 
Қарапайым емес шынжар; 
 
Қарапайым шынжыр; 
 
Тұйық маршрут, бірақ цикл емес; 
 
Қарапайым емес цикл; 
 
Қарапайым цикл; 
Бірінші  төбеден  шығатын  ұзындығы  2-ге  тең  барлық  маршруттарды 
және ұзындығы 2-ге тең маршруттың матрицасын табыңыз. 
 

Бақылау жұмыстарының тақырыптары мен нұсқалары (4 бақылау 
жұмысы ). 
1  Бақылау  жұмысы.  Жиындар  теориясы.  Сәйкестiктер,  бейнелеулер, 
функциялар.  А={a,b,c}  және  B={1,2,3,4}  жиындарының  арасында    Р 
сәйкестiгi бар. Р
-1
 сәйкестiгiн табыңыз. Екi сәйкестiктiң де анықталу облысы 
мен  мәндер  жиынын  табыңыз.  Оларды  график  түрiнде  өрнектеңiз. 
Сәйкестiктердiң қасиетiн зерттеңiз.  
 
 
Тапсырма рұсқалары  
1. P={(a,1),(a,2),(b,3),(c,2),(c,3),(c,4)} 
2. P={(а,3), (a,2), (a,4), (b,1), (c,2), (c,4)(c,3)} 
3. P={(a,2),(a,4),(b,1),(b,2),(b,4),(c,2),(c,4)}  
4. P={(а,2),(a,4), (a,3), (c,1), (c,2), (c,3)} 
5. P={(а,2),(a,4), (a,3), (c,1), (c,2), (c,3)} 
6. P={(а,3),(b,4), (b,3), (c,1), (c,2), (c,4)} 
7. P={(а,2),(a,3), (a,4), (b,1), (b,2), (b,4)} 
8. P={(а,1),(a,2), (b,3), (b,4), (c,3), (c,4)} 
9.  P={(а,2), (a,3), (a,4), (c,3), (c,1), (c,4)} 
10. P={(а,1),(a,2), (a,4), (b,2), (b,4), (c,3)} 
11. P={(b,1), (b,3), (c,1), (c,2), (c,3), (c,4)} 
12. P={(а,2), (a,4), (b,3), (c,1),(c,2)} 
13. P={(а,3), (a,2), (b,2), (b,3), (c,1), (c,4)} 
14. P={(а,1), (a,3), (a,4), (b,3), (c,1), (c,4)} 
15. P={(а,1), (b,3), (c,1), (c,4), (c,3), (c,2)} 
16 .P={(а,1), (b,3), (b,1), (b,4), (c,3), (c,2)} 
17. P={(а,1), (а,2), (a,4), (b,1), (b,4), (c,3)} 
18. P={(а,1), (а,4), (b,2), (b,3), (c,1), (c,4)} 
19. P={(а,1), (а,2), (b,2), (b,4), (c,3), (c,2)} 
20. P={(a,1), (a,2), (a,4), (c,3), (c,2), (c,4)} 
б)  Айнымалылардың  барлық  мүмкiн  мәндерiнде  мәнi  берiлген 
функциясы үшiн МДҚФ,МКҚФ табыңыз. 
Тапсырма варианттары 
1. f(x, y, z, t) = (0011100011001100) 
2. f(x, y, z, t) = (1011011000110100) 
3. f(x, y, z, t) = (1001010011100101) 
4. f(x, y, z, t) = (0011011011011010) 
5. f(x, y, z, t) = (1001000100101100)  
6. f(x, y, z, t) = (1010011001001011) 
7. f(x, y, z, t) = (1001100010011100) 
8. f(x, y, z, t) = (0100100010011100) 
9. f(x, y, z, t) = (1101001110010010) 
10. f(x, y, z, t)= (1011001110001010) 
11. f(x, y, z, t) = (1110001101010010) 
12. f(x, y, z, t) = (1000101001111010) 

13. f(x, y, z, t) = (1100101001101000) 
14. f(x, y, z, t) = (1010001110010100) 
15. f(x, y, z, t) = (0111011010101001) 
16. f(x, y, z, t) = (1011101001011001) 
17. f(x, y, z, t) = (1100011101001110) 
18. f(x, y, z, t) = (1001000011110101) 
19. f(x, y, z, t) = (0100110100101011) 
20. f(x, y, z, t) = (0110101101000110) 
в)  Жегалкин    алгебрасы.  f(x,  y,  z)  функциясы  үшiн  Жегалкин 
полиномын табыңыз. 
Тапсырма варианттары: 
1. f(x, y,z ) = ( x   y)   (y
x
)(x
y
)
 (z |
y
x
).      
2. f(x, y,z ) = (x   (
y
(
x
y
))( x   (
xy
z
|
y
) )). 
3. f(x, y,z ) =  x
 (y   z) ↔ (x
y)  (x
z). 
4. f(x, y,z ) = 
)
|
(
)
(
x
y
x
z
. 
5. f(x, y,z ) = (x   y)
(y
x
)(x
y
)|(z 
y
x
). 
6. f(x, y,z ) = x
(y   z)  (x
y)   (x
z). 
7. f(x, y,z ) = 
)
(
)
(
x
z
y
x
. 
8. f(x, y,z ) = (x   y)|(y
x
)↓(x   
y
) 
(z  
y
x
). 
9. f(x, y,z ) = x  (y   z) | (x   y)   (x   z). 
10. f(x, y,z ) = 
x
z
y
x
)
)
((
. 
11. f(x, y,z ) = x  ( 
y
))
(
x
y
 
))
(
|
(
xy
z
y
x
 
12.  f(x, y,z ) = x   (y   z) → (x   y)   (x   z) 
13. f(x, y,z ) = 
)
(
)
|
(
y
z
y
x
. 
14. f(x, y,z ) = (x|y)
(y   
x
)(x 
y
) (z 
 
y
x
). 
15.  f(x, y,z ) = x
 (y|z)   (x
 y) | (x
z). 
16. f(x, y,z ) = 
)
(
)
(
x
z
y
x
. 
17. f(x, y,z ) = 
xy
z
x
y
y
x
|
))
(
(
. 
18. f(x, y,z ) =  x   (y
z)    (x   y) 
 (x   z). 
19. f(x, y,z ) = 
y
z
y
x
)
)
((
. 
20. f(x, y,z ) = x   (y
z)    (x   y) 
 (x   z). 
2.  Бақылау  жұмысы.  Логикалық  функциялардың  толық  жүйелері. 
Комбинаторика. 
а) f
1 
және
 
f
2
 функцияларының қандай класқа жататындығын анықтаңыз. 
Пост теоремасына сүйенiп 
{ f
1 
,f
2
 } функциялар жүйесiнiң толықтығын тексерiңiз. 
№ 
Тапсырмалар 
нұсқалары 
№ 
Тапсырмалар 
нұсқалары 
№ 
Тапсырмалар 
нұсқалары 
1 
F
1
=(0 1 0 1 1 0 1 1) 
f
2
=(x V y)
(z   x) 
8 
f
1
=(0 1 1 0 1 1 1 0) 
f
2
=x   y V z 
15 
f
1
=(0 1 1 1 1 1 0 1) 
f
2
=(x V y)
 xyz 
2 
F
1
=(0 1 0 1 1 0 0 1) 
9 
f
1
=(0 1 1 0 0 0 1 1) 
16 
f
1
=(1 0 0 1 0 1 0 0) 

f
2
=(x 
 y) V 
z
 
f
2
=(x   y)
(y V x) 
f
2
=(x V y)
(z   x) 
3 
f
1
=(0 1 0 1 0 1 1 0)  
f
2
=x   (
y
 V z) 
10 
f
1
=(0 1 1 0 1 1 0 1) 
f
2
=(x   z)
(xVy) 
17 
f
1
=(1 0 0 1 1 0 0 1) 
f
2
=(x 
 y)   z 
4 
f
1
=(0 1 0 1 0 0 1 1) 
f
2
=(x 
 
y
)   z 
11 
f
1
=(0 1 1 1 0 1 0 0) 
f
2
=x y   z x 
18 
f
1
=(1 0 0 1 0 1 1 0) 
f
2
=x V yz 
5 
F
1
=(0 1 0 1 1 1 0 1) 
f
2
=x y V z (x 
y
) 
12 
f
1
=(0 1 1 1 1 0 0 1) 
f
2
=
x
yz
(zVx) 
19 
f
1
=(1 0 0 1 0 0 1 1) 
f
2
=(x 
 y)   z 
6 
f
1
=(0 1 1 0 0 1 0 0) 
f
2
=x y   (y 
 z) 
13 
f
1
=(0 1 1 1 0 1 1 0) 
f
2
=(x
y) (z y) 
20 
f
1
=(1 0 0 1 1 1 0 1) 
f
2
=xy V z(x   y)  
7 
f
1
=(0 1 1 0 1 0 0 1) 
f
2
=
x y
 V(x y   z)  
14 
f
1
=(0 1 1 1 0 0 1 1) 
f
2
=(x V y)   (z V y) 
21 
f
1
=(0 1 0 1 0 1 1 0)  
f
2
=x   (
y
 V z) 
б) Берiлген А цифрлар жиынын пайдаланып қанша әртүрлi үш таңбалы 
натурал сан алуға болады, егер 1) Әр цифр бiрден артық пайдаланылмайды;  
2) Бiр цифрды бiрнеше рет пайдалануға болады; 
б) Тапсырма варианттары 
1.А={3,4,5,6} 
5.А={2,3,5,7,9}  9.А={2,5,7,8,9} 
13. А={3,4,7,9} 
17. А={2,4,7} 
2.А={1,3,5,7} 
6.А={1,4,8,9} 
10.А={3,4,7,8,9}  14. А={2,5,7,8} 
18. А={1,3,5,8,9} 
3.А={2,5,6,7,8}  7.А={2,3,4,5} 
11.А={1,2,5,6} 
15. А={1,3,4} 
19. А={3,4,7,9} 
4. А={3,4,5,9}  8.А={3,7,8,9} 
12.А={2,3,4,5,6}  16. А={3,5,7,8,9}  20. А={2,5,6,7,8} 
в) Тапсырма варианттары 
1. 
5 кiтапты сөреге қанша әдiспен орналастыруға болады 
2. 
Серванттың  бiр  қатарына  6  бокалды  қанша  әдiспен 
орналастыруға болады. 
3. 
Столға  8  адамнан  тұратын  президиумды  қанша  әдiспен 
отырғызуға болады? 
4. 
7 адамды қанша әдiспен  сапқа тұрғызуға болады? 
5. 
Класқа 10 партаны қанша әдiспен қоюға болады? 
6. 
А,Б,В,Г,Д  әрiптерiнен  тұратын  тiзбектi  қанша  әдiспен 
құруға болады? 
7. 
«Персик»  сөзiнен  қанша  әртүрлi  6  әрiптiк  тiзбектер  алуға 
болады? 
8. 
5  пәннен  тұратын  оқу  кестесiн  бiр  күнге  неше  тәсiлмен 
құруға болады? 
9. 
Дастарханға 4 адамды қанша әдiспен отырғызуға болады? 
10. 
Әртүрлi  7  карточка  салынған  қорапты  қанша  әдiспен 
араластыруға болады? 
11. 
 Ұсынылған  6  пәннен  3  пәндi  неше  әдiспен  таңдауға 
болады? 
12. 
Қолда  бар  7  түрлi  жемiстiң  екеуiн  қанша  әдiспен  таңдауға 
болады? 
13. 
10  адамнан  жиналысқа  баратын  3  адамды  қанша  әдiспен 
таңдауға болады? 
14. 
Конкурсқа  7  притенденттен  4  студенттi  қанша  әдiспен 
таңдауға болады? 

15. 
Сөреде  тұрған  10  кiтаптан  неше  әдiспен  оқуға  3  кiтап 
таңдауға болады? 
16. 
10 фильмнен тұратын видеотекадан неше әдiспен әртүрлi 4 
фильм таңдауға болады? 
17. 
Шкафта  iлулi  тұрған  8  галстуктен  неше  әдiспен  әртүрлi  2 
галстук таңдауға болады? 
18. 
Сатылымдағы 9 түрлi газеттен неше әдiспен әртүрлi 5 газет 
сатып алуға болады? 
19. 
8  адамнан  тұратын  топтан  неше  әдiспен  программалау 
курсына 3 адам таңдауға болады? 
20. 
 Менюде  бар  7  тағамнан  неше  әдiспен  3  түрлi  тағам 
таңдауға болады? 
Тапсырмалар варианттары 
1.  Темiр жол бекетiнде m бағдаршам бар. Егер бағдаршам «қызыл», 
«жасыл»,  «сары»  3  күйде  болса,  олардан  неше  түрлi  сигналдардың 
комбинациясын беруге болады? 
2.  Бiр 
мемлекетте  тiстерiнiң  жиынтығы  бiрдей  2  тұрғын 
болмаптыегер  адамның  тiстерiнiң  саны  32  десек  бұл  мемлекеттiң 
тұрғындарының ең көп саны қанша болуы мүмкiн? 
3.  Қайталап  пайдалануға  болатын  тақ  цифрлардан  неше  түрлi  4 
таңбалы сан құрастыруға болады? 
4.  Әртүрлi  12  оқу  құралын  4  студентке  неше  әдiспен  бәлiп  беруге 
болады? 
5.  9  түрлi  күмiс  ақшаны  2  қалтаға  неше  түрлi  әдiспен  салуға 
болады? 
6.  Үшеуi  ток  импульсi  ,  екеуi  үзiлiсте  болатын  әрiптегi  5  түрлi 
сигналдан алфавиттiң неше әрiбiн құрауға болады? 
7.  «Статистика», «Парабола» сөздерiндегi әртүрлi алмастырулардың 
санын анықтаңыз. 
8.  Апада  2 алма, 3 алмұрт және 4 апельсин бар. Олардан 9 күн бойы 
баласына бiр талдан берiп отырады. Қанша әдiспен берiп отыруға болады? 
9.  Почта бөлiмшесiнде 9 түрлi ашық хат сатылады. Ашық хаттың әр 
түрiнiң саны 8ден кем болмаса 8 ашық хаттан тұратын жиынтықты неше 
әдiспен сатып алуға болады? 
10. 
3  жiгiт  пен  2  қыз  жұмыс  орнын  iздейдi.  Егер  қалада  3  тек 
жiгiттер дi қабылдайтын құю цехтары бар 3 зауыт, қыздарды қабылдайтын 
2  тоқыма  фабрикасы  және  жiгiттердi  де,  қыздарды  да  қабылдайтын  2 
фабрика болса неше әдiспен жұмыс таңдауға болады? 
11. 
Бес  қызметкерден  тұратын  топқа  3жолдама  бөлiндi. 
Жолдамалар әртүрлi болса, оны неше әдiспен үлестiруге болады? 
12. 
Взводта 3 сержант және 30солдат бар. Қарауылға 1 сержант 
пен 3 солдатты неше әдiспен жiберуге болады? 
13. 
Неше  әдiспен  15  студенттi  3  оқу  тобына  бесеуден  бөлуге 
болады? 

14. 
Жарысқа  қатысушы  17  спортшыға  бiрiншi,  екiншi  және 
үшiншi орындарды неше әдiспен бөлудiң мүмкiндiгi бар? 
15. 
5әйел  және  7  ер  адамнан  тұратын  қазылар  алқасы  8  әйел 
және  11 ер  адамнан  тұратын  тiзiмнен  таңдалуы  тиiс. Құрамы  неше  түрлi 
қазылар алқасын таңдауға болады? 
16. 
Раушангүлiнiң  4  сорты  сатылады.  Қанша  әртүрлi  букет 
құруға болады? 
17. 
Бiрдей  20шарды.  Әртүрлi  4  урнаға  неше  әдiспен  салуға 
болады? 
18. 
 Әртүрлi  10  шарды,  3  урнаға  қанша  әдiспен  орналастыруға 
болады? 
19. 
Белгiлi  әртүрлi  7  аттан  4  күшiкке  неше  әдiспен  ат  беруге 
болады? 
20. 
25  адамнан  тұратын  топты  7  коалицияға  неше  әдiспен 
бөлуге  болады:5адамнан  2  коалиция,  7  адамнан  1  коалиция,  2  адамнан  4 
коалиция; 
д)Жиындарды  бөлiктеу.  n  объектен  тұратын  жиынды  m  бос  емес 
бөлiктерге бөлуге болады? 
Тапсырма варианттары: 
1. n =7, m =3 
5. n =7, m =4 
9. n =7, m =2 
13. n =5, m =4 
17. n =5, m =3 
2. n =4, m =2 
6. n =7, m =4 
10. n =8, m =3 
14. n =6, m =2 
18. n =5, m =3 
3. n =8, m =6 
7. n =8, m =2 
11. n =5, m =3 
15. n =5, m =2 
19. n =5, m =3 
4. n =7, m =5 
8. n =4, m =3 
12. n =6, m =4 
16. n =6, m =3 
20. n =6, m =5 
 
3-Бақылау жұмысы. Ең кіші қосылу туралы есеп. 
7 төбелі бағытталмаған толық графтың қабырғалар салмағының матрицасы 
берілген. Оң ең кіші қаңқалы ағашын табыңыз. Жеткілікті түсініктемелермен оны 
графикалық түрде кескіндеңіз. 
Тапсырма варианттары. 
 
 
1. 
∞ 
1 
3 
4 
5 
6 
2 
2. 
∞ 
6 
1 
1 
7 
5 
2 
 
1 
∞ 
1 
2 
3 
5 
7 
 
6 
∞ 
8 
3 
9 
3 
1 
 
3 
1 
∞ 
4 
1 
2 
8 
 
1 
8 
∞ 
4 
2 
1 
3 
 
4 
2 
4 
∞ 
2 
5 
1 
 
1 
3 
4 
∞ 
1 
5 
5 
 
5 
3 
1 
2 
∞ 
3 
7 
 
7 
9 
2 
1 
∞ 
2 
1 
 
6 
5 
2 
5 
3 
∞ 
8 
 
5 
3 
1 
5 
2 
∞ 
4 
 
2 
7 
8 
1 
7 
8 
∞ 
 
2 
1 
3 
5 
1 
4 
∞ 
 
3 
∞ 
1 
2 
6 
3 
1 
7 
4. 
∞ 
7 
6 
3 
1 
7 
9 
 
1 
∞ 
8 
3 
1 
2 
1 
 
7 
∞ 
2 
4 
8 
2 
5 
 
2 
8 
∞ 
5 
4 
1 
1 
 
6 
2 
∞ 
1 
2 
1 
1 
 
6 
3 
5 
∞ 
5 
3 
2 
 
3 
4 
1 
∞ 
6 
2 
1 
 
3 
1 
4 
5 
∞ 
1 
2 
 
1 
8 
2 
6 
∞ 
6 
8 
 
1 
2 
1 
3 
1 
∞ 
3 
 
7 
2 
1 
2 
6 
∞ 
9 
 
7 
1 
1 
2 
2 
3 
∞ 
 
9 
5 
1 
1 
8 
9 
∞ 
 
5. 
∞ 
1 
2 
7 
3 
4 
8 
6. 
∞ 
5 
7 
3 
9 
1 
4 
 
1 
∞ 
8 
5 
2 
9 
4 
 
5 
∞ 
8 
3 
5 
1 
6 
 
2 
8 
∞ 
1 
8 
4 
2 
 
7 
8 
∞ 
7 
2 
7 
9 
 
7 
5 
1 
∞ 
9 
9 
3 
 
3 
3 
7 
∞ 
4 
1 
6 
 
3 
2 
8 
9 
∞ 
2 
5 
 
9 
5 
2 
4 
∞ 
6 
2 

 
4 
9 
4 
9 
2 
∞ 
6 
 
1 
1 
7 
1 
6 
∞ 
6 
 
8 
4 
2 
3 
5 
6 
∞ 
 
4 
6 
9 
6 
2 
6 
∞ 
 
7. 
∞ 
7 
2 
7 
1 
9 
1 
8. 
∞ 
5 
4 
2 
4 
1 
4 
 
7 
∞ 
4 
7 
8 
2 
6 
 
5 
∞ 
7 
4 
8 
2 
9 
 
2 
4 
∞ 
9 
3 
2 
7 
 
4 
7 
∞ 
8 
2 
2 
7 
 
7 
7 
9 
∞ 
5 
3 
1 
 
2 
4 
8 
∞ 
3 
9 
4 
 
1 
8 
3 
5 
∞ 
9 
5 
 
4 
8 
2 
3 
∞ 
8 
2 
 
9 
2 
2 
3 
9 
∞ 
7 
 
1 
2 
2 
9 
8 
∞ 
1 
 
1 
6 
7 
1 
5 
7 
∞ 
 
4 
9 
7 
4 
2 
1 
∞ 
 

жүктеу/скачать 3,62 Mb.

Достарыңызбен бөлісу: