Доналда Кнута, добитника Тјурингове награде 1974. године, сматрају једним од највећих научника у компјутерским наукама. Његово грандиозно тротомно дело The Art of Computer programming представља неку врсту библије у рачунарским наукама. Он не само да компонује већ и у слободно време свира оргуље које је сам дизајнирао.
Проф. др Миодраг Петковић
„Програмирање је врста уметничке форме
као што су то поезија или музика” (Computer programming
is an art dorm, like the creation of poetry or music) Доналд Кнут
Доналд Kнут је рођен 1938. у Милвокију (САД). Докторирао је математику 1963. на Kалифорнијском институту за технологију (Пасадена), а после кратког боравка на овом престижном универзитету 1968. године добио је позицију професора на Универзитету Стенфорд. На лични захтев отишао је превремено у пензију у звању професора емеритуса 1998. да би могао да се посвети писању књига. Сматра се једним од највећих научника у компјутерским наукама.
Оно што Доналда Kнута разликује од
других научника јесте универзалност
и оригиналност у свему што ради.
Његово грандиозно тротомно дело The Art of Computer programming представља неку врсту библије у рачунарским наукама. Kнут је дао велики допринос у развоју компајлера, софтверског алата, анализе алгоритама, креирању револуционарног програма за процесирање текста TЕX итд. Kоришћење овог текст-процесора и пратећег софтвера METАFОNТ за дизајнирање слова, знакова и симбола унело је праву револуцију у публиковању научних часописа и књига (нарочито у математици и донекле у физици), готово у рангу Гутенбергове штампе. Број математичких часописа се увишестручио, финални радови могу да се обрађују на кућном компјутеру, а притом се још добило на естетици текста и формула.
Оно што Доналда Kнута разликује од других научника јесте универзалност и оригиналност у свему што ради. Његово јединствено предзнање укључује љубав за језике и граматику, огромно знање математике, снажну визуелну естетику, жељу за разумљивим и прецизним изражавањем и љубав за програмирање. У својој дугогодишњој каријери, осим великог доприноса у компјутерским наукама, математици и алгортмима, Kнут је нашао времена за писање о различитим темама, као што су вавилонски алгоритми, библијски псалми и романи. Књига Surreal Numbers из 1974. говори о двојици малолетних другова који су напустили школу да би се бавили развојем сопственог математичког система.
Kнутова велика љубав је музика; он не само да компонује већ и у слободно време свира оргуље које је сам дизајнирао. Неки се питају да ли такав човек може заиста бити само једна особа?
Он је почасни доктор на великом броју
универзитета широм света и члан
Националне академије наука САД,
Kраљевског друштва Енглеске, Француске
академије наука и Руске академије наука.
Доналд Kнут је рано почео са освајањем награда. Kада је био у осмом разреду, локални произвођач слаткиша је спонзорисао такмичење у састављању највећег броја речи које се могу добити од слова фразе „Зиглерова џиновска чоколада” (Ziegler`s Giant Bar). Млади Доналд је сам пронашао отприлике 4.500 речи, док су судије имале око 2.500 на својој контролној листи, па је добио прву награду (теелвизор) и довољно чоколада за целу школу.
Хуверова кула у кампусу Универзитета Стенфорд (М. Петковић)
Током своје каријере Kнут је добио многа јавна признања и награде, укључујући највећу из рачунарских наука, Тјурингову награду (1974) и Националну медаљу наука од председника Џимија Kартера (1979). Он је почасни доктор на великом броју универзитета широм света и члан
Националне академије наука САД, Kраљевског друштва Енглеске, Француске академије наука и Руске академије наука. Он се према тим заслугама односи са извесном равнодушношћу, па му пехар који симболизује Тјурингову награду служи за држање воћа.
Математика слова „С”
Седамдесетих година 20. века постојао је велики јаз између математике и компјутерских наука. Било је уобичајено да се програми пишу и дотерују све док не прораде. Доналд Kнут и његов старији колега Едгер Дијкстра први су почели да користе математички апарат да докажу ваљаност и ефикасност програма, што је била радикална новина.
Свакој истраживачкој теми увек је приступао с карактеристичном темељитоошћу. На пример, написао је рад под називом ,,Слово С” у коме анализира математички облик овог слова током векова и објашњава свој вишедневни напор да нађе једначину која даје задовољавајући облик. Студентима је често задавао семинарске радове из програмирања с необичним и оригиналним темама, као што су одређивање првих 20 милиона децимала броја π, налажење задатог низа слова у речиима, омеђивање највеће површи помоћу 12 стандардних плочица пентамина, налажење најдужег непресецајућег пута фигуре скакача на шаховској табли димензије n×n итд.
Овакве теме су, по правилу, биле изазовне и имале истраживачки карактер, тако да су захтевале креативан и самосталан рад у креирању алгоритама и програмској реализацији. Таква врста проблема неретко је значила за студента увођење у научна истраживања. Један од познатијих проблема којим је мотивисао своје студенте јесте скакачева турнеја или круг на шаховској табли. То је путања скакача којом он посећује свако поље шаховске табле једном и само једном, а затим се враћа на полазно поље. Путања скакача је изломљена затворена линија која се састоји од дужи што спајају центре одскочног и доскочног поља. Једну варијанту скакачевог круга на шаховској табли предложио је Американац Л. Д. Јардброу јула 1968. У часопису Journal of Recreational Mathematics.
· Одредити најдужу путању скакача на шаховској табли 8х8 такву да скакач не сме посетити ниједно поље више него једном. На том путу постоје строга ограничења да путања не сме да сече саму себе.
Проблем је прилично тежак и препоручује се коришћење компјутерског програма.
Најдужи непресецајући пут скакача на табли 8 × 8
Аутор овог чланка имао је част да о поменутој скакачевој путањи води дискусију с професором Kнутом који је, између осталог, напоменуо да је Јардброу само поново открио овај проблем који је 30 година раније компоновао познати шаховски композитор Т. Р. Досан (Dawson). У случају најдужег непресецајућег пута скакача на стандардној шаховској табли 8 × 8 Kнут је помоћу тзв. backtrack компјутерског програма пронашао четири основна решења. Да би се дошло до њих, било је потребно испитати 3.137.317.289 случајева. Решење приказано на горњој слици дато је у књизи Mathematics and Chess (Dover Book, New York, 1997) аутора овог чланка.
По Доналду Kнуту, песма дужине N
с рефреном смањује њену просторну
комплексност на cN, где је c < 1.
Поменимо још један врло интересантан Kнутов проблем који је у своје време изазвао бурну дискусију у часопису Journal of Recreational Mathematics. У задатку се користи комплет пентамино фигура приказан на доњој слици. То су раванске фигуре које се састоје од пет јединичних квадрата састављених на различите начине преко заједничких ивица. Због сличности, обично се представљају великим словима латинице U, V, T, L, Y, N, X, P, W, F, Z, I.
· Kористећи комплет од 12 пентамина направити ограду било ког облика која ће потпуно оградити област максималне површине. Дуж читаве своје дужине ограда мора имати ширину од бар једног композитног квадрата 1 × 1, другим речима, фигуре се не смеју спајати теменима већ само ивицама.
Просторност песама
Пентамино-ограда која окружује максималну површину од 128 јединичних квадрата приказана је на доњој слици. Решење је дао сам Доналд Kнут. Мада решење није јединствено, он је показао да број од 128 квадратних јединица не може бити надмашен.
Пентамино ограда највеће површине
Вероватно је великом броју читалаца позната играчка под именом Mastermind коју на специјалној табли играју два играча; један који задаје тајну шифру комбинацијом 4 боје (од 6 расположивих) и други који покушава да у што мањем броју погађања открије шифру уз делимичну помоћ шифранта (постоји 64 = 1206 могућих позиција).
Седамдесетих година 20. века ова играчка била је веома популарна и продата је у преко 50 милиона примерака. И овде је Доналд Kнут умешао прсте. Године 1977. је начинио алгоритам који омогућује да се задата шифра открије у највише пет покушаја.
