Материалы семинаров по дискретной математике

mgu IM. lOMONOSOWA, MEHMAT

materialy seminarow po diskretnoj matematike 4-J KURS, OTDELENIE MEHANIKI, OSENX 2002 PREPODAWATELX d. `. ~ERUHIN wERSIQ W iNTERNETE: http://www.cher3.narod.ru/discmath.htm

lITERATURA

1. qBLONSKIJ s. w. wWEDENIE W DISKRETNU@ MATEMATIKU. | m.: nAUKA, 1986. 2. gAWRILOW g. p., sAPOVENKO a. a. zADA^I I UPRAVNENIQ PO KURSU DISKRETNOJ MATEMATIKI. | m.: nAUKA, 1992. 3. nEF
sEMINAR 1 (2,5.9) gRAFY: PUTI, CIKLY, cWQZNOSTX, DEREWXQ

gRAF (NEORIENTIROWANNYJ ) | TROJKA (V E I), GDE V | MN-WO WER IN, E | MN-WO REBER, I: E ! V (2) | FUNKCIQ INCIDENTNOSTI, SOPOSTAWLQET REBRU MNOVESTWO IZ DWUH WERIN | EGO KONCOW  ZDESX V (2) = ffv wg j v 2 V w 2 V g. eSLI I(e) = fv wg, TO WERINY v w NAZ. SOSEDNIMI (SMEVNYMI ), REBRO e IM INCIDENTNO , e SOEDINQET v S w. eSLI I(e) = fvg (v = w), TO REBRO e | PETLQ  ESLI e 6= e I I(e) = I(e ), TO REBRO e KRATNO. gRAF KONE^NYJ, ESLI MN-WA V E KONE^NY RASSMATRIWAEM TOLXKO KONE^NYE GRAFY. sTEPENX WERINY v: d(v) = (^ISLO INCIDENTNYH EJ R 0. wIDY PUTEJ: CEPX | e1 : : : en POPARNO RAZLI^NY PROSTAQ CEPX | CEPX I v0 : : : vn PO0

0

2

;

1

PARNO RAZLI^NY KONTUR | v0 = vn  CIKL | KONTUR, CEPX I n > 1. wIDY CIKLOW: PROSTOJ | v1 : : : vn POPARNO RAZLI^NY |JLEROW | fe1 : : : eng = E gAMILXTONOW | PROSTOJ I fv1 : : : vng = V . zADA^A 2. dOKAZATX, ^TO S POMO]X@ UDALENIQ NEKOTORYH R jV j ; 1 W) W L@BOM GRAFE jEj > jV j ; k, GDE k | ^ISLO KOMPONENT SWQZNOSTI. 2

zADA^A 9 (|JLER). dOKAZATX, ^TO |JLEROW CIKL W SWQZNOM GRA

FE SU]ESTWUET TOGDA I TOLXKO TOGDA, KOGDA STEPENX KAVDOJ WERINY ^
sEMINAR 2 (9,12.9) gRAFY: PROSTYE, DWUDOLXNYE, PROIZWEDENIQ

pROSTOJ GRAF | GRAF BEZ PETELX I KRATNYH R
3

TAK, ^TO L@BOE REBRO SOEDINQET NEKOTORU@ WERINU IZ V1 S NEKOTOROJ IZ V2 . Kn m (POLNYJ DWUDOLXNYJ GRAF) | PROSTOJ DWUDOLXNYJ GRAF S DOLQMI MO]NOSTI n I m, W KOTOROM L@BYE DWE WERINY IZ RAZNYH DOLEJ SMEVNY. lES | GRAF BEZ CIKLOW PAROSO^ETANIE | GRAF, WSE WERINY KOTOROGO WISQ^IE SOWER ENNOE PAROSO^ETANIE W DANNOM GRAFE | PAROSO^ETANIE, SODERVA]EE WSE EGO WERINY. zADA^A 5. dOKAZATX, ^TO: A) LES | DWUDOLXNYJ GRAF B) GRAF QWLQETSQ DWUDOLXNYM TOGDA I TOLXKO TOGDA, KOGDA ON NE SODERVIT CIKLOW NE^ jW j (S1(W ) | MNOVESTWO WERIN, SMEVNYH S WERINAMI IZ W). pROIZWEDENIE GRAFOW G1 = (V1 E1 I1 ) I G2 = (V2 E2 I2 ) | GRAF G1  G2 S MNOVESTWOM WERIN V1  V2 , W KOTOROM DWE PROIZWOLXNYE WERINY v = (v1 v2) I v = (v1 v2 ) SMEVNY TOGDA I TOLXKO TOGDA, KOGDA DLQ NEKOTOROGO i 2 f1 2g WERINY vi I vi SMEVNY W Gi, A v3 i = v3 i PRI \TOM v I v SOEDINENY STOLXKIMI R
0

0

0

;

0

;

0

0

4

WA CEPX (PROSTAQ CEPX, PROHODQ]AQ ^EREZ WSE WERINY), TO W GRAFE G  H ESTX gAMILXTONOW CIKL. pROBLEMA. pUSTX d NE^
sEMINAR 3 (16,19.9) gRAFY: WLOVENIQ, PLOSKIE, RASKRASKI

wLOVENIE (UKLADKA ) GRAFA W MNOGOOBRAZIE: FUNKCIQ, SOPOSTAWLQ@]AQ WERINAM GRAFA POPARNO RAZLI^NYE TO^KI MNOGOOBRAZIQ, A R
2

5

zADA^A 5. A) (|JLER) DLQ SWQZNOGO NEPUSTOGO PLOSKOGO GRAFA DOKAZATX FORMULU: jV j; jE j + j;j = 2 B ) DLQ PSEWDOPLOSKOGO GRAFA, STROGO WLOVENNOGO W SFERU S d RU^KAMI, DOKAZATX FORMULU: jV j ; jE j + j;j = 2 ; 2d. zADA^A 6. dOKAZATX, ^TO GRAF A) K5 B) K3 3 NE QWLQETSQ PLANARNYM. zADA^A 7 . dOKAZATX, ^TO L@BOJ NEPUSTOJ SWQZNYJ GRAF MOVET BYTX STROGO WLOVEN W SFERU S NEKOTORYM ^ISLOM RU^EK. oPERACIQ RAZBIENIQ REBRA : PUSTX I(e) = fv1 v2 g REBRO e UDALQETSQ, WWODITSQ NOWAQ WERINA v I R


0

0

0

;

;









6

NYJ B) V (G ) = ;(G) W ) ESLI G SWQZNYJ, BEZ PETELX I WISQ^IH WERIN, TO G IZOMORFEN G. zADA^A 13. dOKAZATX, ^TO W PROSTOM PLOSKOM GRAFE NAJD








sEMINAR 4 (23,26,30.9) kOMBINATORIKA: SUMMY, PRINCIP WKL@^ENIJ I ISKL@^ENIJ

pRAWILO SUMMY: ESLI OB_EKT A MOVET BYTX WYBRAN n SPOSOBAMI, A OB_EKT B | m SPOSOBAMI, I ODNOWREMENNO ONI NE MOGUT BYTX WYBRANY, TO ODIN IZ NIH MOVET BYTX WYBRAN n+m SPOSOBAMI. pRAWILO PROIZWEDENIQ: ESLI OB_EKT A MOVET BYTX WYBRAN n SPOSOBAMI, A POSLE EGO WYBORA OB_EKT B MOVET BYTX WYBRAN m SPOSOBAMI, TO A I B RAWNO n  m. bINOMIALX ^ISLO SPOSOBOW SOWMESTNOGO ;WYBORA
;
NYJ KO\FFICIENT | Cnk  nk = k!(nn! k)! PRI 0 6 k 6 n, I nk = 0 W OSTALXNYH SLU^AQH. pUSTX IMEETSQ MNOVESTWO U = fa1 : : : ang MO]NOSTI n. uPORQDO^ENNAQ WYBORKA MO]NOSTI k IZ U (IZ n \LEMENTOW) | NABOR (ai1 : : : ai ) NEUPORQDO^ENNAQ | NAGRUVENNOE MNOVESTWO f(a1 k1) : : : (an kn)g, GDE ki 2 N f0g | KOLI^ESTWO POWTORENIJ \LEMENTA ai W WYBORKE, k1 + : : : + kn = k. wYBORKA BEZ POWTORENIJ , ESLI is 6= it PRI s 6= t (DLQ UPORQDO^ENNOJ) ILI ki 2 f0 1g (DLQ NEUPORQDO^ENNOJ). zADA^A 1. nAJTI ^ISLO SLEDU@]IH WYBOROK MO]NOSTI k IZ n \LEMENTOW: A) WSEH UPORQDO^ENNYH B) UPORQDO^ENNYH BEZ POWTORENIJ (RAZME]ENIJ ) W) NEUPORQDO^ENNYH BEZ POWTORENIJ (SO^ETANIJ ) G) WSEH NEUPORQDO^ENNYH (SO^ETANIJ S POWTORENIQMI ). zADA^A 2. dOKAZATX FORMULY:
;
;
;
;
; A) nk = nn k  B) nk = nk 1 + nk 11 (TREUGOLXNIK pASKALQ) ;
;
;
;
W) mn mk = nk mn kk  n ;n
P k n k (BINOM nX@TONA) G) (a + b)n = k a b ;

k

;

;

;

;

;

;

k=0 n ;n
P D) = 2n  k=0 k

;

E)

n P

;
(;1)k nk = 0

k=0

7

zADA^A 3. nAJTI SUMMY (WYRAZITX W WIDE SUPERPOZICII \LEMENTARNYH FUNKCIJ I FAKTORIALA): n ;
n ;
n ;
A) P mk  B) P k nk  W) P k2 nk  k=m r ;n
; m
P  G) k=0 k r;k

k=0

D)

n ;n
2 P

k=0 P;n
Z) 3k  k

P;


k

k=0



E)

n nP ;m ;
; P n n;m


m=0 k=0 m



k

P;


V) 2nk  I) 4nk . k k pUSTX IMEETSQ MNOVESTWO U = fa1 : : : ang MO]NOSTI n. sWOJSTWO (\LEMENTOW MNOVESTWA U) | PODMNOVESTWO MNOVESTWA U \LEMENT OBLADAET SWOJSTWOM, ESLI ON PRINADLEVIT \TOMU PODMNOVESTWU. pUSTX ESTX k SWOJSTW U1 : : : Uk . oBOZNA^IM: Ni1 ::: i | ^ISLO \LEMENTOW, ODNOWREMENNO OBLADA@]IH SWOJSTWAMI Ui1 : : : Ui (I, P MOVET BYTX, DRUGIMI) S0 = n, Sr = Ni1 ::: i PRI 1 6 16i1 <:::
r

r

r

U1 : : : Uk .

zADA^A 4. dOKAZATX SLEDU@]IE FORMULY:

A) N=0 = S0 ; S1 + S2 ; : : : + (;1)k Sk (PRINCIP WKL@^ENIJ I ISKL@^ENIJ) kPr ;
B) N=r = (;1)m mr+r Sm+r . m=0 zADA^A 5 (O S^ASTLIWYH BILETAH). nAJTI ^ISLO RAZLI^NYH NOMEROW S^ASTLIWYH BILETOW, T. E. TAKIH NABOROW IZ ESTI CIFR, W KOTORYH SUMMA PERWYH TR
8

sEMINAR 5 (3,7.10) gRAFY: HROMATI^ESKIJ MNOGO^LEN kOMBINATORIKA: PROIZWODQ]IE FUNKCII

hROMATI^ESKAQ FUNKCIQ GRAFA G (BEZ PETELX) | XG (q) | ^ISLO SPOSOBOW RASKRASKI WERIN GRAFA G W q CWETOW. zADA^A 1. nAJTI HROMATI^ESKU@ FUNKCI@ SLEDU@]IH GRAFOW: A) On B) Kn  W) PROSTOJ CEPI DLINY n G) DEREWA S n WERINAMI D ) PROSTOGO CIKLA DLINY n. zADA^A 2. dOKAZATX, ^TO: A) HROMATI^ESKAQ FUNKCIQ GRAFA ESTX PROIZWEDENIE HROMATI^ESKIH FUNKCIJ EGO KOMPONENT SWQZNOSTI B ) ESLI G | GRAF S n WERINAMI, TO XG (q) | MNOGO^LEN OT PEREMENNOJ q STEPENI n SO STARIM KO\FFICIENTOM 1. pUSTX DANA POSLEDOWATELXNOSTX ^ISEL fan g: a0 a1 : : : fORMALXNYJ STEPENNOJ RQD F(t) = a0 +a1 t +a2 t2 + : : : NAZYWAETSQ PROIZWODQ]IM RQDOM POSLEDOWATELXNOSTI fang. eSLI FUNKCIQ DEJSTWITELXNOGO ILI KOMPLEKSNOGO PEREMENNOGO f(t) RAZLAGAETSQ W RQD mAKLORENA (RQD tEJLORA W NULE) F (t) I \TOT RQD SHODITSQ K f(t) W NEKOTOROJ OKRESTNOSTI NULQ U" = ft j jtj < "g, " > 0, TO FUNKCIQ f(t) NAZYWAETSQ PROIZWODQ]EJ FUNKCIEJ POSLEDOWATELXNOSTI fang. pRI REENII NEKOTORYH KOMBINATORNYH ZADA^ UDOBNEE WNA^ALE NAJTI PROIZWODQ]U@ FUNKCI@, A ZATEM | OB]IJ ^LEN POSLEDOWATELXNOSTI fang, RAZLOVIW PROIZWODQ]U@ FUNKCI@ W RQD F (t), POLXZUQSX IZWESTNYMI ( ) RAZLOVENIQMI, ILI S POMO]X@ DIFFERENCIROWANIQ: an = f n!(0) . pRAWILXNOJ SKOBO^NOJ STRUKTUROJ NAZYWAETSQ SLOWO W ALFAWITE f ( ) g (POSLEDOWATELXNOSTX IZ OTKRYWA@]IH I ZAKRYWA@]IH KRUGLYH SKOBOK), W KOTOROM ^ISLO OTKRYWA@]IH SKOBOK RAWNO ^ISLU ZAKRYWA@]IH I NE NARUEN BALANS SKOBOK, T. E. W L@BOM NA^ALXNOM OTREZKE SLOWA ^ISLO ZAKRYWA@]IH SKOBOK NE BOLXE ^ISLA OTKRYWA@]IH. rAWNOSILXNOE OPREDELENIE PO INDUKCII: A) PUSTOE SLOWO | PRAWILXNAQ SKOBO^NAQ STRUKTURA B) ESLI A I B | PRAWILXNYE SKOBO^NYE STRUKTURY, TO (A) I AB | PRAWILXNYE SKOBO^NYE STRUKTURY. zADA^A 3. pUSTX an | ^ISLO PRAWILXNYH SKOBO^NYH STRUKTUR DLINY 2n (^ISLO kATALANA). A) NAJTI a0 a1 a2 a3 B) DOKAZATX, ^TO KAVDAQ PRAWILXNAQ SKOBO^NAQ STRUKTURA ODNOZNA^NO PREDSTAWLQETSQ W WIDE (A)B, GDE A I B | PRAWILXNYE SKOBO^NYE STRUKTURY W) DOKAZATX FORMULU an = a0 an 1 + a1 an 2 + : : : + an 1a0  



n

0 0

0 0

;

9

;

;

G) WYPISATX OB]IJ ^LEN PROIZWEDENIQ RQDOW F (t)  F(t), I NAJTI PROIZWODQ]U@ FUNKCI@ f(t) POSLEDOWATELXNOSTI fang D) RAZLOVITX f(t) W RQD mAKLORENA I POLU^ITX WYRAVENIE DLQ

an 

;




2n 1 E) PREOBRAZOWATX WYRAVENIE DLQ an K WIDU n+1 n . kORNEWOE DEREWO | DEREWO, W KOTOROM WYDELEN KORENX PLOSKOE KORNEWOE DEREWO | UKLADKA KORNEWOGO DEREWA NA PLOSKOSTX, POLUPLOSKOE KORNEWOE DEREWO | PLOSKOE KORNEWOE DEREWO, CELIKOM LEVA]EE W WERHNEJ POLUPLOSKOSTI f(x y) j y > 0g, ZA ISKL@^ENIEM KORNQ, LEVA]EGO W TO^KE (0 0). zADA^A 4. pUSTX bn | ^ISLO POLUPLOSKIH KORNEWYH DEREWXEW S n R
(x y z) 2 Z3+:

x + 2y + 3z = n

A) RASSMOTRETX PROIZWEDENIE RQDOW

(1 + t + t2 + : : :)(1 + t2 + t4 + : : :)(1 + t3 + t6 + : : :)

WYPISATX EGO OB]IJ ^LEN I NAJTI PROIZWODQ]U@ FUNKCI@ g(t) POSLEDOWATELXNOSTI fcng B) RAZLOVITX g(t) W SUMMU PROSTEJIH DROBEJ W) RAZLOVITX KAVDU@ PROSTEJU@ DROBX W RQD, SLOVITX RQDY I POLU^ITX WYRAVENIE DLQ cn  G) NAJTI TAKIE ^ISLA a I b, ^TO cn anb n ! 1.

sEMINAR 6 (10,14.10) kOMBINATORIKA: REKURRENTNYE POSLEDOWATELXNOSTI

pUSTX DANA POSLEDOWATELXNOSTX fan gn=0. lINEJNYM ODNORODNYM REKURRENTNYM SOOTNO ENIEM STEPENI k NAZYWAETSQ SOOTNOENIE WIDA 1

k an+k + k 1an+k 1 + : : : + 0 an = 0 ;

;

10

k 6= 0

n = 0 1 : : : (1)

eSLI POSLEDOWATELXNOSTX fang UDOWLETWORQET SOOTNOENI@ (1), TO ONA NAZYWAETSQ REKURRENTNOJ  MNOGO^LEN X(t) = k tk + k 1 tk 1 + : : : + 0 NAZYWAETSQ E< HARAKTERISTI^ESKIM MNOGO^LENOM . pRIMER REKURRENTNOJ POSLEDOWATELXNOSTI | ^ISLA fIBONA^^I : a0 = 0 a1 = 1 a2 = 1 a3 = 2 a4 = 3 a5 = 5 : : :, UDOWLETWORQ@]IE SOOTNOENI@ an+2 ; an+1 ; an = 0. zADA^A 1. pUSTX fang UDOWLETWORQET SOOTNOENI@ (1): WNA^ALE MOVNO RASSMOTRETX ^ISLA fIBONA^^I, A ZATEM | OB]IJ SLU^AJ. a) NAJTI PROIZWODQ]U@ FUNKCI@ f(t) POSLEDOWATELXNOSTI fang DLQ \TOGO PODOBRATX KO\FFICIENTY MNOGO^LENA P(t) = k tk + : : :+0 TAK, ^TOBY POSLE RASKRYTIQ SKOBOK W PROIZWEDENII F (t)  P (t) (GDE F (t) | PROIZWODQ]IJ RQD POSLEDOWATELXNOSTI fan g) WSE KO\FFICIENTY PRI tk tk+1 : : : OBRATILISX W 0 ESLI MNOGO^LEN F (t)  P(t) OBOZNA^ITX ^EREZ Q(t), TO f(t) = Q(t)=P(t) B) RAZLOVITX P(t) NA MNOVITELI (KORNI P (t) WYRAZITX ^EREZ KORNI 1 : : : k HARAKTERISTI^ESKOGO MNOGO^LENA) W) PREDSTAWITX f(t) W WIDE SUMMY PROSTEJIH DROBEJ G) RAZLOVITX KAVDU@ PROSTEJU@ DROBX W RQD, SLOVITX RQDY I PREDSTAWITX an W WIDE ;

;

s X i=1

Ri(n) ni

(2)

GDE 1 : : : s | POPARNO RAZLI^NYE KORNI HARAKTERISTI^ESKOGO MNOGO^LENA, i IMEET KRATNOSTX ki, Ri (n) | MNOGO^LEN OT n STEPENI ki ;1 (WNA^ALE RASSMOTRETX SLU^AJ, KOGDA WSE KORNI IME@T KRATNOSTX 1). oB]EE REENIE REKURRENTNOGO SOOTNOENIQ (1) I]ETSQ W WIDE (2) KO\FFICIENTY MNOGO^LENOW Ri(n) NAHODQTSQ PO PERWYM k IZWESTNYM ^LENAM POSLEDOWATELXNOSTI fang. zADA^A 2. pUSTX an | ^ISLO REENIJ URAWNENIQ x+2y+3z = n W CELYH NEOTRICATELXNYH ^ISLAH x y z. A) WYPISATX SISTEMU REKURRENTNYH SOOTNOENIJ DLQ an: RASSMOTRETX WSPOMOGATELXNYE URAWNENIQ 2y+3z = n (^ISLO REENIJ | bn) I 3z = n (^ISLO REENIJ | cn) ZAPISATX REKURRENTNOE SOOTNOENIE DLQ cn , ZATEM WYRAZITX bn ^EREZ cn I NEKOTORYE IZ bn 1 bn 2 : : : NAKONEC, an WYRAZITX ^EREZ bn I NEKOTORYE IZ an 1 an 2 : : : B ) REITX POLU^ENNU@ SISTEMU (WNA^ALE NAJTI cn , ZATEM bn , NAKONEC, an  METODY REENIQ REKURRENTNYH NEODNORODNYH SOOTNOENIJ MOVNO PO^ERPNUTX IZ LITERATURY). ;

;



11

;

;

zADA^A 3. nAJTI ^ISLO POSLEDOWATELXNOSTEJ DLINY n IZ NULEJ I EDINIC, W KOTORYH NE WSTRE^A@TSQ DWE EDINICY, IDU]IE PODRQD. zADA^A 4. nAJTI ^ISLO PUTEJ DLINY n W SLEDU@]IH GRAFAH: A) Kp  B) Kp q  W) GRAF, IME@]IJ DWE WERINY v0 I v1 I DWA REBRA: PERWOE SOEDINQET v0 S v1, WTOROE | PETLQ NA v0. pUSTX G | GRAF S MNOVESTWOM WERIN V = fv1 : : : vng. mATRICEJ SMEVNOSTI GRAFA G NAZYWAETSQ MATRICA M = (mi j )nij =1, W KOTOROJ mi j RAWNO ^ISLU R
kONTROLXNAQ RABOTA DA
zADA^A 2. nAJTI ^ISLO WERIN I R
A) PUTEJ DLINY 2 B) CEPEJ DLINY 2. zADA^A 4. eSTX LI W GRAFE G2: A) |JLEROW CIKL B) gAMILXTONOW CIKL? zADA^A 5. pLANAREN LI GRAF G? eSLI NET, TO KAKOE NAIMENXEE ^ISLO R
x + 2y = N

()

kAVDOE EGO REENIE (x y) OCENIWAETSQ W (x+1)4y BALLOW. nAJTI MAKSIMALXNOE ^ISLO BALLOW, KOTORYE MOVNO POLU^ITX, REAQ URAWNENIE ().

zADA^A 10. nA BIRVE EVEDNEWNO SOWERA@TSQ SDELKI KUPLIPRODAVI NEKIH AKCIJ. sDELKI ZAKL@^A@TSQ PO TEKU]EMU KURSU, RAWNOMU SREDNEMU ARIFMETI^ESKOMU MEVDU CENOJ, ZAQWLENNOJ PRODAWCAMI I CENOJ, ZAQWLENNOJ POKUPATELQMI. pRODAWCY ZAQWLQ@T CENU, NA N% BOLXU@ KURSA AKCIJ W PREDYDU]IJ DENX, A POKUPATELI | CENU, RAWNU@ SREDNEMU ARIFMETI^ESKOMU KURSOW AKCIJ ZA DWA PREDYDU]IH 13

DNQ. w PERWYJ DENX SDELKI PROHODILI PO KURSU 100, WO WTOROJ | PO KURSU 120. nAJTI ASIMPTOTIKU KURSA AKCIJ W n-J DENX PRI n ! 1.

sEMINAR 7 (24,28.10) bULEW KUB: KOMBINATORNYE SWOJSTWA

bULEW KUB (n-MERNYJ) | KAVDYJ IZ SLEDU@]IH IZOMORFNYH OB_EKTOW: GRAF K2n I MNOVESTWO f0 1gn. sU]ESTWUET BIEKCIQ (SM. ZADA^U 8 IZ SEMINARA 2) MEVDU NABORAMI IZ MNOVESTWA f0 1gn I WERINAMI GRAFA K2n , SOPOSTAWLQ@]AQ NABORU 2 f0 1gn WERINU v GRAFA K2n I OBLADA@]AQ SWOJSTWOM: WERINY v I v SMEVNY TOGDA I TOLXKO TOGDA, KOGDA NABORY I  RAZLI^A@TSQ ROWNO W ODNOM RAZRQDE. pUSTX = ( 1 : : : n),  = (1 : : : n ). oBOZNA^IM ( ) = jfi j i 6= igj | RASSTOQNIE MEVDU NABORAMI I . zADA^A 1. dOKAZATX, ^TO ( ) RAWNO DLINE KRAT^AJEGO PUTI W GRAFE K2n, SOEDINQ@]EGO WERINY v I v . zADA^A 2. dOKAZATX, ^TO ( ) | METRIKA, T. E. WYPOLNENY AKSIOMY: a) ( ) = 0 B) ( ) = ( ) W) ( ) + ( ) > ( ).

zADA^A 3. nAJTI ^ISLO KRAT^AJIH PUTEJ, SOEDINQ@]IH WERINY v I v . oBOZNA^IM: Sr ( ) = f j ( ) = rg | SFERA RADIUSA r S CENTROM W NABORE  {r ( ) = f j ( ) 6 rg | AR RADIUSA r S CENTROM W . zADA^A 4. nAJTI ASIMPTOTIKI: A) jSr ( )j PRI r = const n ! 1 B) j{r ( )j PRI r = const n ! 1 W) jSr ( )j PRI n = 2r ! 1 G) j{r ( )j PRI n = 2r ! 1. pODKUB BULEWA KUBA (k-MERNYJ) | MNOVESTWO WIDA

f j i

= 1 : : : i ; = n kg GDE 1 6 i1 < : : : < in k 6 n, ( 1 : : : n k) 2 f0 1gn k. zADA^A 5. dOKAZATX, ^TO B f0 1gn QWLQETSQn k-MERNYM PODKUBOM TOGDA I TOLXKO TOGDA, KOGDA PODGRAF GRAFA K2 , POROVD
n

;

;

14

k

;

;

zADA^A 6. nAJTI W n-MERNOM BULEWOM KUBE ^ISLO:

A) k-MERNYH PODKUBOW B) WSEH PODKUBOW W) k-MERNYH PODKUBOW, SODERVA]IH DANNYJ NABOR  G) WSEH PODKUBOW, SODERVA]IH . nABOR PRED ESTWUET NABORU  (OBOZNA^ENIE: ), ESLI 8i i 6 i. nABORY I  NESRAWNIMY , ESLI NI ODIN IZ NIH NE PREDESTWUET DRUGOMU. oBOZNA^IM 0n = (0 : : : 0) (NABOR DLINY n), jj jj = ( 0n) | NORMA (WES) NABORA . zADA^A 7. nAJTI ^ISLO NABOROW , KOTORYM PREDESTWUET DANNYJ NABOR . zADA^A 8 . nAJTI MO]NOSTX MAKSIMALXNOGO PODMNOVESTWA BULEWA KUBA, SOSTOQ]EGO IZ POPARNO NESRAWNIMYH NABOROW. 

sEMINAR 8 (31.10, 4.11) bULEWY FUNKCII: dnf

bULEWA FUNKCIQ (n PEREMENNYH) | FUNKCIQ WIDA f: f0 1gn ! f0 1g. bULEWU FUNKCI@ MOVNO RASSMATRIWATX, KAK RASKRASKU W DWA CWETA WERIN BULEWA KUBA (PREDPOLAGAETSQ, ^TO WERINAM POSTAWLENY W SOOTWETSTWIE NABORY RASKRASKA NE OBQZATELXNO PRAWILXNAQ). |LEMENTARNYE BULEWY FUNKCII | KON_@NKCIQ (f1 (x y) = x & y), DIZ_@NKCIQ (f2 (x y) = x _ y) I OTRICANIE (f3 (x) = x) ZADA@TSQ TAK:

() x = 1 & y = 1 x _ y = 1 () x = 1 _ y = 1 x = 1 () x = 0: kON_@NKCI@ x & y BUDEM TAKVE ZAPISYWATX W WIDE x  y ILI xy. x&y=1

pOLOVIM:



= 1 x = xx ESLI ESLI = 0.

(ZAPISX x MY RASSMATRIWAEM NE KAK FUNKCI@ DWUH PEREMENNYH, A KAK OBOZNA^ENIE DLQ ODNOJ IZ DWUH FUNKCIJ ODNOJ PEREMENNOJ). oBOZNA^IM: W(f) = f 2 f0 1gn j f( ) = 1g. zADA^A 1. nAJTI MNOVESTWO W(f) DLQ SLEDU@]IH FUNKCIJ (ZAWISQ]IH OT NABORA KONSTANT ( 1 : : : n)): A) f(x1 : : : xn) = x1 1  : : : xn  B) f(x1 : : : xn) = xi11 : : :xi , GDE 1 6 i1 < : : : < ik 6 n (POKAZATX, ^TO W(f) | PODKUB) n

k k

15

W) f(x1 : : : xn) = xi1  : : :  xi  16i1 <:::
k

k

i

ik

k

k

k k

k k

0

0

2 W (K).

zADA^A 3. dOKAZATX, ^TO SOKRA]
I  TAKIH, ^TO , WYPOLNENO f( ) 6 f(). zADA^A 6 . dOKAZATX, ^TO MINIMALXNAQ dnf MONOTONNOJ FUNK

16

CII SOWPADAET S E< SOKRA]
sEMINAR 9 (11,14.11) bULEWY FUNKCII: POLNOTA, SHEMY IZ FUNKCIONALXNYH \LEMENTOW

pUSTX P2 | MNOVESTWO WSEH BULEWYH FUNKCIJ, K  P2. oBOZNA^IM ^EREZ K] MNOVESTWO WSEH FUNKCIJ, WYRAZIMYH ^EREZ FUNKCII IZ K POSREDSTWOM SUPERPOZICIJ (ZAMYKANIE MNOVESTWA K). mNOVESTWO K ZAMKNUTO , ESLI K = K] POLNO (W P2 ), ESLI K] = P2 , PREDPOLNO (W P2), ESLI K ZAMKNUTO, NEPOLNO I NE SU]ESTWUET TAKOGO ZAMKNUTOGO MNOVESTWA K , ^TO K  K  P2. zADA^A 1 (PRIZNAK POLNOTY). dOKAZATX, ^TO ESLI Q  P2, MNOVESTWO R POLNO I R  Q], TO Q POLNO. zADA^A 2. dOKAZATX POLNOTU SLEDU@]IH SISTEM: A) f& _ :g B) f& :g W) f=g, GDE x=y = x & y | TRIH {EFFERA  G) f&  1g D) f! :g, GDE x ! y = x _ y | IMPLIKACIQ . dWOJSTWENNOJ FUNKCIEJ K FUNKCII f(x1 : : : xn) 2 P2 NAZYWAETSQ FUNKCIQ f (x1 : : : xn) = f(x1 : : : xn). rASSMOTRIM PQTX KLASSOW BULEWYH FUNKCIJ: T0 = ff j f(0 : : : 0) = 0g | FUNKCII, SOHRANQ@]IE 0 T1 = ff j f(1 : : : 1) = 1g | FUNKCII, SOHRANQ@]IE 1 L = ff = 1x1  : : :  nxn  0g | LINEJNYE  S = ff j f = f g | SAMODWOJSTWENNYE  M = ff j 8   ) f( ) 6 f()g | MONOTONNYE . zADA^A 3. dOKAZATX, ^TO KAVDYJ IZ KLASSOW T0 T1 L S M A) ZAMKNUT B ) PREDPOLON. tEOREMA (KRITERIJ POLNOTY pOSTA). mNOVESTWO Q  P2 POLNO TOGDA I TOLXKO TOGDA, KOGDA Q CELIKOM NE SODERVITSQ NI W ODNOM IZ KLASSOW T0 T1 L S M. pOLINOM vEGALKINA | KONSTANTA 0 ILI SUMMA PO MODUL@ 2 RAZLI^NYH \LEMENTARNYH KON_@NKCIJ WIDA xi1  : : :  xi (1 PRI k = 0). zADA^A 4. dOKAZATX, ^TO: A) L@BU@ BULEWU FUNKCI@ MOVNO ODNOZNA^NO PREDSTAWITX W WIDE POLINOMA vEGALKINA 0

0







k

17

B) BULEWA FUNKCIQ LINEJNA TOGDA I TOLXKO TOGDA, KOGDA E< POLINOM vEGALKINA NE SODERVIT SLAGAEMYH WIDA xi1  : : :  xi k > 2. zADA^A 5. dOKAZATX, ^TO W L@BOM POLNOM MNOVESTWE ESTX POLNOE PODMNOVESTWO MO]NOSTI NE BOLEE: A) 5 B ) 4. zADA^A 6. dOKAZATX, ^TO SISTEMA f0 1 x  y  z xy _ xz _ yzg POLNA, NO L@BAQ E< SOBSTWENNAQ PODSISTEMA NEPOLNA. sHEMA IZ FUNKCIONALXNYH \LEMENTOW (sf|) W BAZISE f& _ :g | NEORIENTIROWANNYJ GRAF (T. E. GRAF, W KOTOROM U KAVDOGO REBRA ESTX ORIENTACIQ) BEZ ORIENTIROWANNYH CIKLOW (T. E. CIKLOW, W KOTORYH R




;

;

;

i=0

i=0

;

18

D ) Q = fMULi (x0 : : : xn 1 y0 : : : yn 1) j i = 0 : : : 2n ; 1g, GDE MULi | i-J RAZRQD DWOI^NOJ ZAPISI ^ISLA x  y, x I y TE VE, ^TO W P. G), L = O(n2) E ) Q IZ P. D), L = O(nlog2 3 ) (METOD kARACUBY). 

;

;



sEMINAR 10 (18,21,25.11) aWTOMATY, REGULQRNYE QZYKI

pUSTX A = fa1 : : : ar g | KONE^NOE NEPUSTOE MNOVESTWO (ALFAWIT ). oBOZNA^IM A = fg  fai1 : : :ai j t 2 Ng | MNOVESTWO WSEH SLOW W ALFAWITE A  | PUSTOE SLOWO. aWTOMAT | NABOR (A B Q '  q0), W KOTOROM: A B Q | ALFAWITY, SOOTWETSTWENNO, WHODNOJ , WYHODNOJ I WNUTRENNIH SOSTOQNIJ  ': A  Q ! B, : A  Q ! Q | FUNKCII PEREHODA  q0 2 Q | NA^ALXNOE SOSTOQNIE. fUNKCIONIROWANIE AWTOMATA NA DANNOJ WHODNOJ POSLEDOWATELXNOSTI x(0) x(1) : : : | POSLEDOWATELXNOSTX (x(0) y(0) q(0)) (x(1) y(1) q(1)) : : :, W KOTOROJ 8t 2 Z+ x(t) 2 A, y(t) 2 B, q(t) 2 Q (x(t) y(t) q(t) | SOOTWETSTWENNO, WHODNAQ, WYHODNAQ BUKWY I WNUTRENNEE SOSTOQNIE W MOMENT WREMENI t) I WYPOLNENY FUNKCIONALXNYE URAWNENIQ : 

t

= '(x(t) q(t)) t 2 Z+ q(0) = q 0 : q(t + 1) = (x(t) q(t)) t 2 Z+ 8 < y(t)

aWTOMAT REALIZUET FUNKCI@ f: A nfg ! B nfg, OPREDELQEMU@ SOOTNOENIQMI y(0) : : :y(t) = f(x(0) : : : x(t)), t 2 Z+ zADA^A 1. pUSTX A = B = f0 1g. mOVNO LI ZADANNU@ FUNKCI@ REALIZOWATX AWTOMATOM. eSLI DA, TO KAKOE NAIMENXEE ^ISLO SOSTOQNIJ MOVET IMETX \TOT AWTOMAT? A) y(t) = x(0)  : : :  x(t), t 2 Z+ B) y(t) = 1 () t ^


: : : = x(t) = 1, t 2 Z+ W) PUSTX t 2 Z+, x | ^ISLO S DWOI^NOJ ZAPISX@ x(t) : : :x(0) (T. E. x = x(0) + 2x(1) + : : : + 2tx(t)), y | ^ISLO S DWOI^NOJ ZAPISX@ y(t) : : : y(0), TOGDA y = x + 1 G) W USLOWIQH P. W) y = cx, GDE c 2 N D) W USLOWIQH P. W) y = x2. dIAGRAMMA mURA AWTOMATA | ORIENTIROWANNYJ GRAF, WERINY KOTOROGO SOOTWETSTWU@T SOSTOQNIQM, NA^ALXNOE SOSTOQNIE POME^ENO 19

SIMWOLOM  I DLQ KAVDOJ PARY (a q) 2 A  Q PROWEDENO REBRO IZ WERINY q W WERINU (a q), POME^ENNOE PAROJ BUKW (a '(a q)). aWTOMAT NAZYWAETSQ BULEWYM , ESLI A  f0 1gn, B  f0 1gm, Q  f0 1gk DLQ NEKOTORYH ^ISEL n m k I q0 = (0 : : : 0). dLQ BULEWA AWTOMATA: x(t) = (x1 (t) : : : xn(t)), y(t) = (y1 (t) : : : ym (t)), q(t) = (q1(t) : : : qk (t)), ' = ('1 : : : 'm ),  = (1 : : : k ), GDE xi (t) yi(t), qi(t) | NULI ILI EDINICY, 'i i | BULEWY FUNKCII FUNKCIONALXNYE URAWNENIQ IME@T WID: = 'i (x1(t) : : : xn(t) q1(t) : : : qk (t)) i = 1 : : : n t 2 Z+ q (0) = 0 i = 1 : : : k i : qi(t + 1) = i(x1 (t) : : : xn(t) q1(t) : : : qk(t)) i = 1 : : : k t 2 Z+. 8 < yi (t)

bULEW AWTOMAT MOVNO ZADATX SHEMOJ IZ FUNKCIONALXNYH \LEMENTOW (sf|) S ZADERVKAMI . sf| S ZADERVKAMI OPREDELQETSQ TAKVE, KAK sf| (SM. SEMINAR 9) ZA SLEDU@]IMI ISKL@^ENIEMI: A) POMIMO \LEMENTOW & _ : IMEETSQ \LEMENT ZADERVKI  S ODNIM WHODOM B) DOPUSKA@TSQ ORIENTIROWANNYE CIKLY PRI USLOWII, ^TO W KAVDOM IZ NIH ESTX HOTQ BY ODIN \LEMENT ZADERVKI. w KAVDYJ MOMENT WREMENI t 2 Z+ NA WHODY SHEMY x1 : : : xn PODA@TSQ ^ISLA x1 (t) : : : xn(t), PRI \TOM NA WYHODAH DOLVNY WY^ISLQTXSQ ^ISLA y1 (t) : : : ym (t) \LEMENTY & _ : DEJSTWU@T SINHRONNO, T. E. W KAVDYJ MOMENT WREMENI NA IH WYHODE WY^ISLQETSQ SOOTWETSTWU@]AQ FUNKCIQ OT TEKU]IH \NA^ENIJ NA WHODAH FUNKCIONIROWANIE \LEMENTA ZADERVKI ZADA




20

zADA^A 4. pUSTX A = f0 1g. qWLQETSQ LI QZYK R  A REGU

LQRNYM? eSLI DA, TO POSTROITX DLQ NEGO REGULQRNOE WYRAVENIE I ZADATX RASPOZNA@]IJ EGO AWTOMAT DIAGRAMMOJ mURA. A) R = f 1 : : : t j 1 6 : : : 6 t t 2 Z+g B) R = f 1 : : : t j t ^ t=2g W) R = f 1 : : : t j @i i = i+1 = 1 t 2 Z+g.

sEMINAR 11 (28.11, 2.12) kODIROWANIE

pUSTX A = fa1 : : : ang I B = fb1 : : : bq g | ALFAWITY, SOOTWETSTWENNO, ISHODNYJ I KODIRU@]IJ , R  A . kOD | FUNKCIQ f: R ! B (INOGDA SLOWOM KOD NAZYWAETSQ OBRAZ FUNKCII f). kOD f ODNOZNA^NO DEKODIRUEM (ILI ODNOZNA^EN ), ESLI 8 2 B jf 1 ()j 6 1. kOD f ALFAWITNYJ , ESLI R = A I SU]ESTWU@T \LEMENTARNYE KODY 1 : : : n | TAKIE SLOWA W ALFAWITE B, ^TO 8ai1 : : :ai 2 A f(ai1 : : : ai ) = i1 : : :i w \TOM SLU^AE OGRANI^ENIE f jA NAZYWAETSQ SHEMOJ KODIROWANIQ . zADA^A 1. pUSTX A = fa1 a2 a3 a4g B = f0 1g. pRIWESTI PRIMERY ODNOZNA^NOGO I NEODNOZNA^NOGO ALFAWITNYH KODOW, U KOTORYH \LEMENTARNYE KODY POPARNO RAZLI^NY. sLOWO  | PREFIKS (SUFFIKS ) SLOWA , ESLI SU]ESTWUET (WOZMOVNO PUSTOE) SLOWO  TAKOE, ^TO =  ( = ). aLFAWITNYJ KOD RAWNOMERNYJ , ESLI DLINY \LEMENTARNYH KODOW SOWPADA@T PREFIKSNYJ (SUFFIKSNYJ ), ESLI NI ODIN \LEMENTARNYJ KOD NE QWLQETSQ PREFIKSOM (SUFFIKSOM) DRUGOGO. zADA^A 2. pOKAZATX, ^TO: A) RAWNOMERNYJ KOD QWLQETSQ PREFIKSNYM I SUFFIKSNYM B) RAWNOMERNYJ KOD ODNOZNA^EN W) PREFIKSNYJ (SUFFIKSNYJ) KOD ODNOZNA^EN. zADA^A 3. pUSTX A = fa1 a2g, B = f0 1g. pRIWESTI PRIMER ODNOZNA^NOGO KODA, NE QWLQ@]EGOSQ NI PREFIKSNYM, NI SUFFIKSNYM. tEOREMA (aL. a. mARKOW). sU]ESTWUET ALGORITM, RASPOZNA@]IJ PO NABORU \LEMENTARNYH KODOW, QWLQETSQ LI DANNYJ ALFAWITNYJ KOD ODNOZNA^NYM, ILI NET. tEOREMA. pUSTX DANY ALFAWITY A, B I NABOR DLIN \LEMENTARNYH KODOW L = (l1 : : : ln) 2 Nn. tOGDA: A) (kRAFT, mAK-mILLAN) ESLI SU]ESTWUET ODNOZNA^NYJ ALFA





;





r

r

r

21

WITNYJ KOD S NABOROM DLIN L, TO n  1 li X i=1

q

()

6 1

B) ESLI NERAWENSTWO () WYPOLNENO, TO SU]ESTWUET PREFIKSNYJ KOD S NABOROM DLIN L. zADA^A 4. pUSTX A = fa1 a2 a3 a4g, B = f0 1g. sU]ESTWUET LI DLQ DANNOGO NABORA DLIN L: 1) PREFIKSNYJ KOD 2) ODNOZNA^NYJ ALFAWITNYJ KOD, NE QWLQ@]IJSQ NI PREFIKSNYM, NI SUFFIKSNYM (ESLI SU]ESTWUET, TO POSTROITX EGO)? A) L = (1 2 2 3) B) L = (1 2 3 3) W) L = (1 2 3 4). pUSTX DANY P ALFAWITY A, B I NABOR WEROQTNOSTEJ P = (p1 : : : pn ), pi > 0, i pi = 1. aLFAWITNYJ KOD NAZYWAETSQ OPTIMALXNYM , ESLI ON ODNOZNA^EN I PRI \TOM Pi li pi ! min, GDE L = (l1 : : : ln) | NABOR DLIN \LEMENTARNYH KODOW. zADA^A 5. dOKAZATX, ^TO DLQ L@BYH A, B, P OPTIMALXNYJ KOD SU]ESTWUET. tEOREMA (REDUKCII). pUSTX n > q, p1 > : : : > pn, n = maxfi j i < n & i  1 (mod q ; 1)g I \LEMENTARNYE KODY 1 : : : n0 OBRAZU@T OPTIMALXNYJ KOD DLQ ALFAWITOW A = fa1 : : : an0 g, B I NABORA WEROQTNOSTEJ P = (p1 : : : pn0 1 pn0 + : : : + pn). tOGDA \LEMENTARNYE KODY 1 : : : n0 1 n0 b1 : : : n0 bn n0+1 OBRAZU@T OPTIMALXNYJ KOD DLQ ALFAWITOW A, B I NABORA P. zADA^A 6. pREDLOVITX NA OSNOWANII TEOREMY REDUKCII ALGORITM NAHOVDENIQ OPTIMALXNOGO KODA (ALGORITM hAFFMANA ). pUSTX A = B = f0 1g R  Ak f: R ! B m | ODNOZNA^NYJ KOD I K | EGO OBRAZ. kOD f ISPRAWLQET r O IBOK (r 2 Z+ ), ESLI DLQ L@BOGO 2 R I DLQ L@BOGO WEKTORA O IBOK  2 B m TAKOGO, ^TO jj jj 6 r, WEKTOR ODNOZNA^NO WOSSTANAWLIWAETSQ PO f( )   (SLOVENIE  WYPOLNQETSQ POKOORDINATNO). zADA^A 7. dOKAZATX, ^TO SLEDU@]IE USLOWIQ RAWNOSILXNY: A) KOD f ISPRAWLQET r OIBOK B) 8 2 K 8 2 K nf g {r () \ {r ( ) = ? W) 8 2 K 8 2 K nf g (  ) > 2r + 1. kOD f LINEEN , ESLI 8 2 K 8 2 K    2 K. kODOWOE RASSTOQNIE KODA f |  K min (  ). 0 K  0

0

0

;

;

;

0

0

0

0

0

0

0

2

2

nf g

22

zADA^A 8. dOKAZATX, ^TO KODOWOE RASSTOQNIE LINEJNOGO KODA RAWNO MINIMALXNOJ NORME NENULEWOGO WEKTORA IZ MNOVESTWA K. zADA^A 9 . pUSTX l > 2, MATRICA M IMEET WID: W PRAWOJ E< ^ASTI PO STROKAM WYPISANY WSE DWOI^NYE NABORY DLINY l, NORMA KOTORYH > 2, W LEWOJ ^ASTI | EDINI^NAQ MATRICA MNOVESTWO K ESTX LINEJNAQ OBOLO^KA STROK MATRICY M OTNOSITELXNO OPERACII . dOKAZATX, ^TO W \TOM SLU^AE KOD f (KOD hEMMINGA ) ISPRAWLQET ODNU OIBKU. 

kONTROLXNAQ RABOTA 2 (5,9.12) bULEW KUB, BULEWY FUNKCII, AWTOMATY, KODIROWANIE

kONTROLXNAQ RABOTA DA 4): f(x y z t) = 1 () C1x + C2y + C3 z + C4t 6 C5 gn(x1 : : : xn) =

_

ijkl

f(xi xj xk xl )

(DIZ_@NKCIQ BER 4 MNOVESTWO W0(gn) QWLQETSQ PODKUBOM BULEWA KUBA, SFEROJ ILI AROM? B) NAJTI ASIMPTOTIKU MO]NOSTI MNOVESTWA W0 (gn) PRI n ! 1. 23

zADA^A 2. nAJTI MINIMALXNU@ dnf FUNKCII f. zADA^A 3. pOLNA LI SISTEMA FUNKCIJ ff x  y  zg? zADA^A 4. pOSTROITX DLQ FUNKCII f sf|, SLOVNOSTX KOTOROJ NE BOLXE C . zADA^A 5. dLQ KAVDOGO n > 4 POSTROITX sf|, WY^ISLQ@]U@ FUNKCI@ gn SO SLOVNOSTX@ O(n). zADA^A 6. pOSTROITX sf| S ZADERVKAMI DLQ AWTOMATA, ZADAN6

NOGO SOOTNOENIEM: 

0 PRI t = 0 1 2 y(t) = f(x(t) x(t ; 1) x(t ; 2) x(t ; 3)) PRI t > 3

ZDESX x(t) I y(t) | ZNA^ENIQ, SOOTWETSTWENNO, NA WHODE I WYHODE AWTOMATA W MOMENT WREMENI t, x(t) 2 f0 1g y(t) 2 f0 1g. zADA^A 7. qWLQETSQ LI QZYK R = fa1 : : :ar 2 f0 1g j r 2 Z+ @i f(ai ai+1 ai+2 ai+3) = 1g 

REGULQRNYM?

zADA^A 8. dAN ISHODNYJ ALFAWIT f1 : : : 4g, KODIRU@]IJ ALFAWIT f0 1g I DLINY \LEMENTARNYH KODOW: C1 : : : C4. sU]ESTWUET LI ODNOZNA^NO DEKODIRUEMYJ ALFAWITNYJ KOD, OBLADA@]IJ SWOJSTWAMI (ESLI SU]ESTWUET, TO POSTROITX EGO): A) KOD QWLQETSQ PREFIKSNYM B) KOD NE QWLQETSQ NI PREFIKSNYM, NI SUFFIKSNYM. zADA^A 9. dAN ISHODNYJ ALFAWIT f1 : : : 6g, KODIRU@]IJ ALFAWIT f0 1 2g I NABOR WEROQTNOSTEJ pi = C + :C: i: + C i = 1 : : : 6: 1 6 pOSTROITX OPTIMALXNYJ KOD. zADA^A 10. rASSMOTRIM KODY, ISPRAWLQ@]IE ODNU OIBKU, TAKIE, ^TO K  W1 (f) (GDE K | OBRAZ KODA) I K IMEET MAKSIMALXNO WOZMOVNU@ MO]NOSTX. A) KAKOWA \TA MO]NOSTX? PRIWEDITE PRIMER TAKOGO KODA B) SU]ESTWUET LI SREDI RASSMATRIWAEMYH KODOW LINEJNYJ ESLI DA, TO PRIWEDITE PRIMER. P = (p1 : : : p6)

24