Edsger Vibe Dijkstra
Kako programirati nemoguće
Kada se mladi Edsger Dijkstra ženio Marijom Debets 1957. godine, u venčanom listu naveo je da je po zanimanju programer. Matičar je zahtevao da se u list upiše bilo šta „normalno” jer tada u Holandiji nije bilo tog zanimanja.
Edsger Vibe Dijkstra 11. maj 1930. Roterdam – 6. avgust 2002 . bio je holandski matematičar, programer, softverski inženjer i esejista. Dobio je Turingovu nagradu 1972. za fundamentalni doprinos razvoju strukturiranih programskih jezika.
Početkom 1950-ih, „elektronski mozgovi“ su bili novina. Dijkstra je slučajno naleteo na Adrijana van Vajngardena, direktora Odeljenja za računanje u Matematičkom centru u Amsterdamu, koji mu je ponudio posao pa je tako i zvanično postao prvi „programer“ Holandije 1952. godine. Tada to nije bila ugledna profesija, ali je on shvatio da su računari tu da ostanu i da bi im valjalo dodati neku trunku ‘pameti’ više. 1959. Mladi matematičar je doktorirao na Univerzitetu u Amsterdamu tezom 'Komunikacija sa automatskim računarom' posvećenoj opisu asemblerskog jezika dizajniranog za prvi komercijalni računar razvijen u Holandiji, Electrologica Ks1.
Od 1952. do 1962. Dijkstra je radio u Matematiškom centru u Amsterdamu, gde je blisko sarađivao sa Bramom Janom Lupstrom i Karelom S. Šoltenom, koji su bili zaduženi za hardver. Njihov saradnja je delovala neobično: prvo bi odlučili o interfejsu između hardvera i softvera, zatim bi dizajneri hardvera moralistriktno da poštuju dogovor, dok bi Dijkstra, pisao softver za nepostojeću mašinu. Ovo ga je naučilo važnosti dokumentacije i da se otklanjanje grešaka u programu može izbeći pažljivim dizajnom.
Dijkstra je formulisao i rešio problem najkraćeg puta, a sa Jaap Zonneveld-om je razvio prvi kompajler za programski jezik ALGOL 60 skoro godinu pre nego što je proizveden sam računar. ALGOL 60 je predstavljao ključni napredak u usponu strukturiranog programiranja. Kasnih 1960-ih izgradio je operativni sistem THE (nazvan po univerzitetu, tada poznat kao Technische Hogeschool Eindhoven), koji je uticao na dizajn narednih operativnih sistema korišćenjem softverski zasnovane virtuelne memorije sa stranicama.
Goto je izjava koja se nalazi u mnogim računarskim programskim jezicima. On vrši jednosmerni prenos kontrole na drugu liniju koda; nasuprot tome, opoziv funkcije obično vraća kontrolu. Preskočene lokacije se obično identifikuju pomoću oznaka, iako neki jezici koriste brojeve redova. Na nivou mašinskog koda, goto je oblik izraza grananja ili špila.
Teorema strukturiranog programa je dokazala da naredba goto nije neophodna za pisanje programa koji se mogu izraziti kao dijagrami toka.
Dijkstrin algoritam je algoritam za pronalaženje najkraćih putanja između čvorova na grafu, koji može predstavljati, na primer, mreže puteva. Algoritam postoji u mnogo varijanti. Dijkstrin originalni algoritam pronašao je najkraći put između dva data čvora, ali češća varijanta fiksira jedan čvor kao „izvorni“ čvor i pronalazi najkraće putanje od izvora do svih ostalih čvorova na grafu, stvarajući stablo najkraćeg puta . Dijkstra algoritam koristi oznake koje su pozitivni celi brojevi. Može se generalizovati korišćenjem bilo koje oznake koje su delimično uređene, pod uslovom da su naknadne monotono neopadajuće. Ova generalizacija se naziva generički Dijkstrin algoritam najkraćeg puta.
U nekim oblastima, posebno veštačkoj inteligenciji, Dijkstrin algoritam ili njegove varijante poznate kao traženje uniformnih troškova formulisan je kao primer opštije ideje pretrage. Radi lakšeg razumevanja, ovde se koriste termini raskrsnica, put i mapa, međutim, u formalnoj terminologiji ovi termini su vrh, ivica i graf. Pretpostavimo da želite da pronađete najkraći put između dve raskrsnice na mapi grada: početne tačke i odredišta. Dijkstrin algoritam inicijalno beskonačno označava rastojanje do svake druge raskrsnice na mapi. Ovo se radi ne da bi se impliciralo da postoji beskonačna udaljenost, već da se primeti da te raskrsnice još nisu posećene. Neke varijante ove metode ostavljaju rastojanja raskrsnica neoznačenim. Sada izaberite trenutnu raskrsnicu na svakoj iteraciji. Za prvu iteraciju, trenutna raskrsnica će biti početna tačka, a rastojanje do nje će biti nula. Za naredne iteracije trenutna raskrsnica će biti najbliža neposećena raskrsnica početnoj tački. Ovaj algoritam se stoga proširuje napolje od početne tačke, interaktivno uzimajući u obzir svaki čvor koji je bliži u smislu udaljenosti najkraće putanje dok ne stigne do odredišta. Kada se ovako shvati, jasno je kako algoritam nužno pronalazi najkraći put.
Zatim se Dijkstra pridružio Burroughs Corporation, koja je bila poznata po proizvodnji računara zasnovanih na inovativnoj hardverskoj arhitekturi. Uveo je i rad od kuće. U stvari, Dijkstra je bio jedini istraživač Barouza i radio je povremeno putujući u filijale u Sjedinjenim Državama. Smanjio je broj časova na univerzitetu na jedan dan u nedelji. Taj dan, utorak, ubrzo je postao poznat kao 'Tuesdai Afternoon Club', seminar tokom kojeg je sa kolegama razgovaraonauci, sagledavajući sve aspekte: notaciju, organizaciju, prezentaciju, jezik, sadržaj. Isti princip je 1984. Preneo na Univerzitet Teksasa u Ostinu. Napisao je skoro 500 dokumenata u EVD seriji od kojih su većina bili tehnički izveštaji, za privatni promet unutar odabrane grupe.
Među njegovim najpoznatijim doprinosima kompjuterskoj nauci je algoritam najkraćeg puta, poznat kao Dijkstrin algoritam, koji se široko predaje na savremenim studijama informatike. Njegovi ostali doprinosi uključuju algoritam ranžirne stanice; multiprogramski sistem THE, važan rani primer strukturiranja sistema kao skupa slojeva; Bankerov algoritam i konstrukcija semafora za koordinaciju više procesora i programa. Drugi koncept koji je Dijkstra formulisao u oblasti distribuiranog računarstva je koncept samostabilizacije – alternativni način da se obezbedi pouzdanost sistema.
Kao univerzitetski profesor veći deo života, Dijkstra je nastavu doživljavao ne samo kao obaveznu aktivnost već i kao ozbiljan istraživački poduhvat. Njegov stil predavanja je bio idiosinkratičan. Tokom predavanja, pravio je duge pauze između rečenica koje su mu služile kao način da razmišlja u hodu. Njegovi kursevi nisu imali mnogo veze sa računarstvom, ali su se uvodili posetioce u dubine algebre grananja (branching algebra in the deep wet forest). Na početku svakog semestra fotografisao bi studente, kako bi zapamtio njihova imena. Dok je držao predavanja, pisao je dokaze kredom na tabli i prezirao ono što se danas zove Pover -point. Pozvao je studente da predlože ideje, koje je potom analizirao. Završne ispite je vodio usmeno bez unapred formulisanih pitanja. Nije koristio programe za obradu teksta. Većinu publikacija napisao je sam. Nikada nije imao sekretaricu i sam se brinuo za svu prepisku. Njegov rad se odlikovao elegancijom, autor je više od 1.300 radova, od kojih su mnogi pisani rukom. Bili su to eseji i parabole; bajke i upozorenja; sveobuhvatna objašnjenjna procesa programiranja i pedagoške instrukcije. Poput Vidgenštajna imao je običaj da kopira svaki rad i distribuira ga maloj grupi kolega koji biga dalje širili grupama posvećenih.
Bio je poznat po duhovitosti, elokvenciji, grubosti, naglosti i često okrutnosti prema kolegama, kao i po rečima, kao što su: „Pitanje da li mašine mogu da misle je jednako relevantno kao i pitanje da li Podmornice mogu da rone." Njegov savet studentu koji je pitao kako da odabere temu za istraživanje, bio je: "Radi ono što samo ti možeš". Kao otvoren i kritički vizionar, oštro se protivio učenju BASIC-a.
U mnogim alegoričnim pričama, Dijkstra je opisao izmišljenu kompaniju čiji je bio predsednik. Kompanija se zvala Mathematics, Inc i bila je osnovana za komercijalizaciju matematičkih teorema na isti način na koji su softverske kompanije komercijalizovale proizvodnju kompjuterskih programa. Izmislio je brojne aktivnosti i izazove Mathematics Inc opisao ih ih u nekoliko EVD priča.
U „Skromnom programeru „ (1972), napisao: je „Ne smemo zaboraviti da nije naš posao da pravimo programe, već da dizajniramo klase proračuna koje će pokazati željeno ponašanje.“ Protivio se uključivanju softverskog inženjeringa među akademske računarske nauke. Napisao je da, „Kako je ekonomija poznata kao „Bedna nauka“, softversko inženjerstvo treba da bude poznato kao „Paćenička disciplina“, zato što je osuđeno na propast zbog toga što je njen cilj kontradiktoran sam sebi.“
Dijkstra je bio jedan od onih 'hard core' matematicara, koji su smatrali prirodne jezike dvosmislenim i neupotrebljivim za nauku a ljudsku inteligenciju inferiornom u odnosu na kompjutersku inteligenciju. Cuvena je njegova izjava da je pitanje da li masine mogu da misle podjednako smisleno kao i pitanje da li podmornica moze da pliva.