Përdoruesi:N.Bytyci/sandbox
Edsger Dijkstra
Edsger Wybe Dijkstra (11 maj 1930 – 6 gusht 2002) ishte një programues holandez, shkencëtar i sistemeve, shkencëtar i shkencave kompjuterike, inxhinier softuerik dhe pionier në shkencën e informatikës. Ai punoi si programues në Mathematisch Centrum (Amsterdam) nga viti 1952 deri në 1962. Një profesor universiteti për pjesën më të madhe të jetës së tij, Dijkstra mbajti Katedrën Schlumberger Centennial në Shkenca Kompjuterike në Universitetin e Teksasit në Austin nga viti 1984 deri në pensionimin e tij në vitin 1999. Ai ishte profesor i matematikës në Universitetin e Teknologjisë Eindhoven (1962–1984) dhe studiues në Korporatën Burroughs (1973–1984). Në vitin 1972, ai u bë personi i parë që nuk ishte as amerikan dhe as britanik që fitoi çmimin Turing.
Një nga figurat më me ndikim të gjeneratës së themelimit të shkencës kompjuterike. Kontributet e tij themelore mbulojnë fusha të ndryshme të shkencës kompjuterike, duke përfshirë ndërtimin e kompajllerave, sistemet operative, sistemet e shpërndara, programimin sekuencial dhe të njëkohshëm, paradigmën dhe metodologjinë e programimit, kërkimin e gjuhës programuese, hartimin e programit, zhvillimin e programit, verifikimin e programit, parimet e inxhinierisë softuerike, algoritmet e grafikut, dhe bazat filozofike të programimit kompjuterik dhe shkencave kompjuterike. Shumë nga punimet e tij janë burim i fushave të reja kërkimore. Disa koncepte dhe probleme që tani janë standarde në shkencën kompjuterike u identifikuan për herë të parë nga Dijkstra ose mbajnë emra të shpikur prej tij.
Deri në mesin e viteve 1960, programimi kompjuterik konsiderohej më shumë një art (ose një zanat) sesa një disiplinë shkencore. Sipas fjalëve të Harlan Mills (1986), "programimi [para viteve 1970] konsiderohej si një aktivitet privat, zgjidhjen e enigmave të shkrimit të udhëzimeve kompjuterike për të punuar si program". Në fund të viteve 1960, programimi kompjuterik ishte në një gjendje krize. Dijkstra ishte një nga një grup i vogël akademikësh dhe programuesish industrialë që mbrojtën një stil të ri programimi për të përmirësuar cilësinë e programeve. Dijkstra, i cili kishte një sfond në matematikë dhe fizikë, ishte një nga forcat shtytëse pas pranimit të programimit kompjuterik si një disiplinë shkencore. Ai shpiku frazën "programim i strukturuar" dhe gjatë viteve 1970 kjo u bë ortodoksia e re e programimit. Si krijues i lëvizjes së programimit të strukturuar (lëvizja e parë e jashtëzakonshme në historinë e programimit kompjuterik), idetë e tij rreth metodologjisë së programimit ndihmuan në vendosjen e themeleve për lindjen dhe zhvillimin e disiplinës profesionale të inxhinierisë softuerike, duke u mundësuar programuesve të organizojnë dhe menaxhojnë gjithnjë e më shumë projekte komplekse softuerike. Siç vuri në dukje Bertrand Meyer (2009), "Revolucioni në pikëpamjet e programimit i nisur nga ikonoklastia e Dijkstra-s çoi në një lëvizje të njohur si programim i strukturuar, i cili mbrojti një qasje sistematike dhe racionale për ndërtimin e programit. Programimi i strukturuar është baza për gjithçka që është bërë. pasi në metodologjinë e programimit, duke përfshirë programimin e orientuar nga objekti.”
Studimi akademik i llogaritjes së njëkohshme filloi në vitet 1960, me Dijkstra (1965) që vlerësohej si punimi i parë në këtë fushë, duke identifikuar dhe zgjidhur problemin e përjashtimit të ndërsjellë. Ai ishte gjithashtu një nga pionierët e hershëm të kërkimit mbi parimet e informatikës së shpërndarë. Puna e tij themelore mbi konkurencën, semaforët, përjashtimin e ndërsjellë, bllokimin (përqafimin vdekjeprurës), gjetjen e shtigjeve më të shkurtra në grafikë, tolerancën ndaj gabimeve, vetë-stabilizimin, ndër shumë kontribute të tjera përfshin shumë nga shtyllat mbi të cilat është ndërtuar fusha e llogaritjes së shpërndarë. Pak para vdekjes së tij në 2002, ai mori çmimin ACM PODC Influential-Paper Award në informatikë të shpërndarë për punën e tij në vetë-stabilizimin e llogaritjes së programit. Ky çmim vjetor u riemërua Çmimi Dijkstra (Edsger W. Dijkstra Prize in Distributed Computing) vitin e ardhshëm. Ndërsa çmimi, i sponsorizuar së bashku nga Simpoziumi i Shoqatës për Makineritë Kompjuterike (ACM) mbi Parimet e Informatikës së Shpërndarë (PODC) dhe Simpoziumi Ndërkombëtar i Shoqatës Evropiane për Shkenca Teorike Kompjuterike (EATCS) mbi Informatikën e Shpërndarë (DISC), pranon se "Asnjë individ tjetër ka pasur një ndikim më të madh në kërkimin në parimet e llogaritjes së shpërndarë".
Kontributet dhe ndikimi pionier në shkencën e informatikës
Edhe pse një fizikan teorik nga trajnimi, Dijkstra u bë një nga figurat më me ndikim të gjeneratës së themelimit të shkencës kompjuterike. Si një pionier i hershëm në shumë fusha kërkimore të shkencës kompjuterike, ai ndihmoi në formimin e disiplinës së re si nga një këndvështrim inxhinierik ashtu edhe nga ai akademik. Shumë nga punimet e tij janë burim i fushave të reja kërkimore. Shumë koncepte që tani janë standarde në shkencën kompjuterike u identifikuan për herë të parë nga Dijkstra ose mbajnë emra të shpikur prej tij. Disa probleme të rëndësishme gjithashtu u formuluan dhe u zgjidhën fillimisht prej tij. Një studim i vitit 1994 me mbi një mijë profesorë të shkencave kompjuterike u krye për të marrë një listë të 38 punimeve shkencore më me ndikim në këtë fushë, dhe Dijkstra është autore e pesë punimeve. Në moshën 42-vjeçare, ai u bë fituesi i parë jo-amerikan, jo britanik dhe evropian kontinental i çmimit Turing. Gjatë dyzet viteve të tij si shkencëtar informatikë, i cili përfshinte pozicione si në akademi ashtu edhe në industri, Dijkstra dha një kontribut të rëndësishëm në shumë fusha të shkencës kompjuterike, duke përfshirë ndërtimin e përpiluesve, sistemet operative, llogaritjen e njëkohshme (programimin e njëkohshëm), informatikë të shpërndarë, programimin. paradigma dhe metodologjia, kërkimi i gjuhës programuese, dizajni i programit, zhvillimi i programit, verifikimi i programit, parimet e inxhinierisë së softuerit, dizajni i algoritmit dhe bazat filozofike të programimit kompjuterik dhe shkencave kompjuterike. Përveç kësaj, Dijkstra ishte shumë i interesuar në mësimdhënien e shkencave kompjuterike dhe në marrëdhëniet midis shkencës akademike të informatikës dhe industrisë së softuerit. Kontributet e tij kryesore pioniere (duke përfshirë idetë, shpikjet dhe inovacionet) përfshijnë: Konceptet, metodat, parimet dhe teoritë: përpiluesi Dijkstra–Zonneveld ALGOL 60 (përpiluesi i parë i plotë i punës ALGOL 60), stacki i thirrjeve, konkurenca, programimi i njëkohshëm, proceset e njëpasnjëshme bashkëpunuese, seksioni kritik, përqafimi vdekjeprurës (bllokimi), problemi i filozofëve kombëtarë holandezë problemi i flamurit, sistemet tolerante ndaj gabimeve, programimi pa goto, gjuha e komandës së ruajtur (komandat e ruajtura), struktura me shtresa në arkitekturën e softuerit, nivelet e abstraksionit, programimi me shumë fije, përjashtimi i ndërsjellë (mutex ose bllokimi), problemi prodhues-konsumator (problemi i tamponit të kufizuar ), familjet e programeve, semantika e transformatorëve kallëzues, sinkronizimi i procesit, sistemet e shpërndara vetë-stabilizuese (vetë-stabilizimi), semafori, ndarja e shqetësimeve, problemi i berberit të fjetur, analiza e strukturuar, programimi i strukturuar, sistemi i shumëprogramimit, jodeterminizmi i pakufishëm, llogaritja e parakushteve më të dobëta Algoritmet: algoritmi i Dijkstra-s, algoritmi DJP, algoritmi Dijkstra-Scholten, algoritmi i Dekker-it (përgjithësimi), algoritmi i bankierit, renditja e lëmuar, algoritmi i oborrit të largimit, algoritmi i shënimit me tre ngjyra, algoritmi i shënjimit me tre ngjyra, algoritmi i parandalimit të njëkohshëm, algoritmi i ndërprerjes, algoritmi algoritmi i algoritmit, -algoritme stabilizuese.
Puna algoritmike
Algoritmi i Dijkstra-s
Zgjedh kulmin e pavizituar me distancën më të ulët, llogarit distancën përmes saj me çdo fqinj të pavizituar dhe përditëson distancën e fqinjit nëse është më e vogël. Shënoni i vizituar (i vendosur në të kuqe) kur mbaroi me fqinjët. Puna algoritmike e Dijkstra-s (veçanërisht algoritmet grafike, algoritmet e njëkohshme dhe algoritmet e shpërndara) luan një rol të rëndësishëm në shumë fusha të shkencës informatike. Sipas Leslie Lamport (2002), Dijkstra "filloi fushën e algoritmeve të njëkohshme dhe të shpërndarë me punimin e tij CACM të vitit 1965 "Zgjidhja e një problemi në kontrollin e programimit të njëkohshëm", në të cilin ai së pari deklaroi dhe zgjidhi problemin e përjashtimit të ndërsjellë. Siç shpjegon Lamport, "ajo letër ndoshta është arsyeja pse ekziston PODC (...). Ajo mbetet edhe sot e kësaj dite gazeta më me ndikim në këtë fushë. Fakti që nuk fitoi një çmim PODC Influential Paper Award pasqyron një ndarje artificiale midis algoritmeve të njëkohshme dhe atyre të shpërndara. – një ndarje që nuk ka ekzistuar kurrë në veprën e Dijkstra-s.” Në vitin 1959 Dijkstra botoi në një artikull 3 faqesh 'Një shënim mbi dy probleme në lidhje me grafikët' algoritmin për të gjetur shtegun më të shkurtër në një grafik midis çdo dy nyjesh të dhëna, tani i quajtur algoritmi i Dijkstra. Ndikimi i tij gjatë 40 viteve të ardhshme përmblidhet nga artikulli i Mikkel Thorup, "Shtigjet më të shkurtra të padrejtuara me një burim të vetëm me peshë pozitive të plotë në kohën lineare" (1999): "Që nga viti 1959, të gjitha zhvillimet teorike në SSSP [Shtigjet më të shkurtra me një burim të vetëm] sepse grafikët e përgjithshëm të drejtuar dhe të padrejtuar janë bazuar në algoritmin e Dijkstra." Algoritmi i Dijkstra përdoret në SPF, Rruga e Shkurtër e Parë, e cila përdoret në protokollet e rrugëtimit OSPF dhe IS-IS. Modifikime të ndryshme të algoritmit të Dijkstra janë propozuar nga shumë autorë duke përdorur heuristikat për të reduktuar kohën e ekzekutimit të kërkimit të rrugës më të shkurtër. Një nga algoritmet heuristike më të përdorura është algoritmi i kërkimit A* (i përshkruar për herë të parë nga Peter Hart, Nils Nilsson dhe Bertram Raphael nga Instituti i Kërkimeve Stanford në 1968), qëllimi kryesor është të zvogëlohet koha e ekzekutimit duke reduktuar hapësirën e kërkimit. . Dijkstra mendoi për problemin e rrugës më të shkurtër kur punoi në Qendrën Matematikore në Amsterdam në 1956 si programues për të demonstruar aftësitë e një kompjuteri të ri të quajtur ARMAC. Objektivi i tij ishte të zgjidhte një problem dhe një përgjigje (që do të prodhohej nga kompjuteri) që njerëzit jo-kompjuter mund ta kuptonin. Ai krijoi algoritmin e rrugës më të shkurtër në rreth 20 minuta pa ndihmën e letrës dhe stilolapsit dhe më vonë e zbatoi atë për ARMAC për një hartë transporti paksa të thjeshtuar të 64 qyteteve në Holandë (në mënyrë që 6 bit të mjaftonin për të përfaqësuar qytetin në algoritëm). Siç kujton ai, në një intervistë të botuar në 2001: Cila është mënyra më e shkurtër për të udhëtuar nga Roterdami në Groningen, në përgjithësi: nga qyteti i caktuar në qytet? Është algoritmi për rrugën më të shkurtër, të cilin e projektova në rreth njëzet minuta. Një mëngjes po bëja pazar në Amsterdam me të fejuarën time të re dhe të lodhur, u ulëm në tarracën e kafenesë për të pirë një filxhan kafe dhe po mendoja nëse mund ta bëja këtë, dhe më pas projektova algoritmin për rrugën më të shkurtër . Siç thashë, ishte një shpikje njëzet minutash. Në fakt është botuar në ’59-ën me tre vjet vonesë. Publikimi është ende i lexueshëm, në fakt është mjaft i këndshëm. Një nga arsyet që është kaq e bukur ishte se e projektova pa laps dhe letër. Mësova më vonë se një nga avantazhet e dizajnit pa laps dhe letër është se jeni pothuajse i detyruar të shmangni të gjitha kompleksitetet e shmangshme. Më në fund ai algoritëm u bë, për habinë time të madhe, një nga gurët e themelit të famës sime.
— Edsger Dijkstra, në një intervistë me Philip L. Frana, Communications of the ACM 53 (8), 2001.
Hulumtimi i sistemit operativ
Në vitet 1960 Dijkstra dhe kolegët e tij në Eindhoven projektuan dhe zbatuan sistemin operativ THE (që qëndron për 'Technische Hogeschool Eindhoven'), i cili u organizua në shtresa abstraksioni të identifikuara qartë. Artikulli i tij i vitit 1968 mbi këtë temë siguroi themelin për dizajnet e mëvonshme të sistemeve operative. David Alan Grier i Shoqërisë Kompjuterike IEEE shkruan, "Në përgjithësi e gjurmojmë idenë e ndërtimit të sistemeve kompjuterike në shtresa që nga një punim i vitit 1967 që shkencëtari holandez i kompjuterave Edsger Dijkstra dha në një konferencë të përbashkët të Shoqërisë Kompjuterike IEEE/ACM. Përpara këtij dokumenti, inxhinierët kishte luftuar me problemin e organizimit të softuerit. Nëse shikoni shembujt e hershëm të programeve, dhe mund të gjeni shumë në bibliotekën elektronike të Shoqërisë së Kompjuterëve, do të zbuloni se shumica e kodeve të asaj epoke janë të ndërlikuara, të vështira për t'u lexuar, vështirë për t'u modifikuar dhe sfidues për t'u ripërdorur. Në punimin e tij të vitit 1967, Dijkstra përshkroi se si softueri mund të ndërtohej në shtresa dhe dha një shembull të një sistemi operativ të thjeshtë që përdorte pesë shtresa. Ai pranoi se ky sistem mund të mos ishte një test realist i tij idetë por ai argumentoi se "sa më i madh të jetë projekti, aq më thelbësor është strukturimi!" Ideja e përdorimit të shtresave për të kontrolluar kompleksitetin është bërë një shtyllë kryesore e arkitekturës së softuerit. Ne e shohim atë në shumë forma dhe aplikoni atë në shumë probleme. Ne e shohim atë në hierarkinë e klasave në programimin e orientuar nga objekti dhe në strukturën e arkitekturës së orientuar nga shërbimi (SOA). SOA është një aplikim relativisht i fundit i shtresimit në shkencën kompjuterike. Ai u artikulua në 2007 si një mjet për të kontrolluar kompleksitetin në sistemet e biznesit, veçanërisht sistemet e shpërndara që përdorin në mënyrë thelbësore internetin. Ashtu si plani i Dijkstra për zhvillimin e sistemit, sistemi i tij i shtresimit quhet SOA Solution Stack ose S3. Nëntë shtresat e S3 janë: 1) sistemet operacionale, 2) komponentët e shërbimit, 3) shërbimet, 4) proceset e biznesit, 5) veprimet e konsumatorit, 6) integrimi i sistemit, 7) kontrolli dhe sigurimi i cilësisë, 8) arkitektura e informacionit dhe 9) qeverisja dhe politikat e sistemit.” Dijkstra organizoi dizajnin e sistemit në shtresa në mënyrë që të zvogëlojë kompleksitetin e përgjithshëm të softuerit. Megjithëse termi 'arkitekturë' nuk ishte përdorur ende për të përshkruar dizajnin e softuerit, kjo sigurisht u konsiderua si pamja e parë e arkitekturës së softuerit.[70] Ai prezantoi një sërë parimesh të projektimit të cilat janë bërë pjesë e fjalorit të punës së çdo programuesi profesionist: nivelet e abstraksionit, programimi në shtresa, semafori dhe proceset e njëpasnjëshme bashkëpunuese. Punimi i tij origjinal mbi sistemin operativ THE u ribotua në numrin e 25-vjetorit të Communications of ACM, në janar 1983. Si hyrje, kryeredaktori thotë: "Ky projekt inicioi një linjë të gjatë kërkimesh në sistemet me shumë nivele arkitektura - një linjë që vazhdon deri në ditët e sotme sepse modulariteti hierarkik është një qasje e fuqishme për organizimin e sistemeve të mëdha.
Jeta personale dhe vdekja
Dijkstra bëri një mënyrë jetese modeste, deri në atë pikë sa ishte spartane. Shtëpia e tij dhe e gruas së tij në Nuenen ishte e thjeshtë, e vogël dhe modeste. Ai nuk kishte televizor, apo celular dhe nuk shkonte në kinema. Ai luante në piano dhe, ndërsa ishte në Austin, i pëlqente të shkonte në koncerte. Një dëgjues entuziast i muzikës klasike, kompozitori i preferuar i Dijkstra ishte Mozart. Dijkstra vdiq më 6 gusht 2002. Sipas zyrtarëve në Universitetin e Teksasit, shkaku i vdekjes ishte kanceri.