Главная » Все файлы » Просмотр файлов из архивов » PDF-файлы » В.Б. Алексеев - Электронный коспект лекций

В.Б. Алексеев - Электронный коспект лекций, страница 15

PDF-файл В.Б. Алексеев - Электронный коспект лекций, страница 15 Сложность алгоритмов (53355): Лекции - 7 семестрВ.Б. Алексеев - Электронный коспект лекций: Сложность алгоритмов - PDF, страница 15 (53355) - СтудИзба2019-09-18СтудИзба

Описание файла

PDF-файл из архива "В.Б. Алексеев - Электронный коспект лекций", который расположен в категории "". Всё это находится в предмете "сложность алгоритмов" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр PDF-файла онлайн

Текст 15 страницы из PDF

pOSKOLXKU PO USLOWI@ PRI L@BOM WHODE MA[INA OSTANAWLIWAETSQ, TO ONA NE MOVET "ZACIKLITXSQ", TO ESTX KONFIGURACIQ NE MOVETPOWTORITXSQ. PO\TOMU WREMQ RABOTY PRI L@BOM WHODE NE PREWOSHODIT^ISLA RAZLI^NYH KONFIGURACIJ. pRI \TOMlog2(rp1(n) p1(n) k) = p1 (n) log2 r + log2 p1(n) + log2 k 6 p(n);GDE p(n)| NEKOTORYJ POLINOM. tEOREMA DOKAZANA.sLEDSTWIE. dLQ L@BOJ ZADA^I IZ PSPACE t(n) 6 2p(n) GDEp(n) NEKOT RYJ POLINOMoPREDELENIE. zADA^A RASPOZNAWANIQ (QZYK) L NAZYWAETSQPSPACE -POLNOJ, ESLI:1)L PSPACE ,2)K L POLINOMIALXNO SWODQTSQ WSE ZADA^I IZ PSPACE .uTWERVDENIE.

eSLI DLQ NEKOTOROJ PSPACE POLNOJ ZADVA^I SU]ESTWUET ALGORITM S POLINOMIALXNOJ SLOVNOSTX@ TO,|o.-PSPACE = P-,.zADA^A O KWANTIFICIROWANNYH BULEWSKIH FORMULAH (QBF).wHOD FORMULA WIDA:(Q1x1)(Q2x2) : : : (Qm xm)[F (x1; : : : ; xm )];GDE x1; : : : ; xm |BULEWSKIE PEREMENNYE, F |BULEWSKAQ FORMULA W BAZISEfKON_@NKCIQ,DIZ_@NKCIQ,OTRICANIEg, Q ; i 2 f9; 8g DLQ WSEH i.tREBUETSQ WYQSNITX, ISTINNA LI DANNAQ FORMULA.lEMMA.

