Otvety na vse voprosy26.03.2002 15:49 | Astronet
- Ot redakcii.
Nesmotrya na to, chto Donal'd Knut ne yavlyaetsya astronomom, my reshili opublikovat' etot perevod, poskol'ku vklad sozdannoi im sistemy verstki tekstov
v razvitie astronomii neocenim.
TeX yavlyaetsya osnovnym
formatom predstavleniya statei, prinimaemyh vedushimi mirovymi astronomicheskimi
zhurnalami. TeX ispol'zuetsya i na astronete dlya verstki statei, blagodarya
chemu my imeem vozmozhnost' publikovat' stat'i s lyubymi slozhnymi formulami.
Po obrazovaniyu matematik, Donal'd Knut poluchil izvestnost' svoimi
issledovaniyami po informatike, osobenno po teorii algoritmov. On
yavlyaetsya avtorom mnogih knig (spisok ego trudov v MathSciNet
soderzhit
160 nazvanii), sredi kotoryh trehtomnoe "Iskusstvo programmirovaniya"[1],
za kotoroe v 1986 g. on poluchil nagradu Amerikanskogo Matematicheskogo
Obshestva. V sootvetstvuyushem zayavlenii govoritsya, chto dannaya kniga
"vnesla bol'shii vklad v prepodavanie matematiki nyneshnemu
pokoleniyu studentov, chem lyubaya matematicheskaya kniga, vyshedshaya v poslednie desyatiletiya".
Dolgozhdannyi chetvertyi tom nahoditsya v
stadii podgotovki i nekotorye ego chasti dostupny na veb-stranice
Knuta http://www-cs-faculty.stanford.edu/~knuth.
Knut - sozdatel' yazykov dlya podgotovki tekstov TeX i METAFONT, kotorye proizveli perevorot v napisanii i rasprostranenii tehnicheskoi literatury vo mnogih otraslyah, vklyuchaya i matematiku. V 1974 g. on prochel v Amerikanskom Matematicheskom Obshestve Gibbsovskuyu lekciyu, kotoruyu nazval "Podgotovka matematicheskih tekstov". Vposledstvii ona byla opublikovana v Byulletene Amerikanskogo Matematicheskogo Obshestva.[2]
Knut poluchil diplom po matematike v 1963 g. v Kaltehe pod rukovodstvom
Marshalla Holla. V 1974 g. on byl nagrazhden Premiei T'yuringa Associacii
Komp'yuternoi Tehniki. Sredi ego nagrad -
Nacional'naya Nauchnaya Medal' SShA (National Medal of Science, 1979),
medal' Adel'skolda Shvedskoi Korolevskoi akademii nauk(1994),
premiya Harvi Tehniona (Izrail', 1995),
medal' Dzhona fon Neimana ot IEEE (1995) i
premiya Kioto Fonda Inamori. S 1968 goda Knut rabotaet v Stenfordskom
Universitete, gde on v nastoyashee vremya imeet zvanie zasluzhennogo
professora Iskusstva Programmirovaniya.
Knut: V kazhdom kurse, prochitannom mnoi v Stenforde, poslednyaya lekciya byla posvyashena "otvetam na vse voprosy". Studenty ne byli obyazany na nei prisutstvovat', esli ne hoteli, no esli oni prihodili, oni mogli zadat' vopros na lyubuyu temu, krome religii, politiki i zavershayushego kurs ekzamena. Ya pozaimstvoval etu ideyu u Richarda Feinmana, kotoryi ispol'zoval ee pri chtenii svoih kursov v Kaltehe, i mne vsegda bylo interesno videt', chto zhe deistvitel'no interesuet studentov. Segodnya ya otvechu na lyuboi vopros na lyubuyu temu. Razreshim li my voprosy po religii ili politike? Ya ne znayu. No vas ne zhdet ekzamen, o kotorom stoilo by volnovat'sya. Ya postarayus' otvechat' kratko, chtoby my smogli razobrat' pobol'she voprosov.
Itak, kto hochet zadat' pervyi vopros? Esli voprosov net... (Knut delaet vid, chto sobiraetsya uhodit'.)
Vopros: Byl special'nyi doklad amerikanskomu prezidentu, doklad PITAC[3],
soderzhashii nekotorye rekomendacii. Menya interesuet, ne hoteli by vy
prokommentirovat' prioritety, sformulirovannye v etih rekomendaciyah:
bolee horoshaya razrabotka programm, sozdanie teraflopnogo komp'yutera,
sovershenstvovanie Interneta, vklyuchaya povyshenie bezopasnosti i
propusknoi sposobnosti, i social'no-ekonomicheskie aspekty regulirovaniya
informacii, nahodyasheisya v komp'yuternyh setyah.
Knut: Mne kazhetsya, chto eto ochen' horoshii nabor problem dlya doklada prezidentu... No na samom dele chto ya hotel by uvidet', tak eto dat' vozmozhnost' tysyacham specialistov po informatike delat' to, chto oni hotyat. Eto to, chto real'no prodvinulo by otrasl' vpered. Po svoemu opytu napisaniya "Iskusstva programmirovaniya"[1] znayu : esli by vy menya kazhdyi god sprashivali, chto iz proizoshedshego v informatike za etot god naibolee vazhno, ya, vozmozhno, ne smog by skazat' nichego, no za pyat' let otrasl' menyaetsya polnost'yu. Informatika - eto potryasayushee sotrudnichestvo lyudei so vsego mira, dobavlyayushih malen'kie kirpichiki v ogromnuyu stenu. Imenno eti otdel'nye kirpichiki, a ne epohal'nye sobytiya, i sostavlyayut sut' nashei raboty.
Sleduyushii vopros?
Vopros: Matematiki govoryat, chto u Boga est' "Kniga Dokazatel'stv", kuda
zapisyvayutsya naibolee krasivye dokazatel'stva. Mozhete li vy
nazvat' kakie-nibud' algoritmy, dostoinye "Knigi Algoritmov"?
Knut: Horoshii vopros. Ideyu o tom, chto u Boga est' kniga, v kotoroi zapisany luchshie matematicheskie dokazatel'stva, vyskazal Pol' Erdos, i, kazhetsya, moi drug Gyunter Cigler iz Berlina nedavno pisal ob etom[4].
Ya pomnyu, matematiki govorili mne v 60-e gody, chto oni priznayut informatiku vzrosloi naukoi, kogda v nei budet 1000 fundamental'nyh algoritmov. Ya dumayu, my uzhe dostigli poryadka 500. Nesomnenno, est' mnozhestvo algoritmov, kotorye, ya dumayu, mozhno schitat' sovershenno prekrasnymi i v nekotorom rode bessmertnymi. Dva primera - algoritm Evklida i sootvetstvuyushii, rabotayushii v binarnoi zapisi, vozmozhno, razrabotannyi v Kitae primerno togda zhe, kogda evklidov - v Grecii. V svoih knigah ya v osnovnom imeyu delo s klassicheskimi i uzhe davno sushestvuyushimi algoritmami, no tem ne menee kazhdyi god poyavlyayutsya novye idei, kotorye, ya dumayu, ostanutsya navsegda.
Vopros: Est' li u vas kakie-nibud' soobrazheniya po povodu kvantovyh vychislenii?
Knut: Da, no ya znayu pro nih ne ochen' mnogo. Eto paradigma, polnost'yu otlichnaya ot privychnoi mne. Ona imeet s nei mnogo obshego, no ona ochen' neprivychna v tom plane, chto vy poluchaete vse otvety v konce, a ne opredelyaete na kazhdom shage, chto delat' dal'she. Mnogoe iz etogo pokazano v fil'me "Run Lola Run", v kotorom syuzhet povtoryaetsya tri raza s tremya razlichnymi finalami. Kvantovye vychisleniya - nechto pohozhee: mir idet mnogimi putyami odnovremenno, i my vybiraem tot, gde rezul'tat luchshe.
Ya neploho razbirayus' v nekvantovyh vychisleniyah, poetomu, vpolne vozmozhno, esli kvantovye vychisleniya zavoyuyut sebe mesto pod solncem, ya budu ne v sostoyanii sdelat' nichego novogo. Ya posvyatil zhizn' komp'yuteram ne potomu, chto menya tak uzh interesuyut vychisleniya, a potomu, chto, kak okazalos', u menya eto neploho poluchaetsya. K schast'yu, to, chto ya delayu horosho, okazalos' interesno i drugim lyudyam. Moi sposobnosti dumat' ob algoritmah razvilis' ne potomu, chto ya hotel pomoch' lyudyam reshat' ih zadachi. Pochemu-to, kogda ya byl podrostkom, ya imel neobychnyi sklad uma, kotoryi sdelal menya neplohim programmistom. No ya ne sposoben tak zhe horosho razbirat'sya i v kvantovyh vychisleniyah, eto, mne kazhetsya, mir, otlichnyi ot moego.
Vopros iz zadnih ryadov ?
Vopros: Ya rabotayu v oblasti teorii dokazatel'stv, i odna iz naibolee
vazhnyh rabot tam - vasha stat'ya 1970 goda
"Zadachi s prostymi vyskazyvaniyami v obshih algebrah"
[5] , napisannaya vmeste s P. Bendiksom. U
menya dva voprosa. Vo-pervyh, prodolzhaete li vy sledit' za etoi
oblast'yu, i chto vy dumaete o ee sostoyanii? I vtoroi, kto takoi Bendiks
i kak slozhilas' ego dal'neishaya sud'ba?
Knut: Eta rabota byla opublikovana v 1970, no na samom dele ya sdelal ee v 1967, kogda byl v Kaltehe. Eto byla prostaya ideya, no, k schast'yu, ona okazalas' shiroko primenimoi. Ideya sostoit v tom, chtoby vzyat' nabor matematicheskih aksiom i poluchit' vse ih sledstviya. Esli u menya est' nabor aksiom, a u vas - vozmozhnaya teorema, vy sprashivaete, sleduet li ona iz etih aksiom. Ya nazval stat'yu "Zadachi s prostymi vyskazyvaniyami v obshei algebre", i skazal, chto zadacha yavlyaetsya "prostoi", esli moi metod s nei spravlyaetsya. Teper' etot metod znachitel'no rasshiren drugimi lyud'mi, i gorazdo bol'shee kolichestvo zadach "prosty". Ya dumayu, ih rabota zamechatel'na.
1967 byl dlya menya samym dramaticheskim godom. U menya ne bylo vremeni dlya issledovanii. U menya bylo dvoe detei mladshe 2-h let, ya byl naznachen lektorom v Associacii Komp'yuternoi Tehniki na tri nedeli, ya dolzhen byl chitat' lekcii na letnei shkole NATO v Kopengagene, ya dolzhen byl vystupat' na konferencii v Oksforde, i tak dalee. I ya zanimalsya korrekturoi "Iskusstva programmirovaniya", pervyi tom kotorogo vyshel v 1968. Vse eto vdobavok k tem obychnym kursam, kotorye ya chital togda, i k obostreniyu yazvy, iz-za kotorogo ya lozhilsya v bol'nicu, i redaktorstvu v dyuzhine zhurnalov. V tom godu ya rabotal nad dvumya malen'kimi ideyami. Odna stala izvestna kak algoritm Knuta-Bendiksa, drugaya izvestna kak atributivnye grammatiki[7]. Eto byl samyi produktivnyi god moei zhizni, no i, krome togo, samyi bespokoinyi.
Vy sprashivali pro Pitera Bendiksa. On byl studentom na odnom iz moih kaltehovskih kursov, "Vvedenii v algebru". Predpolagalos', chto kazhdyi student napishet kursovuyu rabotu, i Piter sdelal svoi otchet po voplosheniyu etogo algoritma. On byl fizikom. Shla V'etnamskaya voina, a on ne hotel v nei uchastvovat'. On uehal v Kanadu i pyat' let prorabotal shkol'nym uchitelem, a pozdnee poluchil diplom po fizike. Paru let nazad ya uznal, chto on zhivet vblizi Stenforda i pozvonil emu, i okazalos', chto on ves'ma neploho provel eti gody.
V 60-e, esli by ya pisal stat'yu so svoim rukovoditelem Marshallom Hollom, eto znachilo by, chto on pridumyvaet teoriyu, a ya zanimayus' programmirovaniem. No esli ya pisal sovmestno s kem-to eshe - ya delal teoriyu, a etot kto-to zanimalsya programmami. Pit Bendiks byl horoshim programmistom, kotoryi realizoval metod.
Vopros: Mne kazhetsya, chto proshe pererabotat' knigu, chem vnosit'
izmeneniya v ogromnye programmnye produkty, kotorye my vidim kazhdyi
den'. Kak mozhno primenit' teoriyu k usovershenstvovaniyu programmnogo
obespecheniya?
Knut: Nesomnenno, oshibki v programmah ispravlyat' gorazdo slozhnee, chem v knige. Na samom dele, moi glavnyi vyvod iz desyatiletnei raboty nad TEX-om sostoit v tom, chto pisat' programmy trudno. Eto gorazdo trudnee, chem vse ostal'noe, chem ya zanimalsya. Poka ya pisal TEX, ya ne mog zanimat'sya polnocennym prepodavaniem. Hotya ya lyublyu prepodavanie, ya byl vynuzhden na god ot nego otkazat'sya - slishkom mnogoe nado bylo derzhat' v golove odnovremenno. Pisat' knigu lish' nemnogim slozhnee, chem pisat' tehnicheskuyu stat'yu, no pisat' programmy gorazdo trudnee, chem knigu.
V svoih knigah ya predlagal voznagrazhdenie pervomu, kto naidet ocherednuyu oshibku v tekste, i ya dolzhen priznat', chto ya vypisal v Germaniyu chekov bol'she, chem kuda by to ni bylo. Ya poluchal pis'ma otovsyudu, no nemeckie chitateli okazalis' moimi luchshimi kritikami. Ya tochno tak zhe platil za oshibki v svoih programmah - TeX-e i METAFONT-e. Voznagrazhdeniya udvaivalis' kazhdyi god: ya nachinal s $2.56, potom $5.12, i tak dalee, do $327.68, kogda ya prekratil udvaivanie. V TEX-e i METAFONT-e ne nahodilos' oshibok s 1994 ili 1995 goda, hotya hodyat sluhi, chto kto-to nedavno nashel odnu. Ya planiruyu snova zanyat'sya etim cherez god ili dva. Ya delayu vse v "paketnom rezhime", kstati. Ya sobirayus' snova zanyat'sya vozmozhnymi oshibkami v TeX-e, skazhem, v 2003 godu.
Ya schitayu, chto davat' znat' pol'zovatelyam, chto ty privetstvuesh' soobsheniya ob oshibkah - edinstvennaya ser'eznaya metodika, kotoraya mozhet byt' ispol'zovana v industrii programmnogo obespecheniya. Po-moemu, Microsoft dolzhen byl by skazat': "Vy budete poluchat' chek ot Billa Geitsa za kazhduyu naidennuyu oshibku"
Vopros: Kakoe znachenie vy pridaete razrabotke effektivnyh algoritmov
i chto, po-vashemu, zhdet ee v budushem?
Knut: Ya schitayu, chto razrabotka effektivnyh algoritmov yavlyaetsya, v nekotorom rode, yadrom informatiki. Ona nahoditsya v centre polya nashei deyatel'nosti. Komp'yutery segodnya gorazdo bystree, chem ran'she, i poetomu dlya mnogih zadach net neobhodimosti zabotit'sya ob effektivnosti algoritmov. Ya mogu pisat' v kakom-to smysle ochen' neeffektivnye programmy, no esli oni vydayut otvet cherez sekundu - kogo eto volnuet? Tem ne menee, nekotorye veshi my dolzhny povtoryat' milliony ili milliardy raz, i prostogo znaniya konechnosti chisla povtorenii ne hvataet dlya polucheniya otveta. Poetomu chislo zadach, trebuyushih razrabotki effektivnyh algoritmov, po-prezhnemu veliko. Naprimer, mnogie zadachi yavlyayutsya NP-polnymi1, a etot klass yavlyaetsya daleko ne samym slozhnym. Poetomu ya vizhu prakticheski neogranichennye perspektivy dlya razrabotki effektivnyh algoritmov. I eto menya raduet, tak kak eto yavlyaetsya moim lyubimym delom.
Vopros: Vy ser'ezno interesuetes' golovolomkami, v tom chisle "Hanoiskoi bashnei" dlya chisla sterzhnei, bol'shem 3. Ya ne budu zadavat' bolee slozhnyi vopros - kakovo kratchaishee reshenie - tak kak ne uveren, chto vse znayut etu golovolomku. No ya hochu zadat' bolee filosofskii vopros - mozhno li pokazat', chto eta zadacha nerazreshima?
Knut: Znaet li auditoriya zadachu "Hanoiskoi bashni"? U vas est' 3 sterzhnya i nabor diskov raznogo razmera, i nado perelozhit' vse diski s odnogo sterzhnya na drugoi, prichem diski na sterzhnyah vsegda dolzhny byt' otsortirovany tak, chtoby bol'shii lezhal vnizu. Vy mozhete perekladyvat' po odnomu disku za raz. Genri Dudeni predlozhil obobshenie etoi zadachi da bol'shee kolichestvo sterzhnei, i vopros o kratchaishem reshenii dlya sluchaya 4 sterzhnei ostavalsya otkrytym bolee 100 let. Zadacha s 3 sterzhnyami ochen' prosta, my obuchaem pervokursnikov reshat' ee.
No voz'mem druguyu, bolee izvestnuyu zadachu - predpolozhenie Gol'dbaha:
kazhdoe chetnoe chislo mozhno predstavit' kak summu dvuh nechetnyh prostyh.
Ya schitayu, chto eta zadacha nikogda ne budet reshena. Ya dazhe dumayu, chto eta
zadacha mozhet ne imet' dokazatel'stva.
Ona mozhet byt' odnoi iz teh neproveryaemyh teorem,
kotorye, kak pokazal Gedel', dolzhny sushestvovat'. Na samom dele, seichas
my znaem, chto v kakom-to smysle pochti vse pravil'no postroennye
vyskazyvaniya o matematike neproveryaemy. Predpolozhenie Gol'dbaha, v
kakom-to smysle, pravil'no, potomu chto ne mozhet byt' lozhnym.
Sushestvuet tak mnogo sposobov predstavit' chetnoe chislo summoi dvuh nechetnyh,
chto s
rostom samogo chisla chislo ego predstavlenii stanovitsya vse bol'she i
bol'she. Voz'mite 
-znachnoe chetnoe chislo i predstav'te,
skol'kimi sposobami ego mozhno razlozhit' na summu dvuh nechetnyh. Dlya
-bitnogo nechetnogo chisla veroyatnost' okazat'sya prostym
proporcional'na 
.
Kakim obrazom vse eti pary nechetnyh chisel mogut byt' ne prostymi?
Etogo prosto ne mozhet byt'. No eto ne znachit, chto vy nashli
dokazatel'stvo, tak kak opredelenie prostoty mul'tiplikativno, togda
kak predpolozhenie Gol'dbaha otnositsya k additivnomu svoistvu. Poetomu
eto predpolozhenie prespokoino mozhet byt' vernym, no pri etom mozhet
ne sushestvovat' strogogo sposoba dokazat' eto.
Dlya sluchaya 4-sterzhnevoi "Hanoiskoi bashni" est' mnozhestvo sposobov dostich' togo, chto nam kazhetsya kratchaishim chislom hodov, no u nas net sposoba kak-to oharakterizovat' eti resheniya. Imenno poetomu ya dlya sebya reshil, chto nikogda ne smogu reshit' ee, i prekratil nad nei dumat' v 1972 godu. No v svoe vremya ya potratil celuyu nedelyu, vser'ez pytayas' ee reshit'.
Vopros: Kakovy seichas pyat' samyh vazhnyh zadach v informatike?
Knut: Ya ne lyublyu eti sostavleniya "luchshih desyatok". Eto desyat' naimenee mne nravyashihsya zadach. Ya dumayu, vy dolzhny by rabotat' nad malen'kimi veshami, kirpichikami, kotorye sostavlyayut stenu.
Vopros: Vy dolgoe vremya zanimalis' komp'yuternoi podgotovkoi tekstov. Kakovy vashi vpechatleniya ot rezul'tatov etoi raboty?
Knut: Ya ochen' schastliv, chto moya rabota byla v otkrytom dostupe i pozvolila lyudyam na vseh platformah obshat'sya drug s drugom cherez Internet. Ya osobenno obradovan neskol'kimi poslednimi proektami. Dve nedeli nazad ya slushal zamechatel'nuyu lekciyu Bernda Vegnera (Berndt Wegner) iz Berlinskogo Tehnicheskogo Universiteta o planah setevyh zhurnalov Evropeiskogo Matematicheskogo Obshestva. Eto bylo by prosto nemyslimo bez svobodno rasprostranyaemyh programmnyh produktov, vyrosshih iz moei raboty. Poetomu ya ochen' dovolen, chto ona sposobstvuet progressu nauki.
Ya schastliv videt' mnozhestvo horosho vyglyadyashih knig. Do nachala moei raboty matematicheskie knigi vyglyadeli vse huzhe i huzhe s kazhdym godom. Trebovalos' bol'shoe kolichestvo professional'noi ruchnoi raboty chtoby nabirat' teksty po-staromu, lyudi, kotorye eto umeli, postepenno umirali, i do matematicheskih knig ne dohodili ruki. Ya nikogda ne rasschityval, chto TEX ohvatit vsyu sferu podgotovki tekstov. Ya ne ochen' lyublyu sorevnovat'sya, i ya ne hotel lishat' raboty kogo-to, kto delaet eto po-drugomu. No ya obnaruzhil, chto nikto ne hotel vser'ez zanimat'sya matematicheskimi publikaciyami, i matematika byla tem, chto ya mog uluchshit', ne boyas', chto kto-to poschitaet menya vyskochkoi.
Oborotnoi storonoi stalo to, chto ya teper' slishkom vzyskatelen. Ya ne mogu poiti v restoran i zakazat' edy - ya nachinayu rassmatrivat' shrift v menyu. Cherez pyat' minut ya osoznayu, chto menyu eshe soderzhit informaciyu o blyudah. Esli by ya nikogda ne dumal o komp'yuternoi podgotovke publikacii, ya mog by prozhit' v chem-to bolee schastlivuyu zhizn'.
Vopros: Ne mogli by vy obrisovat' perspektivy informatiki, vehi ee razvitiya na sleduyushie desyat' - dvadcat' let?
Knut: Vy opyat' sprashivaete o vehah. Est' bol'shoi interes k prilozheniyam v biologii, tak kak v etoi oblasti v poslednee vremya bylo mnogo chego otkryto i sushestvuyut shansy pobedit' bolezni. Tot fakt, chto sushestvovanie cheloveka osnovan na diskretnom kode, oznachaet chto lyudi vrode vas i menya, horosho razbirayushihsya v diskretnyh zadachah, sposobny sdelat' v etoi oblasti chto-to stoyashee. Eti zadachi ochen' slozhny i mnogoobeshayushi, poetomu ya predvizhu zdes' horoshee budushee.
No, na samom dele, ya ne zamechayu zamedlenii i vo vsei nashei oblasti. Kazhdyi raz, dumaya, chto ya otkryl nechto stoyashee, ya smotryu v Internete i vizhu, chto kto-to eshe uzhe sdelal eto. Nasha oblast' do sih por pohozha na kipyashii chainik, na kotoryi nel'zya nadet' kryshku.
Naschet biologii, ya dumayu, my mozhem uverenno predskazat', chto tam budut ser'eznye zadachi eshe kak minimum let 500. Ya ne mogu skazat' togo zhe pro informatiku.
Vopros: Kakova svyaz' mezhdu matematikoi i programmirovaniem kak iskusstvom?
Knut: Po-nemecki iskusstvo - eto Kunst. Amerikanskii fil'm "Iskusstvennyi intellekt" - sootvetstvenno Kunctlicher Intelligenz, odnovremenno "iskusstvennyi" i "hudozhestvennyi". Ya dumayu o programmirovanii s oglyadkoi na krasotu kak o chem-to izyashnom, chem-to, chem vy mozhete gordit'sya, esli sumeli ih soedinit'. Matematika tochno tak zhe izyashna. Obe nauki, informatika i matematika, otlichny ot drugih svoei iskusstvennost'yu, ih net v prirode. Oni polnost'yu v nashei vlasti. My vydvigaem aksiomy, i kogda my reshaem zadachu, my mozhem dokazat', chto deistvitel'no reshili ee. Ni odin astronom nikogda ne budet znat', verny li ego teorii. Vy ne mozhete sletat' i pomerit' solnce.
Eto pervoe, chto prihodit v golovu pro etu svyaz'. No est' i razlichiya mezhdu matematikoi i programmirovaniem, i inogda ya mogu razlichit' kogda odevayu odnu shlyapu ili druguyu. Kakaya-to chast' menya lyubit matematiku, a kakaya-to - programmirovanie v emacs. Oni prekrasno uzhivayutsya, no ya ne schitayu, chto eto edinaya paradigma.
Vopros: Kakova svyaz' mezhdu Bogom i komp'yuterami?
Knut: V odnoi iz svoih knig, "Osveshenie bibleiskih tekstov, stihi 3:16"[6] ya ispol'zoval sluchainyi vybor dlya izucheniya shestidesyati razlichnyh stihov Biblii i togo, chto lyudi razlichnyh ispovedanii, zhivshie v raznoe vremya govorili o nih. Iznachal'no ya provel eto issledovanie dlya sebya, a potom obnaruzhil, chto eto dostatochno interesno, i mne sledovalo by napisat' ob etom knigu. Shest'desyat luchshih hudozhnikov, mnogie iz kotoryh nemcy, po moei pros'be proillyustrirovali ee. Eti raboty dvazhdy vystavlyalis' v Germanii, a takzhe v drugih stranah. Krome togo, oni vystavlyalis' v Nacional'nom Sobore v Vashingtone. V knige ya ispol'zoval metodologiyu, kotoraya primenyaetsya v informatike dlya analiza slozhnyh struktur, chtoby proverit', ne pomozhet li on nashemu ponimaniyu Biblii, kotoraya, estestvenno, yavlyaetsya takoi slozhnoi strukturoi. V knige ya ne dayu otvetov, ya prosto govoryu, kak zdorovo po moemu mneniyu to, chto zhizn' ostaetsya nepreryvnym issledovaniem. Zdes' sam put' bolee vazhen, chem ego konechnaya cel'.
Vopros: Znaete li vy, "P=NP"2uzhe dokazano? Hodyat sluhi, chto eto tak.
Knut: Chto imenno vy slyshali?
Vopros: Chto-to iz Rossii.
Knut: Iz Rossii? Eto novost' dlya menya. Ya ne dumayu, chto kto-to uzhe dokazal eto. No, ya znayu, Endi Yao (Andy Yao) nadeetsya reshit' etu zadachu v blizhaishie pyat'-desyat' let. On vdohnovlen Endryu Uailsom (Andrew Wiles), posvyativshim sem' let dokazatel'stvu Poslednei Teoremy Ferma. Oni oba iz Prinstona. Esli kto i sposoben sdelat' eto, to eto Endi.
Tri ili chetyre goda nazad poyavilas' stat'ya v kitaiskom zhurnale, v kotoroi odin professor zayavlyal chto sposoben reshit' NP-slozhnuyu zadachu3 za polinomial'noe vremya. On rassmatrival zadachu o klikah4, i ispol'zoval ochen' hitryi sposob ih predstavleniya. Metod predpolozhitel'no rabotal za polinomial'noe vremya, no real'no treboval chto-to poryadka n12 shagov, tak chto bylo nevozmozhno ego proverit' uzhe pri n=5. Poetomu bylo ochen' slozhno iskat' oshibki v ego dokazatel'stve. Ya poehal v Stenford i zasel za nego s nashimi diplomnikami, i nam potrebovalas' para chasov, chtoby naiti oshibku. Ya napisal avtoru pis'mo ob etom, i eshe cherez paru mesyacev on otvetil, chto "net, net, tam net oshibki". Ya reshil bol'she s etim ne svyazyvat'sya. Ya sdelal svoyu chast' raboty. No ya ne veryu, chto eta zadacha reshena. Eto samaya slozhnaya zadacha iz stoyashih segodnya pered sovremennoi teoreticheskoi informatikoi, a vozmozhno, i vsei sovremennoi naukoi.
Vopros: Chto vy dumaete o kriptograficheskih algoritmah? I o nyneshnih popytkah politikov ogranichit' issledovaniya v etoi obrasti?
Knut: Nesomnenno, vse kriptograficheskie issledovaniya ostavalis' odnoi iz samyh aktivnyh oblastei informatiki na protyazhenii poslednih desyati let, i mnogie rezul'taty zamechatel'ny i prekrasny. Ne mogu skazat', chto horosho vo vsem etom razbirayus', odnako. No klyuchevoi vopros zdes' - o zloupotrebleniyah vozmozhnostyami zashishennoi svyazi. Ya ne hochu, chtoby prestupniki ispol'zovali ee v svoih prestupnyh celyah.
Ya veruyushii chelovek, i ya znayu, chto Bog v kurse vseh moih sekretov, i potomu ya vsegda chuvstvuyu, chto moi mysli v nekotorom smysle izvestny vsem. Iz etogo ya i ishozhu. Ya ne schitayu, chto dolzhen skryvat' vse, chto ya delayu. S drugoi storony, ya, estestvenno, otnoshus' sovershenno po-drugomu k tomu, chto kto-to mozhet ispol'zovat' etu otkrytost' protiv menya, naprimer, vospol'zovavshis' moimi bankovskimi schetami. Poetomu ya za vysokii uroven' sekretnosti. No dolzhno li byt' nevozmozhnym dlya vlastei rasshifrovat' informaciyu dazhe pri ugolovnyh rassledovaniyah, v krainih sluchayah - tut ya sklonyayus' k tomu, chto v nekotoryh situaciyah dolzhny vse-taki byt' metody raskodirovaniya nekotoryh shifrov.
Vopros: Budut li u nas razumnye mashiny kogda-nibud' v budushem? I dolzhny
li oni byt'?
Knut: Ocenki, kogda zhe imenno u nas poyavyatsya dumayushie mashiny, vsegda byli neskol'ko preuvelicheny. Ya do sih por ne vizhu priznakov resheniya central'noi problemy - chto est' znanie, chto znachit dumat'. Nevropatologi sposobny provodit' izmereniya tochnee, chem kogda by to ni bylo, no my do sih por tak daleki ot otveta, chto ya dazhe ne mogu nazvat' nevrologiyu odnoi iz naibolee aktivnyh otraslei. Biologiya poluchaet otvety - DNK, stvolovye kletki i tak dalee. No naschet znaniya - my do sih por ih ishem.
V poslednie god ili dva vyshli navodyashie na razmyshleniya knigi, odna, napisannaya Hansom Moravekom (Hans Moravec)[10], i eshe odna - Reem Kazvellom (Ray Kuzwell)[9]. Obe utverzhdayut, chto cherez dvadcat' ili tridcat' let u nas budut mashiny, bolee umnye, chem chelovek. Nekotoryh lyudei eto pugaet. Po moemu mneniyu, esli deistvitel'no tak budet - flag im v ruki. Chto s togo, chto oni budut umnee nas? My smozhem uchit'sya u nih. No ya ne vizhu kakih-libo proryvov v dannom voprose.
Dve nedeli nazad v Grecii ya byl na predstavlenii knigi Kristosa Papadimitru (Cristos Papadimitrou), predsedatelya komp'yuternogo obshestva v Berkli. On opublikoval po-grecheski roman "Ulybka T'yuringa"[8]. Ne hochu pereskazyvat' syuzhet, no kogda on budet pereveden na nemeckii ili angliiskii, vy naidete tam ochen' horoshee obsuzhdenie iskusstvennogo intellekta i testa T'yuringa.
Samaya mnogoobeshayushaya model' togo, kak mozg myslit, iz vidennyh mnoi govorit, chto mozg - eto dinamicheskii geneticheskii algoritm, kotoryi rabotaet nepreryvno. Poka ya razgovarivayu s vami, u vas v mozgu sorevnuetsya mnozhestvo teorii po povodu togo, chto zhe ya hochu skazat'. Eto vyzhivanie naibolee podhodyashego, nepreryvnaya bor'ba konkuriruyushih teorii. Nekotorye okazyvayutsya na poverhnosti i na samom dele popadayut v vashe soznanie, no vse ostal'nye takzhe prisutstvuyut. U nas v golove mozhet nepreryvno idti chto-to vrode vzrosleniya idei. Eta model' daet, pohozhe, pravil'noe ob'yasnenie togo, kak my delaem to, chto delaem, pri otnositel'no medlennoi reakcii nashih neironov. No ya, konechno, ne specialist v etoi oblasti.
Vopros: Chto vy dumaete o patentah na programmnoe obespechenie? Seichas v Evrope idet bol'shaya diskussiya na etu temu.
Knut: Ya protiv patentovaniya togo, chto kazhdyi student vpolne mozhet otkryt'. V SShA i tak zapatentovano ogromnoe kolichestvo trivial'nyh veshei, i eto menya sil'no bespokoit. Est' organizaciya, kotoraya uzhe mnogo let zanimaetsya tem, chto patentuet ostavshiesya trivial'nye idei, chtoby oni byli dostupny kazhdomu. To, kak razvivaetsya patentovanie, grozit polnost'yu ostanovit' komp'yuternuyu industriyu.
Algoritmy - sugubo matematicheskie veshi, kotorye tochno tak zhe ne dolzhny
patentovat'sya, kak znachenie chisla 
.
No v otnoshenii chego-nibud'
netrivial'nogo, napodobie metoda vnutrennei tochki (interior point method)
v lineinom programmirovanii, gorazdo bol'she opravdanii tomu, kto
poluchaet prava na licenzirovanie metoda na korotkoe vremya, vmesto togo,
chtoby ob'yavlyat' ego kommercheskoi tainoi. V etom - vsya ideya patentovaniya,
samo slovo "patent" oznachaet "sdelat' dostupnym".
Ya vospityvalsya na matematicheskoi kul'ture, poetomu ya ne privyk trebovat' s lyudei den'gi kazhdyi raz, kogda oni ispol'zuyut dokazannuyu mnoi teoremu. No ya vystavlyayu schet za to vremya, kotoroe potratil, ob'yasnyaya im, kakuyu imenno teoremu im ispol'zovat'. Vpolne opravdanno poluchat' den'gi za uslugi, nastroiku i usovershenstvovanie, no ne ob'yavlyat' sam algoritm svoei sobstvennost'yu.
No tut est' odin interesnyi vopros. Mozhete li vy, skazhem, zapatentovat' polozhitel'noe chislo? Vpolne vozmozhno, chto esli my voz'mem million samyh bystryh segodnyashnih superkomp'yuterov i oni poschitayut nam trehsotznachnuyu konstantu, kotoraya mogla by byt' ispol'zovana dlya resheniya lyuboi NP-slozhnoi zadachi kakim-nibud' hitrym deistviem nad etim chislom. Nahozhdenie etogo chisla potrebovalo by ogromnogo vychislitel'nogo vremeni, i, opredeliv ego, vy smogli by sdelat' mnogo poleznogo. Tak deistvitel'no li eto chislo budet otkryto chelovekom? Ili eto nechto dannoe nam Bogom? Kogda my nachinaem dumat' nad slozhnymi problemami, prihoditsya menyat' tochku zreniya na to, chto sushestvuet v prirode, a chto - izobreteno nami.
Vopros: Vy vypisyvali cheki lyudyam, nashedshim oshibki v vashih knigah. Ya ne slyshal, chtoby hot' odin pred'yavil etot chek k oplate. Znaete li vy, kakuyu summu poteryaete, esli kazhdyi iz nih reshit poluchit' svoi den'gi?
Knut: Est' odin chelovek, zhivushii pod Frankfurtom, kotoryi, vozmozhno, poluchil by bol'she tysyachi dollarov. Eshe odin, iz Los-Gatosa, Kaliforniya, kotorogo ya nikogda ne vstrechal, obnalichivaet chek na $2.56 primerno raz v mesyac, i tak uzhe neskol'ko let. Vsego ya vypisal bolee dvuh tysyach chekov za eti gody, v srednem chut' bol'she $8.00 na kazhdyi. I dazhe esli kazhdyi obnalichit eti cheki, bolee cenno dlya menya to, chto moi knigi stanovyatsya luchshe.
Perevod S.V. Karpova
Literatura
1 The Art of Computer Programming ,by Donald E. Knuth. Russkii perevod etogo trehtomnika "Iskusstvo programmirovaniya" pereizdavalsya poslednii raz v 2000 g.
Volume 1:Fundamental Algorithms (third edition,Addison-Wesley,1997).
Volume 2:Seminumerical Algorithms (third edition,Addison-Wesley, 1997).
Volume 3:Sorting and Searching (second edition, Addison-Wesley, 1998).
Volume 4:Combinatorial Algorithms (in preparation).
2 Mathematical typography,by Donald E.Knuth.Bull. Amer.Math.Soc.(N.S.)1 (1979),no.2,337 372. Reprinted in Digital Typography (Stanford,California:CSLI Publications,1998),pp.19 65.
3 President's information technology advisory committee. See http://www.itrd.gov/ac/.
4 Proofs from The Book, by Martin Aigner and Gunter Ziegler. Second edition, Springer Verlag, 2001.
5 Simple word problems in universal algebras,by Peter B.Bendix and Donald Knuth.Computational Problems in Abstract Algebra ,J.Leech,ed.(Oxford: Pergamon,1970),pp.263 297.Reprinted in Automation of Reasoning ,Jorg H.Siekmann and Graham Wrightson,eds.(Springer,1983),pp.342 376.
6 3:16 Bible Texts Illuminated, by Donald E.Knuth. A-R Editions,Madison,Wisconsin,1990.
7 Semantics of context-free languages,by Donald E. Knuth.Mathematical Systems Theory 2 (1968), 127 145.See also The genesis of attribute grammars,in Lecture Notes in Computer Science 461 (1990),1 12.
8 TO XAMOGELO TOY TOYRINGK (The Smile of Turing), by Christos Papadimitriou.Livani Publishers, Athens,Greece,2001.
9 The Age of Spiritual Machines:When Computers Exceed Human Intelligence, by Ray Kurzweil.Penguin USA,2000.
10 Robot:Mere Machine to Transcendent Mind, by Hans P.Moravec. Oxford University Press, 2000.
Primechaniya perevodchika:
1 NP-polnye zadachi, klass naibolee slozhnyh zadach iz prinadlezhashih k NP, to est' razreshimyh za polinomial'noe vremya na nedeterminirovannoi mashine T'yuringa. Razreshimost' lyuboi iz NP-polnyh zadach na determinirovannoi mashine T'yuringa (to est' dokazatel'stvo ee prinadlezhnosti k klassu P) oznachaet razreshimost' lyuboi zadachi dannogo klassa, to est' ekvivalentnost' P=NP. Primery zadach etogo klassa - proverka vypolnimosti propozicional'nyh form, zadachi o maksimal'noi klike, kommivoyazhere i gamil'tonovom cikle. Podrobnee o problemah, svyazannyh so slozhnost'yu vychislitel'nyh zadach, mozhno prochitat' zdes'.2 Eto izvestnaya problema ekvivalentnosti klassov zadach, razreshimyh za polinomial'noe vremya s pomosh'yu sootvetstvenno determinirovannoi i nedeterminirovannoi mashin T'yuringa. Fakticheski, dokazatel'stvo etogo utverzhdeniya oznachalo by razreshimost' lyuboi NP-slozhnoi zadachi za polinomial'noe vremya.
3 NP-slozhnaya zadacha, razreshimaya s pomosh'yu nedeterminirovannoi mashiny T'yuringa. K dannomu klassu otnosyatsya, naprimer, izvestnye zadachi kommivoyazhera i zadacha o upakovke. NP-polnye zadachi yavlyayutsya podklassom dannogo.
4 Zadacha o naibol'shei klike (Maximum Clique Problem), NP-polnaya zadacha, v kotoroi trebuetsya naiti na karte naibol'shuyu gruppu gorodov, kazhdyi iz kotoryh napryamuyu soedinen dorogoi so vsemi gorodami etoi gruppy. Dlya ee resheniya v nastoyashee vremya neizvesten algoritm luchshe, chem pryamaya proverka vseh vozmozhnyh grupp.
|
Publikacii s klyuchevymi slovami:
personalii
Publikacii so slovami: personalii | |
Sm. takzhe:
Vse publikacii na tu zhe temu >> | |
