Id\u0105c na fali wyk\u0142adu o problemach nieobliczalnych (kt\u00f3ry ju\u017c si\u0119 odby\u0142; zob. poprzedni wpis), chcia\u0142bym podzieli\u0107 si\u0119 z Pa\u0144stwem kilkoma jeszcze spostrze\u017ceniami odno\u015bnie zwi\u0105zku mi\u0119dzy z\u0142o\u017cono\u015bci\u0105, nieobliczalno\u015bci\u0105 i nieprzewidywalno\u015bci\u0105.
\nPodzieli\u0107 si\u0119 m.in. po to, by wybrzmia\u0142a wyra\u017aniej konkluzja wyk\u0142adu.<\/p>\n
1) Ot\u00f3\u017c, po pierwsze, z\u0142o\u017cono\u015b\u0107 w sensie najbardziej dos\u0142ownym dotyczy struktury algorytm\u00f3w<\/strong>. Patrz\u0105c na z\u0142o\u017cono\u015b\u0107 z perspektywy tego\u017c sensu, musimy u\u015bwiadomi\u0107 sobie, \u017ce wsp\u00f3\u0142czesne programy komputerowe (czyli implementacje algorytm\u00f3w) maj\u0105 niezwykle skomplikowany kod, kt\u00f3ry s\u0142u\u017cy nie rozwi\u0105zywaniu jakiego\u015b pojedynczego problemu (np. sortowania), lecz gigantycznej liczby spl\u0105tanych ze sob\u0105 problem\u00f3w, kt\u00f3re sk\u0142adaj\u0105 si\u0119 na realizowane przez program zadanie (np. obs\u0142uga terminali lotniskowych). Programy takie tworz\u0105 nadto ca\u0142e zespo\u0142y programist\u00f3w (niekoniecznie zorientowanych w tym, co robi kolega i niekoniecznie \u201eogarniaj\u0105cych\u201d ca\u0142o\u015b\u0107 algorytmu). Dochodz\u0105 do tego nieustanne poprawki kodu, czynione cz\u0119sto ad hoc, w odpowiedzi na jakie\u015b wychwytywane wyrywkowo b\u0142\u0119dy. A co powiedzie\u0107 o takiej jeszcze sytuacji, kiedy niekt\u00f3re fragmenty program\u00f3w lub nawet ca\u0142e programy powstaj\u0105 po cz\u0119\u015bci losowo, np. w drodze symulowanej ewolucji (zahaczyli\u015bmy o to na wyk\u0142adzie)\u2026? 2) Po drugie jednak, w znaczeniu mniej dos\u0142ownym \u2013 przyj\u0119tym za to w\u015br\u00f3d informatyk\u00f3w i omawianym na wyk\u0142adzie \u2013 z\u0142o\u017cono\u015bci\u0105 nazywa si\u0119 pewn\u0105 w\u0142asno\u015b\u0107 algorytm\u00f3w, kt\u00f3ra dotyczy ich dzia\u0142ania<\/strong> (a nie struktury). W\u0142a\u015bciwie s\u0105 to r\u00f3\u017cne w\u0142asno\u015bci. Mamy tu przede wszystkim z\u0142o\u017cono\u015b\u0107 czasow\u0105<\/strong>, czyli miar\u0119 zale\u017cno\u015bci mi\u0119dzy czasem realizacji a rozmiarem danych. Informuje ona, jak szybko ro\u015bnie czas wykonywania algorytmu, gdy wzrasta rozmiar danych (np. w tempie logarytmicznym, czyli bardzo wolno, lub w tempie wyk\u0142adniczym, czyli bardzo szybko). Mamy te\u017c z\u0142o\u017cono\u015b\u0107 pami\u0119ciow\u0105<\/strong>, kt\u00f3ra m\u00f3wi o tym, jak ro\u015bnie zu\u017cycie pami\u0119ci maszyny, gdy ro\u015bnie rozmiar danych. Tyle tytu\u0142em dopowiedzenia do wyk\u0142adu. A wszystkim cierpliwym uczestnikom wczorajszych zaj\u0119\u0107 serdecznie dzi\u0119kuj\u0119<\/strong>.<\/p>\n Pawe\u0142 Stacewicz.<\/p>\n","protected":false},"excerpt":{"rendered":" Id\u0105c na fali wyk\u0142adu o problemach nieobliczalnych (kt\u00f3ry ju\u017c si\u0119 odby\u0142; zob. poprzedni wpis), chcia\u0142bym podzieli\u0107 si\u0119 z Pa\u0144stwem kilkoma jeszcze spostrze\u017ceniami odno\u015bnie zwi\u0105zku mi\u0119dzy z\u0142o\u017cono\u015bci\u0105, nieobliczalno\u015bci\u0105 i nieprzewidywalno\u015bci\u0105. Podzieli\u0107 si\u0119 m.in. po to, by wybrzmia\u0142a wyra\u017aniej konkluzja wyk\u0142adu. 1) … Czytaj dalej
\nTo wszystko powoduje, \u017ce z\u0142o\u017cono\u015b\u0107 strukturalna<\/strong> algorytm\u00f3w przek\u0142ada si\u0119 g\u0142adko na nieprzewidywalno\u015b\u0107<\/strong> program\u00f3w\/komputer\u00f3w, czyli na ich nieobliczalno\u015b\u0107 (w pewnym sensie). M\u00f3wi\u0105c prosto: wi\u0119kszo\u015b\u0107 program\u00f3w jest tak skomplikowana, \u017ce mimo ich wielokrotnego testowania, poprawiania itd., trudno przewidzie\u0107, co we wszystkich mo\u017cliwych sytuacjach dany program \u201ezrobi\u201d.<\/p>\n
\nOwo \u201edzia\u0142aniowe\u201d rozumienie z\u0142o\u017cono\u015bci mo\u017ce by\u0107 myl\u0105ce (zw\u0142aszcza w j\u0119zyku polskim), bo przecie\u017c nie idzie w nim o z\u0142o\u017cono\u015b\u0107 samego algorytmu (ten mo\u017ce by\u0107 bardzo prosty), ani o zawi\u0142y opis rozwi\u0105zywanego problemu (ten znowu mo\u017ce by\u0107 bardzo prosto wyra\u017cony), idzie w nim o trudno\u015b\u0107, czyli komplikacj\u0119<\/strong>, w rozwi\u0105zywaniu problemu dla du\u017cych danych. Komplikacja ta odnosi wprost do nieobliczalno\u015bci w sensie informatycznym – wszak problemy trudne lub algorytmicznie nierozwi\u0105zywalne zwie si\u0119 w\u0142a\u015bnie nieobliczalnymi<\/strong> (praktycznie lub bezwzgl\u0119dnie).
\nA w jaki spos\u00f3b owa druga, \u201edzia\u0142aniowa z\u0142o\u017cono\u015b\u0107\u201d, wp\u0142ywa na hipotetyczn\u0105 nieprzewidywalno\u015b\u0107 komputer\u00f3w (czyli nieobliczalno\u015b\u0107 w nieco innym sensie ni\u017c wy\u017cej)?
\nTu powt\u00f3rz\u0119 konkluzj\u0119<\/strong> z wyk\u0142adu: wp\u0142ywa tak, \u017ce chc\u0105c omin\u0105\u0107 problem nadmiernej z\u0142o\u017cono\u015bci czasowej lub pami\u0119ciowej danego algorytmu, trzeba stosowa\u0107 pewne \u201eniedok\u0142adne\u201d heurystyki (to znaczy: zast\u0105pi\u0107 nieefektywny algorytm dok\u0142adny efektywnym algorytmem aproksymacyjnym); heurystyki za\u015b zale\u017c\u0105 niekiedy od wybor\u00f3w losowych; to za\u015b poci\u0105ga za sob\u0105 mniejsz\u0105 lub wi\u0119ksz\u0105 nieprzewidywalno\u015b\u0107 wykonuj\u0105cego algorytm komputera.<\/p>\n
\nJe\u015bli sam wyk\u0142ad lub powy\u017csze uwagi, zainspirowa\u0142y kogo\u015b do jakich\u015b przemy\u015ble\u0144, gor\u0105co zapraszam do dyskusji w blogu (prosz\u0119 \u015bmia\u0142o komentowa\u0107).<\/p>\n