QBF 2 PSPACE:.dOKAZATELXSTWO pUSTX NA WHOD POSTUPILA FORMULA(Q1x1)(Q2x2) : : : (Qm xm)[F (x1; : : : ; xm )];DLINY n. tOGDA DLINA FORMULY F (x1; : : : ; xm ) NE BOLEE n, I DLQ L@BOGOZADANNOGO NABORA (1; : : : ; m WY^ISLENIE F (1; : : : ; m ) MOVNO WYPOLNITX ZA WREMQ, A ZNA^IT I S ISPOLXZOWANIEM PAMQTI, NE BOLEE p1(n),GDE p1 |NEKOTORYJ POLINOM.

eSLI ZAFIKSIROWANY TOLXKO ZNA^ENIQ1; : : : ; k PEREMENNYH x1; : : : ; xk , TO MY POLU^AEM PODZADA^U: NAJTIISTINNOSTNOE ZNA^ENIE FORMULY(Qk+1xk+1) : : : (Qmxm )[F (1; : : : ; k )(xk+1; : : : ; xm )]:pRIMENIM DLQ RE[ENIQ ISHODNOJ ZADA^I (I WSEH EE PODZADA^) SLEDU@]IJ REKURSIWNYJ ALGORITM:1.wY^ISLITX (Q2x2) : : : (Qm xm)F (0; x2 ; : : : ; xm ) \TIM VE REKURSIWNYM ALGORITMOM. zAPOMNITX POLU^ENNOE ZNA^ENIE (1 BIT) W DOPOLNITELXNOJ Q^EJKE..752.wY^ISLITX NA TOJ VE ZONE \TIM VE ALGORITMOM(Q2x2) : : : (Qm xm )F (0; x2; : : : ; xm ).3.eSLI Q1 = 8 I OBA ZNA^ENIQ, WY^ISLENNYE W 1 I 2, RAWNY 1,TOWYDATX OTWET 1, INA^E WYDATX 0.eSLI Q1 = 9 I OBA ZNA^ENIQ W 1 I 2RAWNO 0, TO WYDATX 0, INA^E WYDATX 1.iZ OPISANIQ ALGORITMA WIDNO, ^TO DLQ RE[ENIQ ZADA^I KAVDOGO UROWNQ NUVNO NA 1 Q^EJKU BOLX[E, ^EM NA RE[ENIE L@BOJ EEPODZADA^I.

tAK KAK NA WY^ISLENIE F (1; : : : ; m ) TREBUETSQ PAMQTINE BOLEE p1 (n), TO DLQ WY^ISLENIQ ISTINNOSTNOGO ZNA^ENIQ ISHODNOJFORMULY TREBUETSQ PAMQTX NE BOLEE p1(n) + n Q^EEK. dLQ UPRAWLENIQPROCESSOM PEREHODA OT ODINH PODZADA^ K DRUGIM W OPISANNOM ALGORITMEDOSTATO^NO POMNITX, KAKAQ PODZADA^A RE[AETSQ W DANNYJ MOMENT, TOESTX POMNITX ZNA^ENIQ 1 ; : : : ; k , OPREDELQ@]IE \TU PODZADA^U. tAKIMOBRAZOM, W CELOM OPRISANNYJ ALGORITM TREBUET NE BOLEE p(n) Q^EEKPAMQTI, GDE p|NEKOTORYJ POLINOM.tEOREMA. zADA^A QBF QWLQETSQ PSPACE POLNOJdOKAZATELXSTWO nAM NADLO DOKAZATX, ^TO L@BAQ ZADA^A L IZPSPACE POLINOMIALXNO SWODITSQ K QBF . eSLI L 2 PSPACE , TOSU]ESTWUET MA[INA tX@RINGA M , KOTORAQ RE[AET ZADA^U L S PAMQTX@NE BOLEE p1 (n) I WREMENEM NE BOLEE p(n) (SM. LEMMU), GDE n|DLINA WHODA.pUSTX x|WHOD DLINY n DLQ ZADA^I L.

nAM NADO ZA POLINOMIALXNOEWREMQ POSTROITX KWANTIFICIROWANNU@ FORMULU F (x) TAK, ^TO F (x)ISTINNA TOGDA I TOLXKO TOGDA, KOGDA x 2 L. tOT FAKT, ^TO x 2 L,RAWNOSILEN UTWERVDENI@: DLQ WHODA x SU]ESTWUET PRINIMA@]EE (SOTWETOM "DA") WY^ISLENIE MA[INY M . |TO POSLEDNEE UTWERVDENIEMY I WYRAZIM W WIDE FORMULY F (x). tAK VE, KAK PRI DOKAZATELXSTWENP -POLNOTY ZADA^I wyp, WWEDEM DWA MNOVESTWA PEREMENNYH V I V 0,OPISYWA@]IH 2 PROIZWOLXNYE KONFIGURACII NA ZONE p1(n), I ZAPI[EMFORMULU F0(V; V 0) WYRAVA@]U@ TOT FAKT, ^TO V I V 0 PRAWILXNOZADA@T KONFIGURACII I LIBO V = V 0 , LIBO IZ KONFIGURACII V MYZA ODIN [AG MA[INY M PEREHODIM W KONFIGURACI@ V 0.

kAK POKAZANO PRI DOKAZATELXSTWE NP -POLNOTY ZADA^I wyp DLINA FORMULYF0(V; V 0) MOVET BYTX OGRANI^ENA NEKOTORYM POLINOMOM p2(n) I EEMOVNO POSTROITX ZA POLINOMIALXNOE OT n WREMQ. fORMULA F0(V; V 0 )WYRAVAET TOT FAKT, ^TO IZ KONFIGURACII V W KONFIGURACI@ V 0 MOVNOPEREJTI ZA NE BOLEE ^EM 1 [AG. pOSTROIM TEPERX INDUKTIWNO FORMULYF1; F2; : : : ; Fs , GDE s = p(n), SLEDU@]IM OBRAZOM. pUSTX W |E]E ODNOMNOVESTWO PEREMENNYH, OPISYWA@]IH KONFIGURACI@ NA ZONE p1(n).|.76.tOGDA POLOVIMFk (V; V 0) = 9W [Fk;1(V; W )&Fk;1(W; V 0 )]:fORMULA Fk WYRAVAET TOT FAKT, ^TO V; V 0|PRAWILXNYE KONFIGURACIII IZ V W V 0 MOVNO PEREJTI ZA NE BOLEE, ^EM 2k [AGOW.

fORMULA WKWADRATNYH SKOBKAH RAWNOSILXNA SLEDU@]EJ FORMULE:(8Y )(8Z )[(Y = V )&(Z = W ) _ (Y = W )&(Z = V 0 ) ! Fk;1(Y; Z )]GDE Y; Z |DWA MNOVESTWA PEREMENNYH, OPISYWA@]IH 2 PROIZWOLXNYEKONFIGURACII. pO\TOMU FORMULU Fk MOVNO ZAPISATX W WIDE:Fk (V; V 0 ) = (9W )(8Y )(8Z )[(Y = V )&(Z = W )_(Y = W )&(Z = V 0 ) ! Fk;1(Y; Z )]:tAKIM OBRAZOM, DLINA Fk(V; V 0) OTLI^AETSQ OT DLINY Fk;1(V; V 0 ) NEBOLEE ^EM NA NEKOTORYJ POLINOM p3(n) I DLINA Fk (V; V 0) NE PREWOSHODITp2(n) + kp3 (n).

pUSTX WREMQ RABOTY MA[INY M NE PREWOSHODIT 2p(n) Is + p(n). tOGDA Fs(V; V 0) IMEET DLINU NE BOLEE p2(n)+ p(n) p3(n) = p4(n),GDE p4| POLINOM, I WYRAVAET TOT FAKT, ^TO V I V 0 PRAWILXNYE KONFIGURACII I IZ V W V 0 MOVNO PEREJTI ZA NE BOLEE 2p(n) [AGOW MA[INYM . pUSTX FORMULA Gx(V ) WYRAVAET TOT FAKT, ^TO KONFIGURACIQ VQWLQETSQ PRAWILXNOJ NA^ALXNOJ KONFIGURACIEJ DLQ WHODA x (yf pjytp1(n)), A FORMULA H (V ) WYRAVAET TOT FAKT, ^TO W KONFIGURACII VSOSTOQNIE "DA". tOGDA TOT FAKT, ^TO DLQ WHODA x SU]ESTWUET PRINIMA@]EE WY^ISLENIE MA[INY M MOVNO PREDSTAWITX FORMULOJF (x) = (9V )(9V 0)[Gx(V )&H (V 0)&Fs(V; V 0 )]:pOSKOLXKU DLINA FORMUL Gx(V ) I H (V ) MOVET BYTX OGRANI^ENAPOLINOMOM OT n I ONI MOGUT BYTX POSTROENY ZA POLINOMIALXNOE OT nWREMQ (SM.

DOKAZATELXSTWO NP -POLNOTY ZADA^I wyp), TO POLU^AEM,^TO DLINA F (x) NE PREWOSHODIT POLINOMA OT n I F (x) MOVET BYTXPOSTROENA ZA POLINOMIALXNOE OT n WREMQ. tEOREMA DOKAZANA.pRI OPREDELENII KLASSA DLOG OBY^NO ISPOLXZU@T MODELX MNOGOLENTO^NOJ MA[INY tX@RINGA. pUSTX U MA[INY tX@RINGA IMEETSQNESKOLXKO LENT, ODNA IZ KOTORYH WYDELENA KAK WHODNAQ, I NA KAVDOJLENTE IMEETSQ ODNA GOLOWKA. oDIN [AG RABOTY TAKOJ MA[INY SOSTOITW ODNOWREMENNOM WYPOLNENII OBY^NYH DEJSTWIJ KAVDOJ GOLOWKOJ (UKAVDOJ GOLOWKI SWOI DEJSTWIQ), PRI^EM WESX NABOR DEJSTWIJ ODNOZNA^NO OPREDELQETSQ TEMI SIMWOLAMI, KOTORYE OBOZREWA@TSQ WSEMI GOLOWKAMI I SOSTOQNIEM MA[INY. wHODNOE SLOWO ZAPISYWAETSQ NA WHODNOJLENTE W STANDARTNOJ KONFIGURACII I GOLOWKA NA WHODNOJ LENTE MOVETTOLXKO ^ITATX SIMWOLY, NO NE MOVET ZAPISYWATX NOWYE.77oPREDELENIE. kLASS DLOG OPREDELQETSQ KAK KLASS WSEH ZADA^RASPOZNAWANIQ (QZYKOW), DLQ KOTORYH SU]ESTWUET RASPOZNA@]AQ IHMNOGOLENTO^NAQ MA[INA tX@RINGA, ISPOLXZU@]AQ NA WSEH LENTAH, KROME WHODNOJ, NE BOLEE c log2 n Q^EEK, GDE n |DLINA WHODA I c|NEKOTORAQKONSTANTA (DLQ DANNOJ ZADA^I).iSPOLXZUQ LEMMU, NETRUDNO POKAZATX, ^TO DLOG P .

tAKIMOBRAZOMDLOG P NP PSPACE:mOVNO DOKAZATX, ^TO DLOG =6 PSPACE , PO\TOMU HOTQ BY ODNO IZUKAZANNYH WKL@^ENIJ DOLVNO BYTX STROGIM. oDNAKO KAKOE (ILI KAKIE)IMENNO, POKA (2001 GOD) NE IZWESTNO.78.

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5075
Авторов
на СтудИзбе
455
Средний доход
с одного платного файла
Обучение Подробнее