Äëÿ äîñòóïà ê äàííîé êíèãå íåîáõîäèìà àâòîðèçàöèÿ

Ëîãèí: ïàðîëü Çàïðîñ äîñòóïà

Ïîñòðîåíèå è àíàëèç âû÷èñëèòåëüíûõ àëãîðèòìîâ

  

Àõî À. Ïîñòðîåíèå è àíàëèç âû÷èñëèòåëüíûõ àëãîðèòìîâ. Èçä-âî "Ìèð", Ì., 1979 ã.

 ìîíîãðàôèè ñ åäèíûõ ïîçèöèé èçëàãàþòñÿ ðåçóëüòàòû òåîðåòè÷åñêèõ è ïðèêëàäíûõ èññëåäîâàíèé ïî ïîñòðîåíèþ áûñòðûõ àëãîðèòìîâ è äîêàçàòåëüñòâó èõ îòñóòñòâèÿ. Ðàññìîòðåíû çàäà÷è ïåðåáîðà, óïîðÿäî÷åíèÿ ìàññèâîâ äàííûõ, óìíîæåíèÿ ÷èñåë, óìíîæåíèÿ ìàòðèö; îáñóæäàþòñÿ àëãîðèòìû íà ãðàôàõ. Ìíîãèå ðåçóëüòàòû ðàíåå áûëè ðàññåÿíû â òðóäíîäîñòóïíûõ èñòî÷íèêàõ è â ìîíîãðàôè÷åñêîì âèäå ïóáëèêóþòñÿ âïåðâûå.

Êíèãà ðàññ÷èòàíà íà ñïåöèàëèñòîâ ïî ñîâðåìåííîìó ïðîãðàììèðîâàíèþ, ðàçðàáîò÷èêîâ âû÷èñëèòåëüíûõ ñèñòåì è àëãîðèòìîâ; îíà ìîæåò áûòü èñïîëüçîâàíà êàê ó÷åáíîå ïîñîáèå ñòóäåíòàìè è àñïèðàíòàìè, ñïåöèàëèçèðóþùèìèñÿ â îáëàñòè âû÷èñëèòåëüíîé ìàòåìàòèêè.


Îãëàâëåíèå

ÏÐÅÄÈÑËÎÂÈÅ
ÌÎÄÅËÈ ÂÛ×ÈÑËÅÍÈÉ
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. ÏÐÅÄÂÀÐÈÒÅËÜÍÀß ÎÁÐÀÁÎÒÊÀ