Вопросы к экзамену (1125545)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

Âîïðîñû ê ýêçàìåíó ïî ìåòîäàì îïòèìèçàöèèIII êóðñ, 5 ñåìåñòð, 3 ïîòîêÂâåäåíèå â òåîðèþ ñëîæíîñòè1. (1.1) Îïðåäåëåíèÿ: èíäèâèäóàëüíîé è ìàññîâîé çàäà÷è, êîäèðîâêè çàäà÷è,àëãîðèòìà ðåøåíèÿ ìàññîâîé çàäà÷è, âðåìåííîé ñëîæíîñòè àëãîðèòìà.2. (2.1) Çàäà÷è ðàñïîçíàâàíèÿ ñâîéñòâ. Êëàññû P è NP. (17.2) Ïîíÿòèå âðåìåííîé ñëîæíîñòè àëãîðèòìîâ. (18.2) Ïîíÿòèå íåäåòåðìèíèðîâàííî ïîëèíîìèàëüíûõ çàäà÷.3. (3.1) Òåîðåìà îá ýêñïîíåíöèàëüíîé âðåìåííîé îöåíêå äëÿ çàäà÷ èç êëàññàNP.4. (4.1) Îïðåäåëåíèå ïîëèíîìèàëüíîé ñâîäèìîñòè.

Êëàññ NPC. Òåîðåìà Êóêà1 .5. (5.1) Êðèòåðèé NP-ïîëíîòû. Äîêàçàòåëüñòâî NP-ïîëíîòû çàäà÷è ÖËÍ.6. (6.1) Äîêàçàòåëüñòâî NP-ïîëíîòû çàäà÷è 3-âûïîëíèìîñòü. NP-òðóäíûå çàäà÷è.7. (7.1) Êëàññ co-NP. Ïðèìåð çàäà÷è, äîïóñêàþùåé õîðîøóþ õàðàêòåðèçàöèþ.Äîêàçàòåëüñòâî óòâåðæäåíèÿ î âçàèìîîòíîøåíèè êëàññîâ NPC è co-NP.8. (8.1) Âçàèìîîòíîøåíèå êëàññîâ P, NP è NPC, NP è co-NP. Êëàññ PSPACE.9. (9.1) Ïñåâäîïîëèíîìèàëüíûå àëãîðèòìû. Ïðèìåð äëÿ çàäà÷è î ðþêçàêå.10. (10.1) Ñèëüíàÿ NP-ïîëíîòà.

Òåîðåìà î ñâÿçè ñèëüíîé NP-ïîëíîòû çàäà÷è ññóùåñòâîâàíèåì ïñåâäîïîëèíîìèàëüíîãî àëãîðèòìà åå ðåøåíèÿ.11. (11.1) Îïðåäåëåíèå êîìáèíàòîðíîé çàäà÷è îïòèìèçàöèè è ïðèáëèæåííîãîàëãîðèòìà åå ðåøåíèÿ. Óòâåðæäåíèå î ðàçíèöå ìåæäó ïðèáëèæåííûì è òî÷íûì îïòèìóìîì äëÿ çàäà÷è î ðþêçàêå.12. (12.1) Îïðåäåëåíèåε-ïðèáëèæåííîãî àëãîðèòìà è ïîëíîñòüþ ïîëèíîìèàëü-íîé ïðèáëèæåííîé ñõåìû (ÏÏÏÑ). Ñâÿçü ìåæäó ñóùåñòâîâàíèåì ÏÏÏÑ èïñåâäîïîëèíîìèàëüíîñòüþ.13. (13.1) Òåîðåìà îá îòñóòñòâèè ÏÏÏÑ äëÿ çàäà÷ îïòèìèçàöèè, ñîîòâåòñòâóþùèõ ñèëüíî NP-ïîëíûì çàäà÷àì îïòèìèçàöèè.Îñíîâû ëèíåéíîãî ïðîãðàììèðîâàíèÿ1.

(14.1) Îïðåäåëåíèå îçËÏ. Ïðèöíèï ãðàíè÷íûõ ïðèáëèæåíèé. Àëãåðáàè÷åñêàÿ è áèòîâàÿ ñëîæíîñòü ËÏ. Ðåçóëüòàòû î ñëîæíîñòè äëÿ çàäà÷, áëèçêèõê ËÏ.2. (4.2, 13.2) Ãåîìåòðè÷åñêîå îïèñàíèå ñèìïëåêñ-ìåòîäà.3. (15.1) Òåîðåìà î ãðàíèöàõ ðåøåíèé çàäà÷ ËÏ ñ öåëûìè êîýôôèöèåíòàìè.4. (16.1) Òåîðåìà î ìåðå íåñîâìåñòíîñòè ñèñòåì ëèíåéíûõ íåðàâåíñòâ ñ öåëûìèêîýôôèöèåíòàìè.5.

