Вопросы к экзамену
Описание файла
PDF-файл из архива "Вопросы к экзамену", который расположен в категории "". Всё это находится в предмете "методы оптимизации" из 5 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст из PDF
Âîïðîñû ê ýêçàìåíó ïî ìåòîäàì îïòèìèçàöèè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 Áåçäîêàçàòåëüñòâà..
