Романов В.Ф. Математическая логика и теория алгоритмов. Задачник

Подождите немного. Документ загружается.

з) tloиск

Ira

Грaфе в глyбиIry;

и) зaдaнa

кoМMиBоя)кepa;

к) ЁьI.rисле|IИe

n-Tovислa Фибoнaвuи;

n) oпprдеЛениr xpoN{aтичrскoгo

нислa гpaфa;

м)

опpeдeление

цикJloмaти.iескoгo

uислa гpaфa;

н) зaдaнa o xaнoйскoй

бaпrне;

зaдaчa

BЬlIIoЛI{иМoстlа

бyлевoй

фоpмyльr.

3, BьtДелить из гpaфa

(pис'l)'

pебpaм

кoтopoго

пpиIIиоaнЬI

цeJIoчис-

ЛеннЬIе

''вeсa'',

деpeвo

МиIlиМaЛьIIoгo

(мaкоимaльнoго)

cylvt\,IaрнoГo Bесa'

сoдeр)I(aщее всe BеpIIIиIIЬI

исXoдI{oгo

гpaфa'

!дя

peпreни

зaДaЧИ иопoльзoBaTь

аJIгopиTМ

Кpyокaля.

4' ПpoнyмepoBaв прoизвоJlьtlo

BeрIЦиI{ьI

гpaфa' изoбpalкенного

нa

pllоytlке

1, пpивeсти rlopядoк

пеpeбopa веpIЦиIr

дnя

aJIгopI,rтN{oв пoискa в

гpaфe:

a) в глyбинy;

б)

в rпиpинy.

Укaзaть aсиМIIтoTическиe

сЛo)кнoсти сooTвeтстByloщиx

аJrгopитМoB'

5. }Iaйти

рaскpaокy

веpIIIиrr

гpaфa

фис.2)

''жaднЬtм''

ttлгopитMo]\4.

Pис.l

Pvrc.2

6. Haйти

paскpaокy

BеpIIIиЕr гpaфa, изoбpaжeннoго

нa

мoдифициpoBaв )I(aдI{ьIй аJIгopI.тм

сJIeд}.IощиМ

oбpaзol\,t:

paскpalllивaтЬ

нa oчepeдIloм IIIaгe вeprЦинy,

связaннylо

IЦI{м

чисJIoМ

нepaскpalllенIrЬrx веpIIIиIi;

нaЛo)I(ить

вЬIтекaIoщие иЗ тIpeдЬI.цyщегO

IIIaгa зaпpетьI.

pисytrкe

наибoль-

Yц

Чемy

pавно

xpoМaтцчeскoе

чисЛо

.цЛЯ

этoго гpaфa?

Являeтоя ли э1тlT

гpaф плoским?

7. oпpедeлиTЬ хpoМa.гическoe

чисllo

дЛя

I1oлI{огo

гpaфa, сoдеpжaщeгo:

a) 5 веpтлин;

б) и веpu.rин

8. oпplэделиTь xpoМaтичeскoе

Числo

для

гpaфa с пятЬIo

вepшиЕaМи

пятикoнеч !]oй звeзДьI.'.

Кaкoвa

aсимптoтическaя

слoжIloсть

aтIгopитМa

.цля

этQй

зaдa.rи?

Те хtе

вoпpoсЬI

.цЛя

гpaфa

с вocеМЬIO

Bеplпинalllи

''тpехмеpнoго кyбa''.

9. Кaкс'й гpaф

нaзьIвarTся

дByДoльньrм?

BстpечaЛся ли в paссМoTpeн-

I1ЬIх BьIIIIе з]a.цaчaх

лвyлольньrй

гpaф?

10. Классифицирoвaть

IIo

сло)кttoсTи

слe.цyioщиe

зa.цaчи

МaTеМaTиче-

скoЙ лoгики:

BЬiПoЛHИl/IoCTЬ

(BЬIП);

