O wyższości uniwersytetów nad politechnikami i na odwrót.

Zacznę od czegoś co przerazi wszystkich. Nie należy się jednak bać, pokolej wszystko w kolejnych krokach wyjaśnie.

Teza: Nauka informatyki na uniwersytecie (konkretnie na wydziale o podłożu matematycznym) jest bardziej praktyczne od studiowania na politechnice.

Co to jest teza? Inaczej mówiąc stwierdzenie, które trzeba udowodnić.  Dlaczego takie?
Czasami człowiek siedzi i myśli (a potem głupieje na starość) i nic dobrego z tego nie wychodzi. Dlatego się położyłem, ale wtedy jeszcze głupsze mysli wchodzą do głowy. No i pojawiła się ona.

Nie chce mi się!

No i zaczałem szukać motywacji do nauki… A jako, że nie znalazłem jej w szafie, ani w lodówce, ani też dwóch kilogramach mandarynek (przy okazji, jedzenie mandarynek ma ciekawe skutki uboczne). Podjąłem decyzje – ulitmatum. W każdej chwili wolnej od nauki będe ćwiczył. No i doszło do problemów, bo trudno nazwać ćwiczeniem siedzenie w rozkroku przez godzinę, ani też siedzenie na własnych piętach, tylko po to, aby wymigać się od nauki. No to zajrzałem do historii i tam mężczyźni zasięgali motywacji szukając weny spoglądając na kobiety, albo jak byli mniej szczęsliwi to patrzyli na różnorakie boginie. Kobiet, które by się nie obraziły, gdy bym o nich myślał brak, a boję się też interwencji boskiej, gdybym pomyślał o nie o tej boginii co trzeba, więc zostałem w kropce.
No to został już tylko ostatni cel moich westchnień… nauka.
I jakoś tak szukając, gdzie by tu zacząć zacząłem myśleć, gdzie jest lepiej na matematycznym wydziale czy na politechnice. No i tak powstała teza.

Dowód: Na przykłądzie maszyny Turinga i problemu efektywności.
Istnieje takie coś jak uniwersalna maszyna Turinga. To taki model, może bardziej koncepcja urządzenia, które wczytując dane z prawostronnie nieskończonej taśmy (czyli ma początek, ale końca nie widać) przesuwa się po niej i zmienia swój stan. Jeśli skończy wykonywać program to patrzymy w jakim stanie się znajduje. Jeśli stan, jest tak zwanym stanem akceptującym maszyna pomyślnie zakończyła pracę (algorytm, czyli problem został rozwiązany). I co ma tu do gadania efektywność? Tu zaczyna się różnica pomiędzy matematyką, a inżynierią informatyczną.
Dla matematyka “efektywny algorytm” oznacza ni mniej nie więcej niż coś co się zakończy w skończonym czasie, czyli mówiąc po ludzku – “w końcu zakończy się”. Nie ma znaczenia czy zajmie to minutę, dwa tygodnie, tysiąc lat.
Dzięki takiemu założeniu mamy znacznie więcej możliwości niż inżynierowie, bo dla tych efektywny znaczy taki co się “szybko zakończy”. Szybko, czyli w czasie krótszym niż parzenie mocnej herbaty.

Tu pojawia się przewaga matematyków, możemy patrzeć na problemy nie pod kątem implementacji, ale ich specyfikacji. Innymi słowy tworzymy ładne twierdzenie, które pięknie działa na maszynie Turinga i już! Nie interesuję mnie to czy zajmie to tydzień, dwa, a może rok. Udowadniam, że jest to możliwe i nikt mi nie powie, że jest inaczej. Wtedy inżynier załamie ręce i powie, że to jest nie wykonalne, bo czekając na wynik mu się czajnik spali, albo herbata wystygnie.

Koniec dowodu.

I w czym tkwi problem? W perspektywie. Tu znów odwołuję się do Maszyny Turinga.

Udowodniono (tu musicie mi uwierzyć na słowo), że Maszyna Turinga jest wstanie rozwiązać KAŻDY efektywny (w sensie matematycznym)  algorytm, wystarczy dać jej odpowiednio dużo czasu. Problem jest taki, że nie wiemy jak dużo tego czasu potrzeba. Maszyna Turinga to taka magiczna skrzynka, nie widać co się dzieje w środku, a jedyna oznaką pracy są dwie lampki – czerwona i zielona. Jeśli maszyna zakończy pracę zapali się jedna z nich, zależnie od tego czy problem jest rozwiązany. Ja (matematyk) będe siedział i patrzył na tą lampkę, aż do uchachanej śmierci, bo MT będzie w kółko robić jedną petlę (bo na przykład mój problem jest nie rozwiązaywalny). Owszem mogę przed uruchomieniem MT sprawdzić (efektywnie! czyli znów odowołujemy się do MT) czy dany problem jest rozwiązywalny. I dopiero wtedy uruchomić czekając na wynik.
W tym czasie inżynier skonstruuje dziesięć osobnych modeli (urządzeń), które nie rozwiążą ten problem w 99% przypadkach poprawnie, a w czasie od ich włączenia do wyrzucenia wyniku nie zdążycie powiedzieć “Blueberry Pie!”, no może chwilkę dłużej.
Przykład? Automaty i języki formalne, w czasie, gdy my studenci WMI próbowaliśmy skonsturować moduł sprawdzający czy słowo należy do klasy języków zdefiniowanych przez wyrażenie regularne. OK! Tłumaczę: czy dany wyraz pasuję do schematu, inżynier weźmie gotowy program i go wykorzysta w swoim projekcie. Różnica?
Nasze moduły (jeśli!), gdy kończą pracę po 30 sekundach to jest dobrze, podczas gdy dostępne na rynku programy robią to w czasie rzędu (czyli zbliżonym) do 0.1s, hmmm coś ta matematyczna wersja niechce działać. Pech.

Najgorsza jednak jest niepewność. Skoro nie widzimy co się dzieje w MT to niemożemy jej wyłączyć świadomie wiedząc, że program się zawiesił (wpadł w nieskończoną – bezsensowną – pętle). Nie ma pewności, czy po 163 dniach, dwóch godzinach i 54 minutach program liczący różnicę pomiędzy 3, a 2 (w pierścieniu liczb całkowitych – to tak dla matematyków, żeby się odczepili!), jak odłączymy maszynę od prądu czy to był dobry pomysł. W końcu po 163 dniach, dwóch godzinach, 54 minutach i 10 sekundach mógł się ten algorytm skończyć. Inżynieryjne podejście znów górą!

No i tu dochodzi do sprzeczności. Moje odwoływanie się do nauki padło, a ja wracam do ćwiczeń fizycznych. Dziś,  wspinam się na Ramadę wraz z Polakami czytając relacje z wyprawy. Tak! To też ćwiczenie fizyczne, książka w końcu coś waży, nie?