(8.2, 21.2) Ïîëèíîìèàëüíûé àëãîðèòì îêðóãëåíèÿε1 -ïðèáëèæåííîãîðåøå-íèÿ ñèñòåìû ëèíåéíûõ óðàâíåíèé.6. (9.2, 23.2) Èäåÿ è îïèñàíèå ìåòîäà ýëëèïñîèäîâ.7. (24.2) Îöåíêà ñëîæíîñòè ìåòîäà ýëëèïñîèäîâ ïîèñêàøåíèÿ îçËÏ.ε2 -ïðèáëèæåííîãîðå-8. (17.1) Ñëåäñòâèÿ ñèñòåì ëèíåéíûõ íåðàâåíñòâ. Àôèííàÿ ëåììà Ôàðêàøà1 .9. (18.1) Ëåììà Ôàðêàøà î íåðàçðåøèìîñòè.10. (19.1) Òåîðåìà äâîéñòâåííîñòè ËÏ.11. (20.1) Ñâåäåíèå îçËÏ ê îäíîðîäíîé ñèñòåìå óðàâíåíèé ñ îãðàíè÷åíèåì ïîëîæèòåëüíîñòè.12. (22.2) Èäåÿ ìåòîäà Êàðìàðêàðà.Ýëåìåíòû ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ1. (21.1) Êëàññèôèêàöèÿ çàäà÷ ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ.

Ïðåèìóùåñòâà âûïóêëîãî ñëó÷àÿ.2. (1.2, 6.2) Ôîðìóëà ãðàäèåíòíîãî ìåòîäà â çàäà÷å áåçóñëîâíîé îïòèìèçàöèè.3. (2.2, 7.2, 11.2) Ôîðìóëà ìåòîäà Íüþòîíà â çàäà÷å áåçóñëîâíîé îïòèìèçàöèè.4. (3.2, 10.2) Èäåÿ ìåòîäà øòðàôà.5. (22.1) Íåîáõîäèìûå óñëîâèÿ ëîêàëüíîãî ìèíèìóìà ïðè îãðàíè÷åíèÿõíåðàâåíñòâàõ äëÿ äèôôåðåíöèðóåìûõ ôóíêöèé.6. (23.1) Ïîíÿòèå î ðåãóëÿðíîñòè îãðàíè÷åíèé-íåðàâåíñòâ â çàäà÷å ìàòåìàòè÷åñêîãî ïðîãðàììèðîâàíèÿ.Ñïîñîáû ðåøåíèÿ ïåðåáîðíûõ çàäà÷1.

(5.2) Ìåòîäû ãëîáàëüíîé ìèíèìèçàöèè.2. (16.2) Ìåòîä âåòâåé è ãðàíèö äëÿ ãëîáàëüíîé ìèíèìèçàöèè ëèïøèöèåâûõôóíêöèé.3. (24.1) Òåîðåìà î öåëî÷èñëåííîñòè ðåøåíèÿ çàäà÷è ËÏ ñ öåëûìè êîýôôèöèåíòàìè äëÿ âïîëíå óíèìîäóëÿðíûõ ìàòðèö îãðàíè÷åíèé.4. (15.2) Ìåòîä âåòâåé è ãðàíèö äëÿ ÖËÏ. Ðàçëè÷íûå ñòðàòåãèè ìåòîäà.5. (14.2) Èäåÿ ìåòîäà âåòâåé è ãðàíèö.

Ïðèìåð äëÿ çàäà÷è ÁËÏ.6. (12.2) Òåîðåìà îïòèìàëüíîñòè äëÿ ðàçëîæèìûõ ôóíêöèé.7. (20.2) Ïðèìåíåíèå ìåòîäîâ äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ äëÿ ïîíèæåíèÿ ðàçìåðíîñòè ðàçëîæèìîé îïòèìèçàöèîííîé çàäà÷è.8. (19.2) Ìåòîä äèíàìè÷åñêîãî ïðîãðàììèðîâàíèÿ äëÿ ÁËÏ ñ íåîòðèöàòåëüíûìè êîýôôèöèåíòàìè.1 Áåçäîêàçàòåëüñòâà..

Характеристики

Тип файла PDF

PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.

Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.

Список файлов вопросов/заданий