2.BЬnПoЛI{I4МoCTЬ

(2.BЬrD;

3-BЬIПoЛHИМoCТЬ

(з-BЬIП).

1]. BьrlтoлниТь lloлинoМиaЛьI{oе

пpеобpазовaнI{е

зa/цaчI{

BЬIП

в зa.цaчy

3-BЬIП

.цля

слeдy}oxцих

ltсxoд}IЬrx

фopмyл:

a) F: х1(-х2У

]xз

х4

V зХ5

V х6)

(xg

-х16),

б)F:

(-х1

х2)(-.*3 v

-xa)(x5v

-х6

v.x7)(;r3

rХ9V

-x1g

r11)'

|2'

oписaть

пpoцeдypy

lloли}IoМиaльнoгo

пpeо6рaзoвaния

зaдaчи

''гaмильToнoв

ЦикЛ1l

''ЗaдaЧy коМMиBoя)I(epa''

дЛя

I]poизвoJlЬнoгo

грaфа'

13 . Какoвa взaимoсBЯзь

N{aпIиFIЬI

Tьrоpингa,

пре.цнa:'flaчецнoй

дJIя

кон-

кpеTtloгo Bь]tчисJ]е}It{Я,

yнивepсaЛЬнoй

МaшиHoй

Tьropингa?

14. Пplтвести

tЦ]иМеpЬI

Зa.цaч'

для

кoтopьIx

спрaBe.цливЬI

yтBep)кДения:

зaдaчa

pеrшaeтся

кotIечl]ьIM авToMaTоN{;

ЗaДaчa не

prцIaеTся

кo}Iеч}lЬII\4 aвтoМaтоМ'

IIo

pешIarTся

I\4aIIIиноЙ

T.ьюpингa:

зaДaчa }Iе pе[laеTсЯ

Мaшинoй

Тьюpингa.

l5.

.Ц,aз:ь

pel(y]]cивI{oе

oIIpеделеI{ие пpaвилЬI{oГo скoбoчнoгo вЬipa)кr.

t1|4я.

16.

!aть

peкypоивнoе

oПpеДелениe

клaссa

pеryляptlЬlx

вьtрarкeний.

!ать

peк1,pсиBнoe

oflрeДелениe

цeпoЧки

наД l|екoтoрЬlM aЛфaBи-

ToIи' исIIoЛЬзyя

IIоH'ITия

пyстoй

цепorlки

и кoнкaTe}Iaции

(пpисоeдтаlleния)'

18.

.{oкaзaть,

tтo rшoбaя

пpиМитивtto

peкypcиBlraя

фyнкция

всtoдy

olr-

pr.целеI{a.

|9.

Кaкaя

фyнкция

пoл).rlaется из пpoстeйrшиx

с пoМoщь1o

лI,IшЬ сy-

пеpпoзиций?

20. Кaкaя

фyнкция

rlолyЧarтоя из

с пoмoщЬIо схеМьI IlpI{l4I,rTив.

нoЙ

peкypсии:

Ф(х):x; v

(х,у,z\=

z*;

б)

Ф @):';

(х,у,z):

х, .

2|.

[aнa

мaтpицa

А:

I\4}lo)кrсTBo eе эЛeМеItTов Е:

{аn,аp,

,.'

a1t

}

двa

ollpе.цrления семeй-

стBa lloдмнoжeств

-I(.I1)

мнoжествa Е:

a) 1 е J, если B

}Iегo

BхO.циT не бoлее oднoгo

эЛе]vtеI{тa I,lЗ кaждoГo

столбЦa;

б)

1 €

acЛvI B

негo

Bхoдит нe бoлее

