Donald Knuth er líklega þekktasti núlifandi tölvunarfræðingurinn. Hann er fæddur í Bandaríkjunum árið 1938 og hefur verið prófessor við Stanford-háskóla frá 1968. Knuth er menntaður stærðfræðingur en fékk áhuga á tölvum þegar hann var við háskólanám. Fyrsta tölvan sem hann sá var IBM 650 en það var fyrsta fjöldaframleidda tölvan. Knuth fékk að nota hana til að reikna ýmsa tölfræði um hafnaboltaleikmenn í háskólanum og eftir það varð ekki aftur snúið. Hann lauk doktorsnámi í stærðfræði við California Institute of Technology en sérhæfði sig í þeirri stærðfræði sem nýttist best í tölvunarfræði og þá sérstaklega við að greina reiknirit.
IBM 650 var engin smásmíði!
Reiknirit (e. algorithm) er lýsing á aðferð til að leysa verkefni. Það geta verið til margar mismunandi aðferðir til að leysa sama verkefnið, til að mynda eru til margir tugir ólíkra röðunarreiknirita. Donald Knuth hefur lagt mikið af mörkum á þessu sviði tölvunarfræðinnar. Hann hefur bæði hannað ný reiknirit fyrir ýmis verkefni og skilgreint almennar formlegar aðferðir til að greina og flokka reiknirit. Greiningar Knuths á reikniritum þykja mjög nákvæmar og skýrar. Greinar hans og bækur hafa því oft verið notaðar sem sýnidæmi um það hvernig á að setja fram og greina reiknirit. Flestir vísindamenn sem starfa á þessu sviði tölvunarfræðinnar hafa orðið fyrir miklum áhrifum frá Donald Knuth.
Knuth er einna þekktastur fyrir bókaröðina The Art of Computer Programming, sem mætti þýða sem Listin að forrita. Þó að aðeins hafi komið út rúmlega þrjú bindi af áætluðum sjö, þá þykja þær með áhrifamestu tölvunarfræðibókum sem gefnar hafa verið út. Allir alvörutölvunarfræðingar hafa að minnsta kosti fyrsta bindið uppi í hillu hjá sér! Þrátt fyrir nafnið fjalla bækurnar ekki aðeins um forritun, heldur eru þær eins konar yfirlit yfir ýmis svið tölvunarfræðinnar. Til dæmis fjallar einn kafli í bindi tvö um slembitölugjafa, það er hvernig á að búa til slembitölur í tölvum. Þó að kaflinn hafi verið skrifaður fyrir meira en 40 árum er hann enn þá ein aðalheimildin á þessu sviði.
Knuth hóf að skrifa bækurnar árið 1963 og setti strax fram áætlun um að þær yrðu í sjö bindum. Knuth þykir mjög nákvæmur og er hann haldinn mikilli fullkomnunaráráttu sem gerði það að verkum að fyrsta bindið kom ekki út fyrr en árið 1968, annað bindið kom út árið eftir og það þriðja árið 1973. Þegar hér var komið við sögu fannst Knuth framsetningin á bókunum ekki nógu góð og vildi gera eitthvað í því. Bækurnar innihalda mikið af stærðfræðiformúlum og það var erfitt að gera prentsmiðjunni það skiljanlegt nákvæmlega hvernig hann vildi að formúlurnar litu út. Hann ákvað því að hanna sitt eigið forrit til þess að setja upp texta og stærðfræðiformúlur þannig að útkoman yrði falleg. Umbrotsforritið sem Knuth hannaði (eftir átta ára vinnu!) heitir TeX (síðasti samhljóðinn er borinn fram eins og sá síðasti í Bach) og í dag er það nær allsráðandi í tölvunarfræði, stærðfræði, eðlisfræði og flestum greinum verkfræði. Allar fræðilegar tímaritsgreinar og mjög margar bækur á þessum sviðum eru skrifaðar í TeX. Við upphaflega hönnun TeX dró Knuth fram ýmis áhugaverð verkefni sem þurfti að leysa til að setja upp texta. Sem dæmi má nefna hvernig skipta á orðum milli lína þannig að línurnar verði sem jafnastar. Knuth hannaði síðan reiknirit fyrir þessi verkefni og lýsti þeim á sinn skýra og greinargóða hátt. Hann forritaði fyrstu útgáfuna af TeX sjálfur og gaf forritið síðan út sem bók. Bókin er um 600 blaðsíður og er mjög læsileg.
Á undanförnum árum hefur Donald Knuth að mestu helgað sig ritun bókanna Listin að forrita. Hann hefur endurútgefið fyrstu þrjú bindin (1997-1998), auk þess að vinna að fjórða bindinu. Fyrsti hluti fjórða bindisins kom út árið 2010 og er áætlað að fleiri hlutar þess bindis komi út á næstu árum. Knuth áætlar að fimmta bindið komi út árið 2020!
Sem dæmi um fjölbreytt áhugamál Knuths þá skrifaði hann árið 1984 grein í eitt virtasta stærðfræðitímarit Bandaríkjana um hið svokallaða salernispappírsvandamál (e. The Toilet Paper Problem). Á tilteknu salerni eru ávallt tvær rúllur af salernispappír og notandi getur valið af hvorri rúllunni hann tekur pappírinn sem hann þarf að nota. Knuth gefur sér að til séu tvær tegundir notenda, þeir sem velja alltaf af stærri rúllunni og þeir sem velja alltaf af þeirri minni. Í stuttu máli felst vandamálið í að áætla hversu mikið af salernispappír er eftir á annarri rúllunni þegar hin er orðin tóm. Þetta fer að sjálfsögðu eftir því hvor tegundin af notendunum er algengari. Knuth leiðir út, með mjög flottri stærðfræði, formúlu fyrir fjölda blaða á rúllunni sem eftir er, miðað við hlutfall notenda sem velur alltaf af stærri rúllunni. Í lok greinarinnar þakkar Knuth arkitektum tölvunarfræðibyggingarinnar í Stanford fyrir að hafa óvart stungið upp á þessu áhugaverða verkefni!
Þessi grein um salernispappírsvandamálið er gott dæmi um húmorinn sem Knuth er þekktur fyrir. Hann hefur oft laumað bröndurum inn í bækur sínar, sérstaklega í atriðaorðaskránni. Til dæmis kom nafn Bo Derek fyrir í atriðaorðaskrá einnar bókar hans með tilvísunum í blaðsíður sem innihéldu töluna 10. Enn er eitthvað um slíkt spaug í bókum hans sem lesendur hafa ekki uppgötvað. Einnig má nefna að útgáfunúmer á TeX fylgja tölunni pí. Þannig var til útgáfa 3, síðan 3.1, svo 3.14 og svo framvegis. Núverandi útgáfa af TeX er útgáfa 3.1415926, sem er átta stafa nálgun á pí.
Þó Donald Knuth sé orðinn 73 ára er hann enn í fullu fjöri og vinnur hörðum höndum við bækur sínar. Tölvunarfræðingar heimsins vona að honum endist aldur og heilsa til að ljúka sem mestu af því verki sem hann hefur sett sér.
Heimildir og annað ítarefni:
Hjálmtýr Hafsteinsson. „Hver er Donald Knuth og hvert er framlag hans til tölvunarfræðinnar?“ Vísindavefurinn, 30. júní 2011. Sótt 19. apríl 2024. http://visindavefur.is/svar.php?id=60137.
Hjálmtýr Hafsteinsson. (2011, 30. júní). Hver er Donald Knuth og hvert er framlag hans til tölvunarfræðinnar? Vísindavefurinn. Sótt af http://visindavefur.is/svar.php?id=60137
Hjálmtýr Hafsteinsson. „Hver er Donald Knuth og hvert er framlag hans til tölvunarfræðinnar?“ Vísindavefurinn. 30. jún. 2011. Vefsíða. 19. apr. 2024. <http://visindavefur.is/svar.php?id=60137>.
Hér getur þú sent okkur nýjar spurningar um vísindaleg efni.
Hafðu spurninguna stutta og hnitmiðaða og sendu aðeins eina í einu. Einlægar og vandaðar spurningar
um mikilvæg efni eru líklegastar til að kalla fram vönduð og greið svör. Ekki er víst að tími vinnist til að
svara öllum spurningum.
Persónulegar upplýsingar um spyrjendur eru eingöngu notaðar í starfsemi vefsins, til dæmis til að
svör verði við hæfi spyrjenda. Spurningum er ekki sinnt ef spyrjandi villir á sér heimildir eða segir ekki
nægileg deili á sér.
Spurningum sem eru ekki á verksviði vefsins er eytt.
Að öðru leyti er hægt að spyrja Vísindavefinn um allt milli himins og jarðar!
Sólin
Rís 05:40 • sest 21:16
Tunglið
Rís 15:13 • Sest 05:59
Flóð
Árdegis: 03:57 • Síðdegis: 16:31
Fjara
Árdegis: 10:23 • Síðdegis: 22:34
Knuth hóf að skrifa bækurnar árið 1963 og setti strax fram áætlun um að þær yrðu í sjö bindum. Knuth þykir mjög nákvæmur og er hann haldinn mikilli fullkomnunaráráttu sem gerði það að verkum að fyrsta bindið kom ekki út fyrr en árið 1968, annað bindið kom út árið eftir og það þriðja árið 1973. Þegar hér var komið við sögu fannst Knuth framsetningin á bókunum ekki nógu góð og vildi gera eitthvað í því. Bækurnar innihalda mikið af stærðfræðiformúlum og það var erfitt að gera prentsmiðjunni það skiljanlegt nákvæmlega hvernig hann vildi að formúlurnar litu út. Hann ákvað því að hanna sitt eigið forrit til þess að setja upp texta og stærðfræðiformúlur þannig að útkoman yrði falleg. Umbrotsforritið sem Knuth hannaði (eftir átta ára vinnu!) heitir TeX (síðasti samhljóðinn er borinn fram eins og sá síðasti í Bach) og í dag er það nær allsráðandi í tölvunarfræði, stærðfræði, eðlisfræði og flestum greinum verkfræði. Allar fræðilegar tímaritsgreinar og mjög margar bækur á þessum sviðum eru skrifaðar í TeX. Við upphaflega hönnun TeX dró Knuth fram ýmis áhugaverð verkefni sem þurfti að leysa til að setja upp texta. Sem dæmi má nefna hvernig skipta á orðum milli lína þannig að línurnar verði sem jafnastar. Knuth hannaði síðan reiknirit fyrir þessi verkefni og lýsti þeim á sinn skýra og greinargóða hátt. Hann forritaði fyrstu útgáfuna af TeX sjálfur og gaf forritið síðan út sem bók. Bókin er um 600 blaðsíður og er mjög læsileg.
Á undanförnum árum hefur Donald Knuth að mestu helgað sig ritun bókanna Listin að forrita. Hann hefur endurútgefið fyrstu þrjú bindin (1997-1998), auk þess að vinna að fjórða bindinu. Fyrsti hluti fjórða bindisins kom út árið 2010 og er áætlað að fleiri hlutar þess bindis komi út á næstu árum. Knuth áætlar að fimmta bindið komi út árið 2020!
Sem dæmi um fjölbreytt áhugamál Knuths þá skrifaði hann árið 1984 grein í eitt virtasta stærðfræðitímarit Bandaríkjana um hið svokallaða salernispappírsvandamál (e. The Toilet Paper Problem). Á tilteknu salerni eru ávallt tvær rúllur af salernispappír og notandi getur valið af hvorri rúllunni hann tekur pappírinn sem hann þarf að nota. Knuth gefur sér að til séu tvær tegundir notenda, þeir sem velja alltaf af stærri rúllunni og þeir sem velja alltaf af þeirri minni. Í stuttu máli felst vandamálið í að áætla hversu mikið af salernispappír er eftir á annarri rúllunni þegar hin er orðin tóm. Þetta fer að sjálfsögðu eftir því hvor tegundin af notendunum er algengari. Knuth leiðir út, með mjög flottri stærðfræði, formúlu fyrir fjölda blaða á rúllunni sem eftir er, miðað við hlutfall notenda sem velur alltaf af stærri rúllunni. Í lok greinarinnar þakkar Knuth arkitektum tölvunarfræðibyggingarinnar í Stanford fyrir að hafa óvart stungið upp á þessu áhugaverða verkefni!
Þessi grein um salernispappírsvandamálið er gott dæmi um húmorinn sem Knuth er þekktur fyrir. Hann hefur oft laumað bröndurum inn í bækur sínar, sérstaklega í atriðaorðaskránni. Til dæmis kom nafn Bo Derek fyrir í atriðaorðaskrá einnar bókar hans með tilvísunum í blaðsíður sem innihéldu töluna 10. Enn er eitthvað um slíkt spaug í bókum hans sem lesendur hafa ekki uppgötvað. Einnig má nefna að útgáfunúmer á TeX fylgja tölunni pí. Þannig var til útgáfa 3, síðan 3.1, svo 3.14 og svo framvegis. Núverandi útgáfa af TeX er útgáfa 3.1415926, sem er átta stafa nálgun á pí.
Þó Donald Knuth sé orðinn 73 ára er hann enn í fullu fjöri og vinnur hörðum höndum við bækur sínar. Tölvunarfræðingar heimsins vona að honum endist aldur og heilsa til að ljúka sem mestu af því verki sem hann hefur sett sér.
Heimildir og annað ítarefni: