Ïîñòðîåíèå è àíàëèç âû÷èñëèòåëüíûõ àëãîðèòìîâ
ÎãëàâëåíèåÏÐÅÄÈÑËÎÂÈÅÌÎÄÅËÈ ÂÛ×ÈÑËÅÍÈÉ 1.1. ÀËÃÎÐÈÒÌÛ È ÈÕ ÑËÎÆÍÎÑÒÈ 1.2. ÌÀØÈÍÛ Ñ ÏÐÎÈÇÂÎËÜÍÛÌ ÄÎÑÒÓÏÎÌ Ê ÏÀÌßÒÈ 1.3. ÂÛ×ÈÑËÈÒÅËÜÍÀß ÑËÎÆÍÎÑÒÜ ÐÀÌ-ÏÐÎÃÐÀÌÌ 1.4. ÌÎÄÅËÜ Ñ ÕÐÀÍÈÌÎÉ ÏÐÎÃÐÀÌÌÎÉ 1.5. ÌÎÄÈÔÈÊÀÖÈß ÐÀÌ 1.6. ÏÐÎÑÒÅÉØÀß ÌÎÄÅËÜ ÂÛ×ÈÑËÅÍÈÉ: ÌÀØÈÍÀ ÒÜÞÐÈÍÃÀ 1.7. ÑÂßÇÜ ÌÀØÈÍ ÒÜÞÐÈÍÃÀ È ÐÀÌ 1.8. ßÇÛÊ ÂÛÑÎÊÎÃÎ ÓÐÎÂÍß — ÓÏÐÎÙÅÍÍÛÉ ÀËÃÎË 2. ÐÀÇÐÀÁÎÒÊÀ ÝÔÔÅÊÒÈÂÍÛÕ ÀËÃÎÐÈÒÌΠ2.1. ÑÒÐÓÊÒÓÐÛ ÄÀÍÍÛÕ: ÑÏÈÑÊÈ, Î×ÅÐÅÄÈ È ÑÒÅÊÈ 2.2. ÏÐÅÄÑÒÀÂËÅÍÈß ÌÍÎÆÅÑÒ 2.3. ÃÐÀÔÛ 2.4. ÄÅÐÅÂÜß 2.5. ÐÅÊÓÐÑÈß 2.6. ÐÀÇÄÅËßÉ È ÂËÀÑÒÂÓÉ 2.7. ÁÀËÀÍÑÈÐÎÂÊÀ 2.8. ÄÈÍÀÌÈ×ÅÑÊÎÅ ÏÐÎÃÐÀÌÌÈÐÎÂÀÍÈÅ 2.9. ÝÏÈËÎà 3. ÑÎÐÒÈÐÎÂÊÀ È ÏÎÐßÄÊÎÂÛÅ ÑÒÀÒÈÑÒÈÊÈ 3.1. ÇÀÄÀ×À ÑÎÐÒÈÐÎÂÊÈ 3.2. ÖÈÔÐÎÂÀß ÑÎÐÒÈÐÎÂÊÀ 3.3. ÑÎÐÒÈÐÎÂÊÀ Ñ ÏÎÌÎÙÜÞ ÑÐÀÂÍÅÍÈÉ 3.4. ÑÎÐÒÄÅÐÅÂÎÌ — ÓÏÎÐßÄÎ×ÅÍÈÅ Ñ ÏÎÌÎÙÜÞ O(n log n) ÑÐÀÂÍÅÍÈÉ 3.5. ÁÛÑÒÐÑÎÐÒ — ÓÏÎÐßÄÎ×ÅÍÈÅ ÇÀ ÑÐÅÄÍÅÅ ÂÐÅÌß O(n log n) 3.6. ÏÎÐßÄÊÎÂÛÅ ÑÒÀÒÈÑÒÈÊÈ 3.7. ÑÐÅÄÍÅÅ ÂÐÅÌß ÄËß ÏÎÐßÄÊÎÂÛÕ ÑÒÀÒÈÑÒÈÊ 4. ÑÒÐÓÊÒÓÐÛ ÄÀÍÍÛÕ ÄËß ÇÀÄÀ×, ÊÀÑÀÞÙÈÕÑß ÐÀÁÎÒÛ Ñ ÌÍÎÆÅÑÒÂÀÌÈ 4.2. ÌÅÒÎÄ ÐÀÑÑÒÀÍÎÂÊÈ 4.3. ÄÂÎÈ×ÍÛÉ ÏÎÈÑÊ 4.4. ÄÅÐÅÂÜß ÄÂÎÈ×ÍÎÃÎ ÏÎÈÑÊÀ 4.5. ÎÏÒÈÌÀËÜÍÛÅ ÄÅÐÅÂÜß ÄÂÎÈ×ÍÎÃÎ ÏÎÈÑÊÀ 4.6. ÏÐÎÑÒÎÉ ÀËÃÎÐÈÒÌ ÄËß ÍÀÕÎÆÄÅÍÈß ÎÁÚÅÄÈÍÅÍÈß ÍÅÏÅÐÅÑÅÊÀÞÙÈÕÑß ÌÍÎÆÅÑÒ 4.7. ÄÐÅÂÎÂÈÄÍÛÅ ÑÒÐÓÊÒÓÐÛ ÄËß ÇÀÄÀ×È ÎÁÚÅÄÈÍÈÒÜ — ÍÀÉÒÈ 4.8. ÏÐÈËÎÆÅÍÈß È ÎÁÎÁÙÅÍÈß ÀËÃÎÐÈÒÌÀ ÎÁÚÅÄÈÍÈÒÜ — ÍÀÉÒÈ 4.9. ÑÕÅÌÛ ÑÁÀËÀÍÑÈÐÎÂÀÍÍÛÕ ÄÅÐÅÂÜÅ 4.10. ÑËÎÂÀÐÈ È Î×ÅÐÅÄÈ Ñ ÏÐÈÎÐÈÒÅÒÀÌÈ 4.11. ÑËÈÂÀÅÌÛÅ ÄÅÐÅÂÜß 4.12. ÑÖÅÏËßÅÌÛÅ Î×ÅÐÅÄÈ 4.13. ÐÀÇÁÈÅÍÈÅ 4.14. ÐÅÇÞÌÅ 5. ÀËÃÎÐÈÒÌÛ ÍÀ ÃÐÀÔÀÕ 5.1. ÎÑÒÎÂÍÎÅ ÄÅÐÅÂÎ ÍÀÈÌÅÍÜØÅÉ ÑÒÎÈÌÎÑÒÈ 5.2. ÌÅÒÎÄ ÏÎÈÑÊÀ  ÃËÓÁÈÍÓ 5.3. ÄÂÓÑÂßÇÍÎÑÒÜ 5.4. ÏÎÈÑÊ Â ÃËÓÁÈÍÓ Â ÎÐÈÅÍÒÈÐÎÂÀÍÍÎÌ ÃÐÀÔÅ 5.5. ÑÈËÜÍÀß ÑÂßÇÍÎÑÒÜ 5.6. ÇÀÄÀ×È ÍÀÕÎÆÄÅÍÈß ÏÓÒÅÉ 5.7. ÀËÃÎÐÈÒÌ ÒÐÀÍÇÈÒÈÂÍÎÃÎ ÇÀÌÛÊÀÍÈß 5.8. ÀËÃÎÐÈÒÌ ÍÀÕÎÆÄÅÍÈß ÊÐÀÒ×ÀÉØÅÃÎ ÏÓÒÈ 5.9. ÇÀÄÀ×È Î ÏÓÒßÕ È ÓÌÍÎÆÅÍÈÅ ÌÀÒÐÈÖ 5.10. ÇÀÄÀ×È Ñ ÎÄÍÈÌ ÈÑÒÎ×ÍÈÊÎÌ 5.11. ÄÎÌÈÍÀÒÎÐÛ Â ÎÐÈÅÍÒÈÐÎÂÀÍÍÛÕ ÀÖÈÊËÈ×ÅÑÊÈÕ ÃÐÀÔÀÕ: ÊÎÌÁÈÍÈÐÎÂÀÍÈÅ ÏÎÍßÒÈÉ 6. ÓÌÍÎÆÅÍÈÅ ÌÀÒÐÈÖ È ÑÂßÇÀÍÍÛÅ Ñ ÍÈÌ ÎÏÅÐÀÖÈÈ 6.2. ÀËÃÎÐÈÒÌ ØÒÐÀÑÑÅÍÀ ÄËß ÓÌÍÎÆÅÍÈß ÌÀÒÐÈÖ 6.3. ÎÁÐÀÙÅÍÈÅ ÌÀÒÐÈÖ 6.4. ÍÂÏ-ÐÀÇËÎÆÅÍÈÅ ÌÀÒÐÈÖÛ 6.5. ÏÐÈËÎÆÅÍÈß ÍÂÏ-ÐÀÇËÎÆÅÍÈß 6.6. ÓÌÍÎÆÅÍÈÅ ÁÓËÅÂÛÕ ÌÀÒÐÈÖ 7. ÁÛÑÒÐÎÅ ÏÐÅÎÁÐÀÇÎÂÀÍÈÅ ÔÓÐÜÅ È ÅÃÎ ÏÐÈËÎÆÅÍÈß 7.2. ÀËÃÎÐÈÒÌ ÁÛÑÒÐÎÃÎ ÏÐÅÎÁÐÀÇÎÂÀÍÈß ÔÓÐÜÅ 7.3. ÁÏÔ ÏÐÈ ÈÑÏÎËÜÇÎÂÀÍÈÈ ÁÈÒÎÂÛÕ ÎÏÅÐÀÖÈÉ 7.4. ÏÐÎÈÇÂÅÄÅÍÈÅ ÏÎËÈÍÎÌΠ7.5. ÀËÃÎÐÈÒÌ ØÅÍÕÀÃÅ — ØÒÐÀÑÑÅÍÀ ÄËß ÓÌÍÎÆÅÍÈß ÖÅËÛÕ ×ÈÑÅË 8. ÀÐÈÔÌÅÒÈ×ÅÑÊÈÅ ÎÏÅÐÀÖÈÈ ÍÀÄ ÖÅËÛÌÈ ×ÈÑËÀÌÈ È ÏÎËÈÍÎÌÀÌÈ 8.1. ÀÍÀËÎÃÈÈ ÌÅÆÄÓ ÖÅËÛÌÈ ×ÈÑËÀÌÈ È ÏÎËÈÍÎÌÀÌÈ 8.2. ÓÌÍÎÆÅÍÈÅ È ÄÅËÅÍÈÅ ÖÅËÛÕ ×ÈÑÅË 8.3. ÓÌÍÎÆÅÍÈÅ È ÄÅËÅÍÈÅ ÏÎËÈÍÎÌΠ8.4. ÌÎÄÓËÜÍÀß ÀÐÈÔÌÅÒÈÊÀ 8.5. ÌÎÄÓËÜÍÀß ÀÐÈÔÌÅÒÈÊÀ ÏÎËÈÍÎÌÎÂ È ÂÛ×ÈÑËÅÍÈÅ ÈÕ ÇÍÀ×ÅÍÈÉ 8.6. ÏÐÈÌÅÍÅÍÈÅ ÊÈÒÀÉÑÊÎÉ ÒÅÎÐÅÌÛ ÎÁ ÎÑÒÀÒÊÀÕ 8.7. ÊÈÒÀÉÑÊÀß ÒÅÎÐÅÌÀ ÎÁ ÎÑÒÀÒÊÀÕ È ÈÍÒÅÐÏÎËßÖÈß ÏÎËÈÍÎÌΠ8.8. ÍÀÈÁÎËÜØÈÅ ÎÁÙÈÅ ÄÅËÈÒÅËÈ È ÀËÃÎÐÈÒÌ ÅÂÊËÈÄÀ 8.9. ÀÑÈÌÏÒÎÒÈ×ÅÑÊÈ ÁÛÑÒÐÛÉ ÀËÃÎÐÈÒÌ ÍÀÕÎÆÄÅÍÈß ÍÎÄ ÏÎËÈÍÎÌΠ8.10. ÍÎÄ ÖÅËÛÕ ×ÈÑÅË 8.11. ÅÙÅ ÐÀÇ Î ÏÐÈÌÅÍÅÍÈÈ ÊÈÒÀÉÑÊÎÉ ÒÅÎÐÅÌÛ ÎÁ ÎÑÒÀÒÊÀÕ 8.12. ÐÀÇÐÅÆÅÍÍÛÅ ÏÎËÈÍÎÌÛ 9. ÀËÃÎÐÈÒÌÛ ÈÄÅÍÒÈÔÈÊÀÖÈÈ 9.1. ÊÎÍÅ×ÍÛÅ ÀÂÒÎÌÀÒÛ È ÐÅÃÓËßÐÍÛÅ ÂÛÐÀÆÅÍÈß 9.2. ÐÀÑÏÎÇÍÀÂÀÍÈÅ ÎÁÐÀÇÎÂ, ÇÀÄÀÂÀÅÌÛÕ ÐÅÃÓËßÐÍÛÌÈ ÂÛÐÀÆÅÍÈßÌÈ 9.3. ÐÀÑÏÎÇÍÀÂÀÍÈÅ ÏÎÄÖÅÏÎ×ÅÊ 9.4. ÄÂÓÑÒÎÐÎÍÍÈÉ ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÉ ÌÀÃÀÇÈÍÍÛÉ ÀÂÒÎÌÀÒ 9.5. ÏÎÇÈÖÈÎÍÍÛÅ ÄÅÐÅÂÜß È ÈÄÅÍÒÈÔÈÊÀÒÎÐÛ ÏÎÇÈÖÈÉ 10. NP-ÏÎËÍÛÅ ÇÀÄÀ×È 10.1. ÍÅÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÅ ÌÀØÈÍÛ ÒÜÞÐÈÍÃÀ 10.2. ÊËÀÑÑÛ ... 10.3. ßÇÛÊÈ È ÇÀÄÀ×È 10.4. NP-ÏÎËÍÎÒÀ ÇÀÄÀ×È ÂÛÏÎËÍÈÌÎÑÒÈ 10.5. ÅÙÅ ÍÅÑÊÎËÜÊÎ NP-ÏÎËÍÛÕ ÇÀÄÀ× 10.6. ÇÀÄÀ×È Ñ ÏÎËÈÍÎÌÈÀËÜÍÎ ÎÃÐÀÍÈ×ÅÍÍÎÉ ÏÀÌßÒÜÞ 11. ÍÅÊÎÒÎÐÛÅ ÄÎÊÀÇÓÅÌÎ ÒÐÓÄÍÎ ÐÀÇÐÅØÈÌÛÅ ÇÀÄÀ×È 11.2. ÈÅÐÀÐÕÈß ÏÎ ÅÌÊÎÑÒÍÎÉ ÑËÎÆÍÎÑÒÈ ÄËß ÄÅÒÅÐÌÈÍÈÐÎÂÀÍÍÛÕ ÌÀØÈÍ ÒÜÞÐÈÍÃÀ 11.3. ÇÀÄÀ×À, ÒÐÅÁÓÞÙÀß ÝÊÑÏÎÍÅÍÖÈÀËÜÍÛÕ ÂÐÅÌÅÍÈ È ÏÀÌßÒÈ 11.4. ÍÅÝËÅÌÅÍÒÀÐÍÀß ÇÀÄÀ×À 12. ÍÈÆÍÈÅ ÎÖÅÍÊÈ ×ÈÑËÀ ÀÐÈÔÌÅÒÈ×ÅÑÊÈÕ ÎÏÅÐÀÖÈÉ 12.2. ÅÙÅ ÐÀÇ Î ÍÅÂÅÒÂßÙÈÕÑß ÏÐÎÃÐÀÌÌÀÕ 12.3. ÌÀÒÐÈ×ÍÀß ÔÎÐÌÓËÈÐÎÂÊÀ ÇÀÄÀ× 12.4. ÍÈÆÍßß ÃÐÀÍÈÖÀ ÄËß ×ÈÑËÀ ÓÌÍÎÆÅÍÈÉ, ÑÂßÇÀÍÍÀß Ñ ÐÀÍÃÎÌ ÏÎ ÑÒÐÎÊÀÌ 12.5. ÍÈÆÍßß ÃÐÀÍÈÖÀ ÄËß ×ÈÑËÀ ÓÌÍÎÆÅÍÈÉ, ÑÂßÇÀÍÍÀß Ñ ÐÀÍÃÎÌ ÏÎ ÑÒÎËÁÖÀÌ 12.6. ÃÐÀÍÈÖÀ ÄËß ×ÈÑËÀ ÓÌÍÎÆÅÍÈÉ, ÑÂßÇÀÍÍÀß Ñ ÐÀÑÑÌÎÒÐÅÍÈÅÌ ÑÒÐÎÊ È ÑÒÎËÁÖΠ12.7. ÏÐÅÄÂÀÐÈÒÅËÜÍÀß ÎÁÐÀÁÎÒÊÀ |