одtloгo элеl\,{еIIтa

из

кaждoй

отрoки

и кФкдoгo

стoлбцa.

,Ц'aнo

мнoжествo B

{аn,

Q22,

a32, a16\,

Зaдaния:.

,{oкaзaть

6ез испoльзoBal{ия пoIUlтия х(a.цI{oгo

aJlГopитмa' чтo

систеМa IVI:

(E,

мaтpoид;

систеМa Mt:

(Е,4)

t{е мaщoид.

2) oпpеделить

pallг

)

в МaTpoи.це M:

J).

Haйти oбoлovкy sp

)

в IuI.

4) Укaзaть кaкoй.либo

ц}tкJI

Явlтяетcя Ли otl

циклoмв

7,[2

Пpивости IIpиN{еp бaзцca M.

6) oпpeделить

paнг

(Е.)

мaтpouДa M.

Coвпaдaeт JIl! ol{ с

palIгoм

flaзиctil

5 tl

з 4

l|'

OTBЕTЬI"

PЕIIIЕIIия.

УкAЗA}Iия

Pазdел

l. B тa6лице

истиннoсти

пoдIгoToвитЬ сToJIбцЬI

для

пoдфоpмуII Ll

Иc-

IloлЬзoвaтЬ у1х.

ДI|я

вьIчrlсЛеIlI]tя зIlaчений

фopмyльr

нa нaбоpaх пepсМeнЕIьIx.

[ля

свeдel{иll

сисTeМ,

.цJIя

кoтopьIx

дoкaзьIBaется

IIoлE{oтa'

к изBeст-

нoй ФПС BoсIloльзoвaтЬсЯ

зaкoнaМи

де

Мoргaнa.

- 4.

AссoциaтиB}loсTЬ

oliеpaцI]tи

мoжет бьlть

пpoвеpеIta

пo

тaблицe

истинIloсти'

.I{ля

теopeтикo-Мtlo)кестBrIIIIoI"I

инTеpпpeTaции

слrДyrт снaчa.

JIa сBeсTи

зaдaннyto

oпepaци}o к бaзисy

\u,

a зaтеlt BоспoльзoвaтЬся

ссloTBеTстBием

Междy бyлeвьtми

oПеpaциями B JIoгике и B Tеopии

м}lo)l(есT'в.

5. Испoльзoвaть

тaблицьt исTиtIнoсти иЛи

сBrдеItие

oпеpaций

к бaзисy

Бyля.

g.22n.

9. HeоyщестBеI{нa,I

IIepеМеннa;I

Ilе

вЛиЯeт

нa зЕaчellиe

фyнкции

пpи

лtобьlx сoчетaнияx знaчeний

oст€}ль}tЬIх перемеI{ЕЬIx.

,{ля

aнaлизa пoстpo-

ить тaблиЦьI

исTи[Itloсти.

10.

Испoльзoвaть

C.{HФ

(сКHФ)

/цJUl

llеpеxo/цa

oт тaблицьI истиItЦoсти

к aнaлиTичесt(oNry

пprдстaвЛеltиto

фyнкций,

a тaкх(e

зaкoltьI

де

Mopгaнa.

Пpи вьIшoлнеIlиI{

oчеpе.цt{oгo

IIyнкTa

мoгyт

бьlть

IIoлeзньIМи

IIpедьIдyщIlе

пyf{ктьI.

l l. Hельзя. Мнoжествo

{

}

пpедстaвляет сoбoй зaмКIryтyto

систеМy.

12.

Bоспoльзoвaться pезyJlьтaтaми

pеIцеtIиЯ

зaдaчи

10.

14,

[лп

lrepexo.цa

к бaзисy

Жегaлкинa

в C,{HФ или

СКHФ следyrт зa-

MrниTЬ oтрI{цal.lия

(lx

Ф 1),

Дtзъюнкции

(х

ху

х Ф

и вoс-

пoЛЬзoвaтЬся

свoйствaми

оIIеpaцРIи Ф, в нaстносTи,

диотpиGyтивнoстьto

кoнЪroнкциI.r oт}loсителЬнo

олo)l(еЕIия

пo

mod

15'

(a)

нe сoxpaняeт

.'l'.,.a

oстальrrьIr

yкaзaHньlе

oПepaции

сoxpa-

няrот;

(б)

нели1tейнaяoпepaцwЯ'a

-линейньr.

16. Пpoaнализиpolraть

сBoйсТBa

фyнкций,

вхoдЯщиx B сисTеМьI' со-

гJiасtlo

oбщей теopeМо

фyнкциoнaлЬнoй

пoлнoте'

]'7.

Системa пoJIнa.

,{ля

пpедстaBJIeния

в нeй

oпеpaциu

исIIoль.

зoвaTЬсooтHoIIIеIlия:

хФу=

-XУ

vз|хi зX:X э0;

ху:

-(х

-y).

18.

PaссмoтpeтЬ

слyчatl:

C):

v C)

l, сpaвниBЛеBуIo и

гIpaвFо

чaсти B

кa)кдoМ из ЭТиx сЛyчaеB.

19.

Лoгическaя

фyнкция

,,Ес!Iуl

To 6

инaче с''

фyнкЦиЯ

Tpеx

лoгическиx ПepеI\iteнньIx;

(z'

b lа

oнa пpинимaет

зI{aчe}tиe

b, ecли а

исTиIlнo' и

с в

ПpoтиBtlоМ

слyчar.

!дя

pешeния

зaдaЧи

дoaTaToчнo

tlpoBеpиTь, яBляeтся ли

набop

IlеpеЧислrнньlx

фyнкций

ФПC.

20.(a)

(А

nB)u B= U.

Pазdeл II

1.(a)

(в)

ПpeдикaтьI;

пpeдI\4еTl{aя

oблaсть

Мtlo)I{естBo

деГаствитель-

IIьIХ чI,IсeJI'

(г)

Tекот.

(д)

Лolкнoе

BьIск€lзЬIBaние.

!ля.цoкaзaтеJIЬсTBa

дoстaToчнo даТЬ

тoчIlylо

слoвеснyto

иl{TерпреTa-

циIо

лeBЬIx

[I пpaвЬIx чaстеЙ

Пpивe.цeнньrx

вьtpaхсeний.

З. Paзбить кaждьtй

пyЕIкт нa

дBе

llo'цзaдaчи:

Г:

(false)

ъl 7,:

(true).

4, BoспoльзoBaTься

пoHlITиеI\{

I\,tlloжeсTвa истиHItoстI1r

дByMестltогo

пpедI-Iкaтa.

Hе

спpaведливa. Paссмотpеть'

нaПpиМep,

ПpедикaT

.'x

нa

числoвoй пpе.цметной

облaсти.

.6.

Пpoвeсти

paссynцrЕия

пpедМетIrЬIмlt oблaстями и М}to)I(есTвaMI,l

истиtlнoсти

пpе.цикaтoв

yсТa}IoBиTЬ'

B кaкиx сЛyчaях леBЬIe

и flpaBЬIr

чaсти IlpиBедеIlt{ьIх

вьlpaжений oднoвprltleннo

ptстиIILIЬt

либо лоrкньi.

Пpимеp,

oпpoвеpгaloщultl

диcтpибyтиBIIoaT.Ь:

М;

o MQ: О,rДe

пpeдDtеT}Iaя

o6лaсть

пpе.цикaToв P{х)

Q.@),

Мp и

Мq

сooтветсTBeнЕo

llx

MltoжесTBa

исTиtlItoсTlI

(

Mp ll Лy'q oбрaзyrот

paзбиение мнolкествa

i1).

пpиведeннoй

фоpмyЛе

I,rсIIoлЬЗyIoтся

ToJIькo oПеpaции

IIpичем

oTpицa}rие

МoжeТ

oTlloоиться

к пpедикaTaМ

и BьIcк€tзЬIвaниям' нo tIе

кBaнTopaM.

9. Mнoжествo

истиtlнoсти IIpедикaTa

F(x} пpедстaвляет

сoбoй пpoек-

циIo

нa oсь

дByМеpнoй

фиryрьI

Irtt{oжeстBa

истиIlносTи

.цByМесTIloго

пpедикaтa

P(х,у),

l0.

Paссмoтpеть

кaчестBe

Mнo)кествa

истиIlнoсTи Предикaтa

P{х'

у)

tloЛосy'

oгрa1rичeннylo

Пo ocи

.т

oTpезкoМ

[0,

1], нo

не oгрaничеFIItyю

IIo

oси

|А

1l. Vл P(x) :э

3х

Л(х)

<э

-(Vх

P(х)) v

Зх

Л(х) сэ Зх-P(x)

Зх.R(x) е

е 3.r

(-P(x)

Л(х)) сэ 3л

(P(х)

э Л(х)).

|2.

Yх Yу

1u x'у 1w P(х,

у,

z) |l,

w) е) Yу Yz

P(а,

у,

z,f

Ql,

z), v,

z,у)),

1 3.

oгpaниuенньrпl пpeдi.tкaтoМ l]aзьrBaeтся пpедикaT'

oпpеделeнньtй нe

нa всей пpeдметнoй обЛaоти, a нa

МItox{eстве

пpeдМетoв'

yдoBJlеTBopяIoщих

дoI1oЛниTr.пьIroNly

yсJIoвиIо.

Пpимep:

V(x е

Р(")

,цля

Bcex x' пpинaдлeжaщиx мнoхсеcтвy Х,

Р(х)

11цg.

Pазdел III

Hеинвapиa}IтI{aя cеTЬ Пeтpи lvrо)кет бьrгь oгpaниченнoй иJIи

llеoгpa-

rrиченнoй.

Неoгpaнивеннa,l

сеть

Пeтpи не

инBapиaHTHa.

2' Еоли

.lислo

lre

деЛиTcя

нa З илll

I{r

деЛиTсЯ

нa

oнo не

делиTся

нa б.

3. Пepвое

}/тBеpждениe

нy)I(дaется B

дoкa:!aTельстве.

Bтopое сIIpaBеt-

ЛиBo.

Aнaлиз

Мoх(нo

ltaчaтЬ с тoгo' чтo А

м6o

вpет,

либо гoBopит пpaвдy.

I7aiпи

BapI{aнт сrцеI{ки yтвеpждений

B и

не IIpивoДяrIIий к пpoтивopе.

чti}o.

Bве"цeм обoзrraчения: P

pимлянин;

Пpедaн

дикTaтopy;

нe-

}IaBи"цит

диктaTоpa;

У-.пьrтaется

yбить

диктaтopa.

Тoгдa

Пo oTI{oшIeниIo

к Мapкy cпpaведдиBьI

сЛедyloщиe

зaкo,циPовaн.

нь1r IIOсьIЛки:

С]:

С2:

-П;

С3: P

-э

(П

IО, в

дизъ}oнктивнoй

фopме:

(-Р

П v

H);

C4: It Э У, в

дизъIotlктltвнoй

фopмe:

(-Hv

У);

ДЛЯ

тIpиМеIleния

Мeтoдa

pезoлroций

сoстaBляеTся KoI{ъIонкTиBнaя

фоpмa,

сoДepжaщ€Ц посьIJIкII !r oTpI{цaIrие

пpед(пoЛaгaеМoГo

зaкJIЮчeнI.Я

(СJ:

-У):

-Ir

(-P

(-H

-У.

.{,aлее

oтьlскивaloтоя

peзoльBеI{тЬI' I(oтoрЬle

могут пр]исoеДи}rятЬсЯ

11ocЬIJIкaI\,I:

Сl и C3

дaroтpeзoJlьвeнтy

.R1;

(Пv

II);

С2

ll RI

,цaк'T

peзoлЬьerIтy

R2:

;

vт С4

дaЮтpезoJIЬвенry

R3; У;

С5

дaIот

кaчестBe

pезoльвeЦтЬI пyотoе

пpедлox<енlre:

(

,{окaзaтельствo

зaкoнllеIlo:

Мapк IIьIтaлся

yбить

l{eзapя.

Bьlвoд

пеpBoгo

paссy)кдeIIи,I нeBеpеtt. Мeтoд

prзoJIIoции

ttе IIoзBo,rя.

ег пoлyrить

.'(

)''.

Bывoд

втopoгo

paссy)кД,еIrI,Iя

нeBrpeн

Iiе

хBaтaeT исxoднЬIx пoсьIлoк

(нет

фaктa,

из кoтopoгo

следyeТ' vтo

pыбьt

}Ir IIpиIra.цлrжaT

к TrплoкpoB-

ньtм).

[ля

пpoвеpкIt

тpeтЬrгo

paссy)l(дeн}Iя ввeдeМ

oбoЗнaЧeнияi M

|\rcтaJlЛi

П_плacтичньrй;К_кpистaллический'

ПосьI-'tки: M э

--II;

К э

-П.

oтpицaяиe

пPrдIloлaгaеМoгo

зaIшIoчеIII{,l:

-(Mэ

К) э M-К. Кoнъrонк-

тивIlzl't

фopмa

для

Метoдa

pезoлtоций:

(-M

-.1)

(-к

-П)

M-К.

Пеpвyrо

и BTopyк) скoбки

N,roжIlo исклIoчиТь

oни сoдеp)кaт

yЕикaлЬ.

ньtй литеpaл

-П'Из

кoнъrс!нкции

Il,I-К пуcтae llpедЛox(ениe

нe

вЬlBoдиT-

ся, сЛедoвaтелЬt{o,

BьIвoд

рaссy}кдеrrия

нeBеpеЕ'

Четвертoе

paосy)кдeнlre

вepнo.

oбoзнaчeния:

дельф+lн,

Kит'

pьtбa.

Кoнъюнrгивнaя

фopмa:

(-Д' v

к)

(-P v

-К)

Пyстoe

пpeдлo)кение

легкo

BьIBo.циTся.

Пpuмeuанuе.

oтрицaние

пpeдпoлaгaeМoГo

зaклIoЧeIIия

-(P

-,\

)

P,Ц.

7.Из

aкcиoмьl'

,4] llcчllcJlения

высказьIвaнlrй

следyeт тeopeмa

T1:

Qээ

((pэ

p)э p))

(в

aксиoмy

А] вмecтo

пеpвoй

I{ет:UIзЬIкoвoй пеpеменной

пoдотaвленa

ПpoПoзицI{ottEшьнaя

пеpемеItнaя

a вe,есTo

втоpoй

фopмyпa

эЙ).

ИзaксиoмьI

А2

итeopeмы

Т1

слeдyеTтеopеI!{a

T2:

(1l

(Ф

p))

((p

Эp))

p))'

Из

T2 IIo

пpaвиJly

BьIвoдa

modus

poпens

следyеT TeoprМa

T3:

({pэ(pэp))эФэЙ).

Из

aксиoмьt

А1 cлeдуe'т,.lтсl

_.тeoprl\,{a.

T4:QlэФэd).

Пpиrvrенив

пpaBиJIo lпodus

poпens к

Шl с

yЧеТoМ

T4,пoлунaeм

теoреМy

T5:

Qэ

p).

8. Bв'эдeм обoзнaчения:''Cк

скaзал; И-

yзвaлa;

Сп

cпpocvтлa. Имeeм

пoсЬtлкlI:

FI:

*.Ск

-У;

F]:

-,Сtэ

э :Cк;

FЗ:

}/;

Предlпoлaгaeмьrй

вьrвoд: R:

Cn .

Cоглaснo тIpиIrципy

кot{тpaпозиции :

-Ск

э-Иё

эСкi

-|:n

Э-Сk э Ск эCп,

Пpименим

Два)кдЬI

cиллогизIvl modus

ponеns;

УэСк

С"

Ск

эСп

Сn-*

Сп

Bьtвсlд lloд(TBеpiкде}r.

oбrэзнaчим: I_

щyо;

-7'_

нaстoящий

мyжиинa

(не

тpyс);,Y-

игpaть

Хoккей.

Конъlонктlrвrraя

фоpмa

/1ля

МеToДa

prЗoЛtoЦии: (-Y

-T

)

-X

-T

Пyст,oe

ПprдJlo)кrние

IIе BьIвo.циTоя, сЛе.цoвitтелЬ!{o'

вьlвoд

''я

тpyо''

Невepr}r.

10. OбознaчиIr,t:

Z-

''тетя

Чapпи.'; B

''видеть

TeтЮ

Чapли

вМестe''.

Пpиltеним

сиЛлoгизN{

modus

ponеns:

T:эБ|

tл

-T

11'

С>.lемa

рaссyхt;1ений

с испoльзoвal{иеl\{

силлогизмa modus

ponеns:

1) Vx

|Челoвек

(х):э

(-..меpmен

(х)h

(.F

|Чeлoвек

('Сoкpаm\:

(R)

Cмеprnен

(Сoкpаm).

Пpи

pеrueниvI ЗaДaчИ

мeToдoМ

peзoлtоций снaчzrлa

цз F I rl,

-Л

(с

lloд.

сTaIroBкoй

вМесТo пеpеМeнIroй

x кoЕотa}ITьI Сoкpаm) IIoлyчIап,I

pезoлЬE}еI{-

Tу

-Чeлoвек

(Coкpаm)'

котopaя сoвместнo

пpедлo)кеIlиeм

,цaет

в кa-

честBе

нoвой

pезoлЬвеtlтЬI

Пyстoe

ПpедЛo)кeниe.

|2. Иcпoлъзoвaть

сxеI\{y

силлoгизMa

modus tollеns с IIредJIo}кеIlиеlll

-Сл,tеpmен

(Кащeй)'

3. Пеpвaя'raсть

aфopизмa:

-(Зх-Зy

P(у,

v х 1у P6l, х1,

гдr пpe.цикaт

P(у, *) нa

Мнoяteствe вeщeй

oзнaчaет

.'Bеlць

пpевoсхоДит

величинoй

веlцЬ ,''.

Bтopaя

.raсть

aфopизмa

(Vy

ЗхP(;t'

x))

не тождeсTBеннa пеpвoй.

(a)

1х P(х)

Vх

+ х)

-(P(у)

& Р(x))

(инavе:

|Mp|

1).

(6)

зx ]

b,+

х)

(Po)

P(x))

(инauel

|Mo|>2),

Зaпись

oтpицaний

ttpиBеденrrьIх

tIpе.цикaToB IIe coсTaвЛяrT

Tp)r.цнoсTи'

15.

(a)

фоpмyле

_унwкaлъньrй

литеpaл. Исклroчив

ДиЗЪIotlктЬl'

сo-

деp)I(aщиe

d, o6нapу>киBael\{'

чTo

yникaJIьItьlй

литepал. }Iтaк'

достaтон-

нo исслeдоBaть

фopмyлy'

сoдep)кaщylо

tlять пoсJreдHиx

скобoк.

.(aлeе

пo-

лyчеHиr

peзoЛьвеIlт

бьIстpо

пplIвo.цI4T к IlyсToМy llpe.цлo)кеrrl{ro

- фоpмyлa

ltевЬIIIoлнип{a.

(б)

Для

aнaJlизa oстaются

четЬIpe скoбки. Пpoцeос

Пoлyчеl{ия

prзoлЬBеI{т oцpаHичeн' и JIeгко

Bидеть'

нтo

(

)

пoЛyчитЬ

I{eДьзЯ

- фopмyлa

вьIпoл}IItN{a.

(в)'

(г)

Peц.Ieние

.цoстигaеTся

пoдхo.цoм, иcIIoлЬзoBaннЬIм в IIре.ц,ьlдy-

IциХ

пylrкTax.

16. Кpоме

JIиTеpЕшa,

кoтopьiй

присyTcтвyет в oднoй

дизъrон.кции

без

Itttвеpсии'

дpyгoй

с ItнBеpсией,

в oбеиx

.цизъIoнкЦиЯx

дoлжен

бьrть

oдин oбщий

ЛитеpzlJl.

Pозdел IV

Bьtчислитeль}taя

сJIoхGtoстЬ

aJIгopItTMa яBляеTся

фyнкциеii,

опIlсЬI-

вarощей

aсиМпToTическyIo зaBисиMoсть

чисJra эЛеI\,{еIIТapнЬIx IIIaгoB aJIгo-

pитмa

(пpи

нaиболеe

''нeблaгoпplt{тньIx''

исхoдгIьlx

дaнньtx)

oT IIaрaI\4еТрoB'

зa.цaЮщиx

paЗмеp зa.цaчи.

Слoх;ность

зa.цaчи

oцегtивaетоя

сЛox{нoстьк)''наиЛyЧЦlегo''

алгopитМa,

известнoгo

для

этой

3aдaчiI.

2. Зal{aчи

(б), (д),

(н)

зкопонеHIJИaJIIrIIЬIе]

ЗaдaЧи

(г)' (o)

y'{P.пoлньte;

зa,цaчи

("),

(и),

(л)

.n/P-тpy.ц}IЬIе;

oсTaJIьt{ЬIе

зaДaчи

prшIalотся

IIoлиI{oМи-

aЛЬ1lЬlМи

aЛ гоp}.1тМaMIl,

З,

B aлгoритме

Кpyскaля

испoJIЬЗyе,тся

пoшIaгoвoe

I1pисoединeние

строяще]\,lyо,{

.цеpеBy

peбеp,

ytlopя,цoЧeьIlrьI;t

пo

неубьrBaниIo

(альтepнaтивa

пo

нeвoзрaстaнию)

весoв;

pебpа'

пpиBo,цящие

в0зIIик}loBrItиIo

цикЛoв'

огIускaroTся.

О6a

aлгоpитМa

иМеIoТ

сЛojкнoсть

{IOpядкa

О(п

nl)'

5' ЖaДньIl"t

aлгopитМ

рaскpaски

пpи

дaннoй

}rуMерaцlrи

вrpIIIиI{

иc-

олЬзует

(lетЬIpе

цвеТa.

6. МoдифициpoванньrЙ

aJlгopитм

исIIoJIЬзуеT

тpи

цBетa

и тoчt{o

oIIpе-

.цел]tт

д{al{нoМ

оJlyчae

хpoМaтическoе

чI{сJI0.

Гpaф

являетcя

IrJIoскиМ.

fiля

l1oлнoгo

гpaфa о

,,r BeршIинaМИ

у@)

гдe

у@)

xpoМaТичe-

ск()е

Чl1оЛO'

ffл:я

ПерBогo

гp'aфa

y(и)

для

BтopoГo

уФ):2,Cлoжнoсть

алгo-

pитlаa- О(п).

9. Bтopой гpaф

из пpeдт,rдyщей

зaДaчII

яBЛяется

,цвyдoJIЬt{ЬIМ. .{пя

двy-

дoльltогo

rpaфa

всегдa сI]paBr.цЛиIrol-

у(п)

10' За.цaчa

2-BЬIГn

oтнoсlиTся

кЛaссy

пoдиIIoМиaJIьIlьD(,

зa,цaЧи

BЬIП

3-BЬiП

кJIaссy NP-пoлньr,к

зaдav'

tt.

(a)

Л(з,l

(Jl

уv

z)(-х2VrJ3

dGP

VХ4

q)(з{ vrх5

vх6)

(-J7

у'l

z)(хgV

Х9 V

-х19)(-y

V сr

Р)(-y'и

-сr

B)(-y

сt,

-p)

(-1,

-с{,

--B)(-z

v u v

p)(-zV

-С{,

B)(-zv

сx,

-B)(-z

-сr

-B

ЗДесь

(.)

.рoponyna

.ц.]1я

з&цaчи

3-BЬIП'

экBиBaлeнтнaя

иохoднoй

пo

крlrтеpиto

BьтIIoJltlиМосrTи.

12.

ПpеобрaзoBaTЬ

зa.цaI{Еьlй

гpaф B

I]oЛtlЬIй

гpaф

дo6aвлением

неoб-

хоДиI\{ьlx

lIЛя

TaкoГo

гrpеобpaзoвaния

pебеp.

Peбpaм Зa.цaннoгo

гpaфa

пpи-

тIиcaTь

вeс,

paвньrй

дoбaвленнЬIМ

рrбpaп,{

вес'

paвнЬIiа2.

[aлee

peшIaTь

зaДaliy

кollМ!{вoя)кrpa.

Если Зa,цaЧa

peЦIaeтся

Toчнo,

тo знaчeние

.цлиньI

обxодa,

paвI{ое

},,' oзIlaчaет

cyщrстBogallиr

гaМильтoIIоBa

циклa

B зa.цaннoМ

гpaфе

(и

чиc.цo веpuлtн).

l3. Униве1lсaпьHaя

МaшIинa

Тьropингa

(УMт)

имитt{pyrT

действия

.птoбrэй кolrкpетнoй

МaпIиttьI Tьtоpингa;

aBтoМaт УМТ''интеpпpe.гиpyет''