В.Б. Алексеев, А.А. Вороненко, С.А. Ложкин, Д.С. Романов и др. - Задачи по курсу «Основы кибернетики» (2002) (1132782), страница 2
Текст из файла (страница 2)
w SLU^AE DETERMINIROWANNYH mt WY^ISLENIE ODNOZNA^NOOPREDELQETSQ WHODOM. w SLU^AE nmt OB_EDINENIE CEPEJ, SOOTWETSTWU@]IH WY^ISLENIQM NA WHODE w, PREDSTAWLQET SOBOJ ORIENTIROWANNOE(OT KORNQ) DEREWO S KORNEM C1 = q1w.rASPOZNAWANIE QZYKOW. pUSTX A | KONE^NYJ ALFAWIT. ~EREZ A!OBOZNA^IM MNOVESTWO WSEH SLOW (KONE^NYH POSLEDOWATELXNOSTEJ) W ALFAWITE A. ~EREZ jjwjj OBOZNA^IM DLINU SLOWA w, OPREDELQEMU@ KAK ^ISLO BUKW W w. pROIZWOLXNOE PODMNOVESTWO L A! NAZYWAETSQ QZYKOMW ALFAWITE A. gOWORQT, ^TO mt (nmt) M S DWUMQ ZAKL@^ITELXNYMISOSTOQNIQMI (PRINIMA@]IM I OTWERGA@]IM) RASPOZNAET QZYK L, ESLI DLQ WSQKOGO SLOWA w 2 A! PRINIMA@]EE WY^ISLENIE M NA WHODE wSU]ESTWUET TOGDA I TOLXKO TOGDA, KOGDA w 2 L.
w SLU^AE, KOGDA w 62 L,KAVDOE WY^ISLENIE LIBO BESKONE^NO, LIBO QWLQETSQ OTWERGA@]IM. gOWORQT, ^TO mt (nmt) M RASPOZNAET QZYK L ZA POLINOMIALXNOE WREMQ,8ESLI ONA RASPOZNAET L I SU]ESTWUET POLINOM p TAKOJ, ^TO DLQ KAVDOGOSLOWA w 2 L SU]ESTWUET PRINIMA@]EE WY^ISLENIE DLINY, NE PREWY[A@]EJ p(jjwjj).~EREZ P OBOZNA^IM KLASS QZYKOW, RASPOZNAWAEMYH mt ZA POLINOMIALXNOE WREMQ.
~EREZ p OBOZNA^IM MNOVESTWO OTOBRAVENIJ WIDAf : A! ! A! , WY^ISLQEMYH mt ZA POLINOMIALXNOE WREMQ. pUSTXL1 I L2 | QZYKI. gOWORQT, ^TO L1 (POLINOMIALXNO) SWODITSQ K L2(OBOZNA^ENIE L1 L2), ESLI SU]ESTWUET FUNKCIQ f 2 p TAKAQ, ^TOw 2 L1 , f (w) 2 L2.qZYKI L1 I L2 (POLINOMIALXNO) \KWIWALENTNY, ESLI L1 L2 I L2 L1 .oPREDELENIE 2.1. kLASS NP ESTX MNOVESTWO QZYKOW, RASPOZNAWAEMYH nmt ZA POLINOMIALXNOE WREMQ.pUSTX P2 | MNOVESTWO PAR (L; M ) QZYKOW IZ P.
gOWORQT, ^TO QZYK KWYWODIM IZ PARY (L; M ), PUTEM NAWE[IWANIQ p-OGRANI^ENNOGO KWANTORA SU]ESTWOWANIQ, ESLI SU]ESTWUET TAKOJ POLINOM p, ^TOK = fx : 9y(x; y) 2 (L; M ) & jjyjj p(jjxjj)g;GDE jjzjj | DLINA SLOWA z.oPREDELENIE2.2. kLASS NP ESTX MNOVESTWO QZYKOW, WYWODIMYH IZ2\LEMENTOW P PUTEM NAWE[IWANIQ p-OGRANI^ENNOGO KWANTORA SU]ESTWOWANIQ.qZYK L NAZYWAETSQ NP -POLNYM, ESLI1) L 2 NP.2) DLQ L@BOGO QZYKA L0 IZ NP WERNO L0 L.sPRAWEDLIWY SLEDU@]IE PROSTYE UTWERVDENIQ.uTWERVDENIE 2.1. eSLI L1 L2 I L2 L3, TO L1 L3.uTWERVDENIE 2.2.
eSLI L1 2 P I L2 L1, TO L2 2 P.uTWERVDENIE 2.3. P NP.uTWERVDENIE 2.4. lIBO WSE NP -POLNYE QZYKI PRINADLEVAT P, LIBO NI ODIN IZ NIH NE PRINADLEVIT P. pERWOE IMEET MESTO TOGDA ITOLXKO TOGDA, KOGDA P=NP.kON_@NKTIWNAQ NORMALXNAQ FORMA (knf) NAZYWAETSQ WYPOLNIMOJ,ESLI NAJDETSQ NABOR ZNA^ENIJ EE PEREMENNYH, NA KOTOROM \TA knf OBRA]AETSQ W EDINICU.
pUSTX K | MNOVESTWO WSEH WYPOLNIMYH knf,A | NEKOTORYJ KONE^NYJ ALFAWIT, A | WZAIMNO ODNOZNA^NOE OTOBRAVENIE K WO MNOVESTWO SLOW W ALFAWITE A. dLQ OPREDELENNOSTI RAS9SMOTRIM ALFAWIT A = f(; ); &; _; :; x; 0; 1g, A OTOBRAVENIE OPREDELIMSLEDU@]IM OBRAZOM: BUKWA WIDA xi PREOBRAZUETSQ W SLOWO x1 : : : l, GDE1 : : : l DWOI^NOE PREDSTAWLENIE ^ISLA i; OSTALXNYE SIMWOLY NE IZMENQ@TSQ. nAPRIMER, ESLI K = x1&(x2 _ x5), TO (K ) = x11&(x010 _ x1101).qZYK wypolnimostx (SOKRA]ENNO wyp) PREDSTAWLQET SOBOJ OBRAZ (K) MNOVESTWA K PRI OTOBRAVENII . qZYK k-wyp ESTX OBRAZMNOVESTWA TEH WYPOLNIMYH knf, U KOTORYH KAVDAQ SKOBKA SODERVITNE BOLEE k BUKW.tEOREMA 2.5. (S. A.
Cook (SM. [4, 1, 3, 7])) eSLI L 2 NP, TO L wyp.sU]ESTWUET DOSTATO^NO BOLX[OJ KLASS ZADA^, ZAKL@^A@]IJSQ W RASPOZNAWANII TEH ILI INYH SWOJSTW GRAFOW, CELYH ^ISEL, MASSIWOW CELYH ^ISEL, KONE^NYH MNOVESTW, BULEWYH FORMUL I T. D. pODHODQ]EJKODIROWKOJ TAKIE ZADA^I MOGUT BYTX SWEDENY K RASPOZNAWANI@ QZYKOW.pO\TOMU W DALXNEJ[EM MY BUDEM WZAIMOZAMENQTX TERMINY \QZYK" I\ZADA^A". zADA^I IZ KLASSA P BUDEM NAZYWATX POLINOMIALXNO RE[AEMYMI.nIVE PRIWEDENY NEKOTORYE NP -POLNYE ZADA^I.1. zADA^A 0-1 cELO^ISLENNOE PROGRAMMIROWANIE (0-1 clp).wHOD: mATRICA A = (aij ) RAZMERA p n I CELO^ISLENNYJ WEKTORb = (b1; : : : ; bp).sWOJSTWO: sU]ESTWUET WEKTOR x = (x1; : : : ; xn) IZ NULEJ I EDINICTAKOJ, ^TOAxT bT :2. zADA^A klika.wHOD: gRAF (G; E ), ^ISLO k.sWOJSTWO: w GRAFE G SU]ESTWUET POLNYJ PODGRAF NA k WER[INAH.3.
zADA^A wer{innoe pokrytie.wHOD: gRAF G = (V; E ), ^ISLO l.sWOJSTWO: sU]ESTWUET TAKOE PODMNOVESTWO WER[IN R, ^TO jRj l IKAVDOE REBRO GRAFA G INCIDENTNO NEKOTOROJ WER[INE IZ R.4. zADA^A pokrytie mnovestw.wHOD: sEMEJSTWO F = fS1; : : : ; Smg PODMNOVESTW MNOVESTWA S , PRIS^EM Sj 2F = S , ^ISLO h.: sU]ESTWUET TAKOE PODSEMEJSTWO T F , ^TO jT j h IS sWOJSTWOSj 2T = S .5. zADA^A raskraska.10wHOD: gRAF G = (V; E ), ^ISLO k.sWOJSTWO: sU]ESTWUET TAKAQ FUNKCIQ : V ! f1; 2; : : :; kg, ^TO (u) =6 (v) DLQ WSEH (u; v) 2 E .2.1.
pUSTX A | ALFAWIT SIMWOLOW LENTY mt, A = f0; 1; g, WHODNOESLOWO ZAPISANO W ALFAWITE f0; 1g, | PUSTOJ SIMWOL.pOLOVIM t(n; L) = min maxw2L;jjwjj=n t(w), GDE MINIMUM BERETSQ POWSEM mt, RASPOZNA@]IM QZYK L. pOKAZATX, ^TO t(n; L) = O(f (n)), ESLI1) L | MNOVESTWO WSEH SLOW, NE SODERVA]IH PODSLOW WIDA 111, f (n) =n;2) L | MNOVESTWO WSEH SIMMETRI^NYH SLOW, f (n) = n2.2.2. pUSTX A | ALFAWIT SIMWOLOW LENTY mt, A = f0; 1; g, WHODNOESLOWO ZAPISANO W ALFAWITE f0; 1g, | PUSTOJ SIMWOL.oCENITX SWERHU WREMQ RABOTY mt, WYQSNQ@]EJ1) DELITSQ LI ^ISLO EDINIC W SLOWE NA 3;2) RAWNO LI ^ISLO EDINIC W SLOWE ^ISLU NULEJ;3) W L@BOM NA^ALXNOM OTREZKE SLOWA ^ISLO EDINIC NE MENX[E ^ISLANULEJ;4) SLOWO PERIODI^NO, T.
E. NAJDETSQ TAKOE SLOWO u W ALFAWITE f0; 1g,^TO WHODNOE SLOWO IMEET WID uu: : u};|n {z:RAZ5) PO DWUM SLOWAM u I v, RAZDELENNYM SIMWOLOM , QWLQETSQ LI SLOWOu PODSLOWOM SLOWA v.2.3. pUSTX A | ALFAWIT SIMWOLOW LENTY mt, A = f0; 1; g, | PUSTOJ SIMWOL. oCENIW SWERHU WREMQ RABOTY mt, OSU]ESTWLQ@]EJ SLEDU@]EE PREOBRAZOWANIE, DOKAZATX ^TO ONO LEVIT W :1) SLOVENIE DWUH CELYH ^ISEL W DWOI^NOJ ZAPISI;2) UMNOVENIE DWUH CELYH ^ISEL W DWOI^NOJ ZAPISI;3) NAHOVDENIE OSTATKA OT DELENIQ ODNOGO CELOGO ^ISLA W DWOI^NOJZAPISI NA DRUGOE;4) NAHOVDENIE OPREDELITELQ KWADRATNOJ MATRICY IZ NULEJ I EDINICW POLE E2 IZ DWUH \LEMENTOW S OPERACIQMI I &;5) UMNOVENIE DWUH KWADRATNYH MATRIC IZ NULEJ I EDINIC W POLE E2IZ DWUH \LEMENTOW S OPERACIQMI I ;6) RE[ENIE SISTEMY LINEJNYH URAWNENIJ W POLE E2 IZ DWUH \LEMENTOW S OPERACIQMI I ;117) NAHOVDENIE ZNA^ENIQ BULEWOJ FUNKCII PO FORMULE NAD BAZISOMf&; _; :g NA NABORE (1; : : : ; n) ZNA^ENIJ PEREMENNYH;8) NAHOVDENIE KORNQ POLINOMA vEGALKINA, T.
E. NABORA, NA KOTOROMPOLINOM OBRA]AETSQ W NOLX;9) NAHOVDENIE KRAT^AJ[EGO RASSTOQNIQ MEVDU DANNOJ PAROJ WER[INW GRAFE;10) POSTROENIE OSTOWNOGO DEREWA GRAFA.2.4. rASKRASITX GRAF G W k CWETOW:1) G - GRAF NA RIS. 1, k = 3;2) G - GRAF NA RIS. 2, k = 2;3) G - GRAF NA RIS. 3, k = 3;4) G - GRAF NA RIS.
5, k = 2;5) G - GRAF NA RIS. 7, k = 3.2.5. nAJTI RAZMER MAKSIMALXNOJ KLIKI GRAFA:1) G - GRAF NA RIS. 1;2) G - GRAF NA RIS. 2;3) G - GRAF NA RIS. 3;4) G - GRAF NA RIS. 8;5) G - GRAF NA RIS. 9.2.6. nAJTI MINIMALXNOE WER[INNOE POKRYTIE GRAFA:1) G - GRAF NA RIS. 1;2) G - GRAF NA RIS. 2;3) G - GRAF NA RIS. 3;4) G - GRAF NA RIS. 4;5) G - GRAF NA RIS.
6.rIS. 1.12rIS. 2.rIS. 4.rIS. 6.rIS. 3.rIS. 5.rIS. 7.rIS. 8. rIS. 9.2.7.dOKAZATX POLINOMIALXNU@ RE[AEMOSTX ZADA^I2-wypolnimostx.2.8. pOSTROITX PREOBRAZOWANIE WHODA ZADA^I L1 WO WHOD ZADA^I L2,DOKAZYWA@]EE POLINOMIALXNU@ SWODIMOSTX QZYKA L1 K QZYKU L2:1) L1 ESTX wypolnimostx, L2 ESTX 01-clp;2) L1 ESTX wypolnimostx, L2 ESTX 3-wypolnimostx;3) L1 ESTX klika, L2 ESTX wer{innoe pokrytie;4) L1 ESTX wer{innoe pokrytie, L2 ESTX pokrytie mnovestw.2.9. dOKAZATX NP-POLNOTU ZADA^ 1 { 5 IZ WWEDENIQ K PARAGRAFU.2.10.
dOKAZATX, ^TO SLEDU@]IE ZADA^I QWLQ@TSQ NP-POLNYMI:1) SU]ESTWOWANIE NABORA, OBRA]A@]EGO dnf W NOLX;2) SU]ESTWOWANIE NABORA, OBRA]A@]EGO dnf W NOLX PRI USLOWII,^TO KAVDOE SLAGAEMOE \TOJ dnf SODERVIT NE BOLEE 4 BUKW.2.11. wYDELITX SREDI PERE^ISLENNYH ZADA^ POLINOMIALXNO RE[AEMYE I NP-POLNYE:131) SU]ESTWOWANIE DWUH PROTIWOPOLOVNYH NABOROW, NA KOTORYH dnfOBRA]AETSQ W EDINICU;2) SU]ESTWOWANIE DWUH PROTIWOPOLOVNYH NABOROW, NA KOTORYH dnfOBRA]AETSQ W NOLX;3) SU]ESTWOWANIE NABORA, NA KOTOROM POLINOM vEGALKINA OBRA]AETSQ W NOLX;4) SU]ESTWOWANIE NABORA, NA KOTOROM ZADANNYE POLINOMY vEGALKINA (KOLI^ESTWO KOTORYH ZARANEE NEIZWESTNO) ODNOWREMENNO OBRA]A@TSQW NOLX;5) SU]ESTWOWANIE \JLEROWA CIKLA W GRAFE (\JLEROWYM CIKLOM NAZYWAETSQ CIKL, PROHODQ]IJ PO WSEM REBRAM GRAFA, PRI^EM PO KAVDOMU WTO^NOSTI ODIN RAZ);6) SU]ESTWOWANIE GAMILXTONOWA CIKLA W GRAFE (GAMILXTONOWYM CIKLOM NAZYWAETSQ PROSTOJ CIKL, PROHODQ]IJ ^EREZ WSE WER[INY GRAFA);7) RASKRASKA WER[IN GRAFA W DWA CWETA (GRAF MOVNO RASKRASITXW DWA CWETA, ESLI KAVDOJ EGO WER[INE MOVNO PRIPISATX CWET TAKIMOBRAZOM, ^TO SMEVNYM WER[INAM PRIPISANY RAZNYE CWETA);8) RASKRASKA WER[IN GIPERGRAFA W DWA CWETA (GIPERGRAFOM NAZYWAETSQ PARA < V; E >, GDE V | KONE^NOE MNOVESTWO WER[IN, E , E 2V ,| MNOVESTWO REBER; GIPERGRAF MOVNO RASKRASITX W DWA CWETA, ESLIKAVDOJ EGO WER[INE MOVNO PRIPISATX CWET TAKIM OBRAZOM, ^TO L@BOEREBRO BUDET SODERVATX PO MENX[EJ MERE DWE WER[INY, OKRA[ENNYE WRAZNYE CWETA).2.12.
wYQSNITX, KAKIE IZ PERE^ISLENNYH ZADA^ QWLQ@TSQ POLINOMIALXNO RE[AEMYMI, KAKIE | NP-POLNYMI:1) RASPOZNAWANIE NELINEJNOSTI BULEWOJ FUNKCII, ESLIA) FUNKCIQ ZADANA TABLICEJ SWOIH ZNA^ENIJ,B) FUNKCIQ ZADANA FORMULOJ,W) FUNKCIQ ZADANA W WIDE dnf,G) FUNKCIQ ZADANA W WIDE SOWER[ENNOJ dnf,D) FUNKCIQ ZADANA W WIDE POLINOMA vEGALKINA;2) RASPOZNAWANIE NEMONOTONNOSTI BULEWOJ FUNKCII, ESLIA) FUNKCIQ ZADANA TABLICEJ SWOIH ZNA^ENIJ,B) FUNKCIQ ZADANA W WIDE dnf,W) FUNKCIQ ZADANA W WIDE SOWER[ENNOJ dnf,G) FUNKCIQ ZADANA W WIDE SOKRA]ENNOJ dnf,D) FUNKCIQ ZADANA W WIDE POLINOMA vEGALKINA;143) RASPOZNAWANIE NESAMODWOJSTWENNOSTI FUNKCII, ESLIA) FUNKCIQ ZADANA TABLICEJ SWOIH ZNA^ENIJ,B) FUNKCIQ ZADANA FORMULOJ,W) FUNKCIQ ZADANA W WIDE dnf,G) FUNKCIQ ZADANA W WIDE SOWER[ENNOJ dnf,D) FUNKCIQ ZADANA W WIDE POLINOMA vEGALKINA;4) SU]ESTWOWOWANIE W GRAFE k-KLIKI (k-KLIKOJ NAZYWAETSQ PODGRAF,QWLQ@]IJSQ POLNYM GRAFOM S k WER[INAMI), ESLIA) ^ISLO k ZARANEE IZWESTNO,B) ^ISLO k PODAETSQ NA WHOD mt WMESTE S GRAFOM;2.13.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
