Projekti i shkrimit të librit u nis nga autori në . Fillimisht ishte planifikuar të dilte në një vëllim, por sasia e materialit doli të ishte aq e madhe sa numri i vëllimeve u rrit në shtatë. Tre vëllimet e para u botuan mjaft shpejt: vëllimi 1 në 1968, vëllimi 2 në 1969 dhe vëllimi 3 në 1973, pasuar nga një pushim deri në shkurt 2005, në të cilin autori botoi pjesën e parë të vëllimit të katërt. U vendos që pjesët e mbetura të vëllimit të katërt të botoheshin afërsisht dy herë në vit në numra të veçantë, pas së cilës do të botohej zyrtarisht i gjithë vëllimi i katërt. Numrat 0, 1, 2, 3 dhe 4 u botuan gjatë viteve 2005-2009, dhe në vitin 2011 doli vëllimi 4A, i cili përfshinte informacione nga këto çështje. Gjithashtu në vitin 2005 doli numri 1 "MMIX - Një kompjuter RISC për mijëvjeçarin e ri", informacion nga i cili do të përfshihet në botimin e ri, të katërt të vëllimit të parë. Numri 6 u botua në 2015 kënaqshmëria, që përfaqëson të tretën e mesme të vëllimit të ardhshëm 4B.

Meqenëse Knuth e kishte konsideruar gjithmonë Artin e Programimit si projektin kryesor të jetës së tij, ai doli në pension në vitin 1993 me synimin që të përqendrohej plotësisht në shkrimin e pjesëve që mungojnë dhe të rregullonte ato ekzistuese. Ai besonte se do të duheshin 20 vjet për të përfunduar punën.

YouTube enciklopedik

• 1 / 5

  Si një ekspert i njohur në dizajnin e përpiluesit, në vitin 1962 Knuth filloi të shkruante një libër mbi dizajnin e përpiluesit. Ai shpejt e kuptoi se qëllimi i materialit duhej të ishte shumë më i gjerë. Në qershor 1965, ai mbaroi së shkruari versionin e parë të asaj që fillimisht donte të botonte në një libër prej dymbëdhjetë seksionesh. Vëllimi i tekstit të shkruar me dorë ishte 3000 faqe. Sipas llogaritjeve të Knuth-it, ky vëllim duhet të kishte 600 faqe të shtypura, por, siç e informoi botuesi i tij, vëllim real do të ishin 2000 faqe. Në këtë drejtim, struktura e librit u rishikua në favor të disa vëllimeve, nga 1-2 seksione secili. Që atëherë, për shkak të rritjes së vazhdueshme të materialit, u vendos që vëllimi i katërt gjithashtu të ndahej në libra të veçantë: 4A, 4B, 4C dhe ndoshta 4D. Por edhe kjo ndarje, me sa duket, nuk do të jetë përfundimtare, pasi seksionet 7.1 dhe 7.2.1 tashmë zënë më shumë se 650 faqe në total.

  Në vitin 1976, Knuth prodhoi një botim të dytë të vëllimit të dytë, i cili kërkonte ritipe. Por dizajni tipografik (monotipi) i përdorur në botimin e parë nuk ishte më i disponueshëm në këtë pikë. Për të shmangur zhgënjimet e ngjashme në të ardhmen, në 1977 Knuth filloi të zhvillonte sistemin e tij tipografik. komplet kompjuterik. Sipas llogaritjeve të tij, puna duhet të kishte zgjatur jo më shumë se gjashtë muaj, por u deshën rreth dhjetë vjet para se të përfundonte. Sistemi u quajt TeX dhe aktualisht përdoret për shtypjen e të gjitha vëllimeve të Artit të Programimit. Për më tepër, më pas, TeX u bë standardi de fakto për të shkruar artikuj dhe monografi në shkencat natyrore.

  Ashtu si librat e tjerë të Knuth, Arti i Programimit shënohet me "emrin e tij të markës": për çdo gabim të gjetur në tekst, autori paguan një dollar heksadecimal, domethënë 2,56 dollarë (0x100 cent, në bazën 16). Një tjetër tipar dallues libri është një bollëk ushtrimesh për vetë-përmbushje, shkallë të ndryshme vështirësie, duke filluar nga enigma të thjeshta"për ngrohje" dhe mbarim çështje të hapura. Vështirësia e secilit ushtrim vlerësohet në një shkallë numerike nga 0 deri në 50. Pra, në botimet e hershme, numri 50 shënohej me  teoremën Fermën e Madhe, por në edicionin e tretë ky vlerësim u “zhvlerësua” në 45, pasi nga atë kohë prova e saj kishte pushuar së qeni një problem i hapur.

  Përmbledhje simbolet për vëllimin e tretë, 1978 "Renditja dhe kërkimi" (majtas - vlerësim, djathtas - shpjegim i shkurtër)

  • Trekëndëshi i Zi - Rekomandohet
  • M - Me një paragjykim matematikor
  • VM - Kërkon njohuri të "matematikës së lartë"
  • 00 - Kërkon një përgjigje të menjëhershme
  • 10 - E thjeshtë (për 1 minutë)
  • 20 - Vështirësi mesatare (për 15 minuta)
  • 30 - Rritja e vështirësisë
  • 40 - Për "matpraktikum"
  • 50 - Problem kërkimor

  Plani origjinal për shkrimin e librit sugjeronte ndarjen e mëposhtme të materialit.

  • Vëllimi 1. Algoritmet bazë.
    • Kapitulli 1. Konceptet bazë.
    • Kapitulli 2. Strukturat e informacionit.
  • Vëllimi 2. Algoritme të derivuara.
    • Kapitulli 3. Numrat e rastit.
    • Kapitulli 4. Aritmetika.
  • Vëllimi 3. Renditja dhe kërkimi.
    • Kapitulli 5. Renditja.
    • Kapitulli 6
  • Vëllimi 4. Algoritme kombinuese.
    • Kapitulli 7. Kërkimi kombinues.
    • Kapitulli 8. Rekursioni.
  • Vëllimi 5. Algoritmet sintaksore.
    • Kreu 9. Kërkimi leksikografik.
    • Kapitulli 10. Kërkimi sintaksor.
  • Vëllimi 6. Teoria e Gjuhëve.
  • Vëllimi 7. Përpiluesit.

  Në fakt, kjo skemë u zbatua deri në vëllimin e tretë.

  NË aktualisht botuar vëllimin 4A, i cili përmban seksionet e para të kapitullit 7. Seksionet e reja janë planifikuar të botohen fillimisht në numra të veçantë (afërsisht 128 faqe), afërsisht dy numra në vit (botimet 0, 1, 2, 3 dhe 4 u botuan në mënyrë të ngjashme përpara botimit të vëllimit 4A).

  Gjuha e shembullit të orientuar nga makina

  Programet e shembujve në libër përdorin një "montim MIX" të krijuar për të ekzekutuar në një kompjuter hipotetik MIX. Në edicionin e tretë, MIX i vjetëruar u zëvendësua nga MMIX, i cili ka një arkitekturë të plotë RISC. Ekziston një softuer që ofron emulim të makinës (M)MIX në kompjuterët standardë të pajtueshëm me IBM. Koleksioni GNU Compiler  ka aftësinë për të përpiluar kodin C/C++ për arkitekturën e synuar MMIX.

  Shumë lexues janë të shtyrë nga përdorimi i gjuhës nivel i ulët, por Knuth e konsideron zgjedhjen e tij të justifikuar, pasi lidhja me arkitekturën është e nevojshme për të qenë në gjendje të gjykojë me saktësi karakteristikat e algoritmit si shpejtësia, konsumi i memories, etj. Si rezultat i kësaj zgjedhjeje, megjithatë, audienca e synuar ngushtohet shumë. Për më tepër, qëllimi i aplikimit të tij si një "libër recetash" për programuesit praktikë, shumë prej të cilëve nuk e dinë gjuhën e asamblesë, dhe nëse e dinë, nuk kanë dëshirë të përkthen algoritme të nivelit të ulët nga libri në gjuhë, është gjithashtu. kufizuar. nivel të lartë. Shumë udhëzues praktike që paraqesin të njëjtin material në një mënyrë më popullore janë publikuar pikërisht për këtë arsye.

  Kritika

  Tipari kryesor i monografisë së Knuth-it, i cili e dallon atë në mënyrë të favorshme nga librat e tjerë të programimit, është shiriti jashtëzakonisht i lartë për cilësinë e materialit dhe prezantimin akademik, si dhe thellësia e analizës së çështjeve në shqyrtim. Falë kësaj, ai është bërë një bestseller i vërtetë dhe një libër referimi për çdo programues profesionist. Arti i Programimit u emërua nga American Scientist si një nga 12 monografitë më të mira fizike dhe matematikore të shekullit të 20-të, së bashku me Dirakun në mekanikën kuantike, Ajnshtajnin në relativitetin, Russell dhe Whitehead në themelet e matematikës dhe disa të tjerë.

  Kopertina e edicionit të tretë të vëllimit të parë të librit përmban një citim nga Bill Gates: “Nëse vërtet e konsideroni veten një programues i mirë…, lexoni Artin e Programimit (Knuth)… Nëse mund t'i lexoni të gjitha këto, duhet të më dërgoni patjetër CV-në tuaj.”.

  Botime

  Origjinale

  E treta (aktuale)

  Në rendin rritës të numrave të vëllimit:

  • Vëllimi 1: Algoritmet themelore. Botimi i tretë (Reading, Massachusetts: Addison-Wesley, 1997), xx+650pp. ISBN 0-201-89683-4
  • Vëllimi 1, Fasikulli 1: MMIX - Një kompjuter RISC për Mijëvjeçarin e Ri. (Addison-Wesley, 14 shkurt 2005) ISBN 0-201-85392-2 (do të jetë në botimin e katërt të vëllimit 1)
  • Vëllimi 2: Algoritme Seminumerike. Botimi i tretë (Reading, Massachusetts: Addison-Wesley, 1997), xiv+762pp. ISBN 0-201-89684-2
  • Vëllimi 3: Renditja dhe kërkimi. Botimi i dytë (Reading, Massachusetts: Addison-Wesley, 1998), xiv+780pp.+foldout. ISBN 0-201-89685-0
  • Vëllimi 4A: Algoritme Kombinuese, Pjesa 1(Upper Saddle River, New Jersey: Addison-Wesley, 2011), xvi+883pp. ISBN 0-201-03804-8
  • Vëllimi 4, Fashiku 6: Kënaqshmëria. (Addison-Wesley Professional, 2015), xiii+310pp. ISBN 978-0-13-439760-3

  E mëparshme

  Sipas datës së publikimit:

  • Vëllimi 1, botimi i parë, 1968. 634 f. ISBN 0-201-03801-3.
  • Vëllimi 2, botimi i parë, 1969, xi+624pp, ISBN 0-201-03802-1 .
  • Vëllimi 3, botimi i parë, 1973, xi+723pp+centerfold, ISBN 0-201-03803-X
  • Vëllimi 1, botimi i dytë, 1973, xiii+634pp, ISBN 0-201-03809-9.
  • Vëllimi 2, botimi i dytë, 1981, xiii+ 688 f. ISBN 0-201-03822-6.
  • Vëllimi 4, Fashiku 2: Gjenerimi i të Gjitha Tuples dhe Permutations, (Addison-Wesley, 14 shkurt 2005) v+127pp, ISBN 0-201-85393-0
  • Vëllimi 4, Fashiku 3: Gjenerimi i të gjitha kombinimeve dhe ndarjeve. (Addison-Wesley, 26 korrik 2005) vi+150pp, ISBN 0-201-85394-9
  • Vëllimi 4, Fashiku 4: Gjenerimi i të gjitha Pemëve - Historia e Gjenerimit Kombinator, (Addison-Wesley, 6 shkurt 2006) vi+120pp, ISBN 0-321-33570-8
  • Vëllimi 4, Fashiku 0: Hyrje në Algoritmet Kombinatore dhe Funksionet Boolean, (Addison-Wesley Professional, 28 prill 2008) vi+240pp, ISBN 0-321-53496-4
  • Vëllimi 4, Fashiku 1: Truket dhe teknikat bitwise; Diagramet e vendimeve binare(Addison-Wesley Professional, 27 mars 2009) viii+260pp,

  Në tregun global të literaturës kompjuterike, ka shumë libra të krijuar për të mësuar algoritmet bazë dhe të përdorur në programim. Ka mjaft prej tyre, dhe ata konkurrojnë me njëri-tjetrin në një masë të madhe. Megjithatë, midis tyre ka një libër të veçantë. Ky është një "Arti i Programimit" me tre vëllime nga D. E. Knuth, i cili dallohet nga të gjitha konkurrencat, është përfshirë në fondin e artë të letërsisë botërore për shkencën kompjuterike dhe është një libër referimi për pothuajse të gjithë ata që janë të lidhur me programimin.

  Si botues, ne e shohim vlerën e librit në atë se ai synon jo aq shumë për të mësuar teknikat e programimit, por për të mësuar, nëse është e mundur, "artin" e programimit, ofron shumë receta për përmirësimin e programeve dhe, më e rëndësishmja. , ju mëson se si t'i gjeni vetë këto receta.

  Nuk është sekret që programuesit tanë janë ndër specialistët më të kualifikuar në botë. Ata përfaqësojnë në mënyrë adekuate shkollën kombëtare të programimit dhe shkencave kompjuterike jashtë vendit, e cila ka dhënë një kontribut të rëndësishëm në formimin e bazave themelore të shkencës kompjuterike. Për të ruajtur këtë nivel dhe për të ecur përpara, është e nevojshme të botohen me kohë libra në rusisht që pasqyrojnë arritjet kryesore botërore në këtë fushë. Një libër i tillë është edhe “Arti i Programimit” me tre vëllime nga D. E. Knuth.

  Jemi krenarë që bibliotekat e programuesve, mësuesve, studentëve, nxënësve të shkollave të mesme dhe shumë të tjerë do të pasurohen me këtë libër klasik dhe se duke e bërë këtë do të kontribuojmë në një kuptim më të thellë të bazave të shkencës kompjuterike. Jemi thellësisht të bindur se libri "Arti i Programimit" i D. E. Knuth mund ta afrojë një person drejt përsosmërisë. Shpresojmë që botimi ynë rus i këtij libri të mrekullueshëm do të konfirmojë edhe një herë se vlerat e vërteta nuk vjetërohen me kalimin e viteve.

  - Victor Shtonda, Genadi Petrikovets, Alexey Orlovich, botues

  Rreth Artit të Programimit

  Çdo libër ka fatin e vet. Disa shfaqen në mënyrë të padukshme dhe po aq të padukshme zhduken në rrjedhën e kohës, të mbuluara me pluhur në raftet e bibliotekave. Të tjerët në periudhë të caktuar janë të kërkuara mes një rrethi të ngushtë specialistësh derisa të zëvendësohen me libra të rinj referimi. Të tjerë akoma, duke u ngritur mbi kohën, ushtrojnë një ndikim të fuqishëm në zhvillimin teknologjik të shoqërisë. Nuk ka aq shumë libra që hyjnë në kategorinë e fundit. Lirimi i tyre është gjithmonë festë. Vitet kalojnë, teknologjitë ndryshojnë, por gjeneratat e reja i rilexojnë faqet e tyre me interes të vazhdueshëm. Pikërisht librave të tillë i përket vepra shumëvëllimore e shkencëtarit të famshëm amerikan Donald Erwin Knuth "Arti i Programimit" i ofruar lexuesit.

  Kanë kaluar gati 30 vjet që nga botimi i parë në vitin 1972 në SHBA i këtij libri. Është përkthyer në shumicën e gjuhëve të botës, përfshirë rusishten. Deri më sot, në territorin e vendeve të CIS, libri me tre vëllime i D. E. Knuth është bërë një gjë e rrallë bibliografike. Në vitin 1998, në Shtetet e Bashkuara u botua edicioni i tretë i Artit të Programimit, i cili ruan sekuencën e prezantimit të materialit. versionet e mëparshme, por është zgjeruar ndjeshëm lista e referencave, e cila përfshin rezultatet më të fundit dhe më të rëndësishme, janë shtuar ushtrime dhe komente të reja dhe janë eliminuar pasaktësitë. Duke pasur parasysh popullaritetin mbarëbotëror të Artit të Programimit, duhet të prisnim një botim të ri të përkthyer në Rusisht, të cilin po e mbani në duar, për një kohë të gjatë.

  Cili është suksesi i "Arti i Programimit" nga D. E. Knuth?

  Së pari, ky libër është një libër i shkëlqyer për shkrimin dhe analizimin e algoritmeve kompjuterike. Seksionet e tij mund të përfshihen në shumë kurse universitare mbi teknologjitë e programimit, teorinë e algoritmeve dhe matematikën diskrete. Libri mund të studiohet edhe nga nxënës të shkollave të mesme që njohin bazat e programimit. Si gjuhë kryesore për shkrimin e algoritmeve, autori zgjodhi gjuhën e udhëzimeve të makinës të një hipotetike kompjuter universal PËRZIERJE. Kjo ju lejon të ndërtoni programe optimale, duke marrë parasysh karakteristikat e kompjuterëve. Transferimi i programeve MIX në kompjuterë të vërtetë ose rishkrimi i tyre në gjuhë të nivelit të lartë nuk është i vështirë. Logjika sesi funksionojnë programet shpjegohet pothuajse gjithmonë me grafikët e thjeshtë të rrjedhës.

  Së dyti, materiali i zgjedhur me kujdes i përfshirë në libër përfshin klasat kryesore themelore të algoritmeve, të cilat në një formë ose në një tjetër hasen më shpesh në praktikën e programimit.

  Së treti, një faktor i rëndësishëm në suksesin e librit të D. E. Knuth është prezantimi enciklopedik. Profesor Knuth ka një aftësi unike për të gjurmuar një problem nga sfondi historik i origjinës së tij deri në Shteti i artit. Referenca të shumta për veprat e mjeshtrave të vjetër (deri në kohën e antikitetit), të përfshira në konteksti bashkëkohor krijojnë te lexuesi një ndjenjë të veçantë përkatësie zhvillim historik idetë dhe metodat shkencore.

  Së katërti, duhet theksuar mjeshtëria e prezantimit. Libri është menduar për një gamë të gjerë lexuesish - nga studentët fillestarë deri te programuesit profesionistë. Të gjithë do të jenë të interesuar të mësojnë algoritme kompjuterike në nivelin e tyre. Materiali është i mjaftueshëm. Për të kuptuar thelbin e metodave, nuk kërkohet njohja e seksioneve të veçanta të matematikës ose teknologjive speciale të programimit. Mund të gjurmohet një përbërje e caktuar "muzikore" e ndërtimit të komplotit (në shtëpi, D. E. Knuth ka një organ të vogël në të cilin luan).

  Lista e përbërësve për suksesin e Artit të Programimit mund të vazhdohet lehtësisht.

  Autori i këtyre rreshtave ndoqi kursin "Arti i Programimit" në prezantimin e profesor Knuth në vitet 1976-1977 gjatë një stazhi në Universitetin Stanford. Pastaj u formua baza algoritmike e teknologjive të programimit, në origjinën e së cilës qëndronte D. E. Knuth. Pati shumë diskutime, seminare, ide kreative.

  Libra të rëndësishëm janë gjithmonë të lidhur me fatin e autorit. Donald Erwin Knuth filloi punën në Artin e Programimit në 1962. Vazhdon edhe sot e kësaj dite. Ai ka shumë plane. Përpara vëllimeve të reja të "Arti i Programimit" që lexuesit mezi presin.

  - Profesor Anatoli Anisimov

  Nga redaktori i përkthimit

  Kanë kaluar rreth 25 vjet nga botimi i parë i Artit të Programimit nga D. E. Knuth. Gjithsesi, libri jo vetëm që nuk është vjetëruar, por mbetet ende udhërrëfyesi kryesor i artit të programimit, libër nga i cili mësohet të kuptosh thelbin dhe veçoritë e këtij arti.

  Me kalimin e viteve për gjuhe angleze tashmë janë botuar botimi i tretë i vëllimit 1 dhe 2, si dhe botimi i dytë i vëllimit të tretë. Autori ka bërë ndryshime dhe shtesa të rëndësishme në to. Mjafton të thuhet se numri i ushtrimeve është pothuajse dyfishuar dhe shumë nga ushtrimet e përfshira në botimet e mëparshme (sidomos përgjigjet e tyre) janë modifikuar. Shumë kapituj dhe seksione janë plotësuar dhe rishikuar ndjeshëm, janë korrigjuar pasaktësitë dhe gabimet tipografike, janë shtuar shumë referenca të reja në literaturë dhe janë përdorur rezultatet teorike të viteve të fundit.

  Kapitulli 3 është ndryshuar ndjeshëm, veçanërisht seksionet 3.5 dhe 3.6, si dhe seksionet 4.5.2, 4.7, 5.1.4, 5.3, 5.4.9, 6.2.2, 6.4, 6.5, etj.

  Natyrisht, lindi nevoja për një botim të ri të librit.

  Përkthimi është bërë sipas botimit të tretë të vëllimit 1 dhe 2 dhe botimit të dytë të vëllimit të tretë. Gjithashtu, janë marrë parasysh shtesat dhe korrigjimet e dhëna me dashamirësi nga autori.

  Gjatë përkthimit jemi përpjekur të ruajmë stilin e autorit, emërtimet dhe mënyrën e paraqitjes së materialit. Në shumicën e rasteve, termat e miratuar në literaturën shkencore në Rusisht janë përdorur. Ekuivalentët në anglisht janë cituar aty ku është e nevojshme. Për shumë arsye, veçanërisht për shkak të kompleksitetit të disa pjesëve, leximi i Artit të Programimit nuk është aspak i lehtë. Një nga arsyet që e vështirëson kuptimin e librit është mënyra se si e prezanton autori; pasi të mësoheni me të, mund ta bëni shumë më të lehtë leximin.

  Për shkak të bollëkut të materialit (shpesh pak të lidhur me njëri-tjetrin), është e pamundur të strukturohet libri në atë mënyrë që koncepte dhe përkufizime të ndryshme të futen menjëherë në përmendjen e parë të tyre. Prandaj, në kapitullin 1, konceptet mund të diskutohen pa referencë, përkufizimet rigoroze të të cilave janë dhënë në vëllimin e 3-të. Prandaj roli i indeksit lëndor është kaq i madh, pa të cilin kuptimi i librit do të ishte dukshëm i vështirë. Shpresojmë që lexuesi të mos habitet kur të gjejë referenca për kapitujt 7, 8 dhe kapitujt pasues që nuk përfshihen në tre vëllimet e propozuara. Së bashku me autorin, shpresojmë që ato të botohen shumë shpejt dhe, natyrisht, të shfaqen menjëherë në përkthim rusisht si vazhdimësi e këtij botimi.

  Duhet t'i kushtohet vëmendje edhe shënimit jo gjithmonë standard të përdorur nga autori. Përveç përkufizimeve, këto emërtime mund të shfaqen në vëllimin e parë dhe janë paraqitur në vëllimin e dytë. Prandaj, pa një indeks shënimesh, do të ishte jashtëzakonisht e vështirë të përdorej libri. Unë gjithashtu dua t'i kushtoj vëmendje shënimit [A], ku A është një deklaratë. Kjo hyrje gjendet në formula, dhe nganjëherë në tekst, dhe tregon një vlerë të barabartë me treguesin A.

  - Profesor Yu. V. Kozachenko

  PARATHËNIE

  Të nderuar lexues! Ju po mbani një libër

  të botojmë të cilat ju na kërkuat me mijëra letra. Na është dashur të kalojmë vite duke kontrolluar dhe ri-kontrolluar me kujdes një numër të pafund recetash dhe të zgjedhim për ju më të mirat, më interesantet, më të përsosurat.

  Tani, pa asnjë dyshim, mund të themi se nëse ndiqni udhëzimet, atëherë çdo pjatë do të dalë njësoj si për ne, edhe nëse nuk keni gatuar kurrë më parë.
  - The McCall Cookbook (1963)

  Procesi i përgatitjes së programeve për një kompjuter dixhital është një aktivitet shumë emocionues. Dhe çështja nuk është vetëm se justifikon veten nga pikëpamja ekonomike dhe shkencore; mund të ngjallë edhe ndjenja estetike, tema të ngjashme të cilët përjetojnë personalitet krijues kur shkruajnë muzikë ose poezi. Po mbani në duar vëllimin e parë të një botimi me shumë vëllime, qëllimi i të cilit është t'i japë lexuesit një shumëllojshmëri njohurish dhe aftësish që përbëjnë zanatin e programuesit.

  Kapitujt e mëposhtëm nuk janë një hyrje në programimin kompjuterik; supozohet se ju tashmë keni një përvojë në këtë fushë. Në fakt, kërkesat për lexuesin janë shumë të thjeshta; megjithatë, një programuesi fillestar do t'i duhet kohë dhe praktikë për të kuptuar se çfarë është kompjuter dixhital. Pra, lexuesi duhet të ketë:

  a) njëfarë kuptimi se si funksionon një kompjuter dixhital me një program të ruajtur; në të njëjtën kohë, nuk është e nevojshme të kuptohet elektronika, gjëja kryesore është të kuptojmë se si komandat mund të ruhen në kujtesën e kompjuterit dhe më pas të ekzekutohen në mënyrë sekuenciale;

  b) aftësia për të shprehur problemin në terma të qartë dhe të përcaktuar, të kuptueshme për kompjuterin(kompjuterët nuk kanë inteligjencë njerëzore, ndaj bëjnë pikërisht atë që u thuhet, as më shumë e as më pak; ky është zakonisht fakti më i vështirë për t'u kuptuar nga përdoruesit fillestarë);

  c) njohuri për më të thjeshtat metodat kompjuterike, si organizimi i cikleve (ekzekutimi i përsëritur i një grupi të caktuar komandash), si dhe përdorimi i nënprogrameve dhe variablave me indekse;

  d) njohja e përbashkët termat kompjuterik, për shembull "memorie", "regjistrat", "bit", "pikë lundruese", "mbushje", "softuer"; shumica e termave që nuk përcaktohen në tekst shpjegohen në një indeks alfabetik në fund të çdo vëllimi.

  Këto katër kushte ndoshta mund të kombinohen në një kërkesë: lexuesi duhet të ketë përvojë në shkrimin dhe korrigjimin e të paktën katër programeve për të paktën një kompjuter.

  Jam përpjekur t'i shkruaj këto libra në atë mënyrë që të mund të shërbejnë për qëllime të ndryshme. Së pari, ato janë një udhëzues referimi që bashkon njohuri nga disa fusha të rëndësishme të shkencës. Së dyti, ato mund të përdoren si mjete ndihmëse për vetë-edukim dhe tekste programimi ose shkenca kompjuterike për universitetet. Për këtë arsye kam përfshirë nje numer i madh i ushtrime dhe u dha përgjigje shumicës së tyre. Gjithashtu, u përpoqa të përqendrohesha në fakte, në vend që të "derdh ujë" dhe të merrem me arsyetime të përgjithshme.

  Ky libër me tre vëllime është i destinuar për të gjithë ata që janë seriozisht të interesuar për kompjuterët, dhe jo vetëm për profesionistët. Në fakt, një nga qëllimet e mia kryesore ka qenë t'i bëj metodat e programimit më të aksesueshme për njerëzit në fusha të tjera. Si rregull, këta specialistë marrin përfitime të mëdha duke përdorur kompjuterë, por nuk mund të përballojnë të kalojnë kohë duke kërkuar informacionin e nevojshëm, copa dhe pjesë të të cilave janë të shpërndara në shumë revista teknike.

  Tema e këtyre librave mund të formulohet si më poshtë: “Analiza jo numerike”. Kompjuterët zakonisht shoqërohen me zgjidhjen e problemeve numerike, si gjetja e rrënjëve të një ekuacioni, interpolimi numerik, integrimi, etj. Por tema të tilla nuk trajtohen në këtë libër me tre vëllime (përveç rasteve kur është e nevojshme të bëhet kjo gjatë rrugës) . Programimi numerik kompjuterik është një fushë jashtëzakonisht interesante dhe me zhvillim të shpejtë;

  është shkruar shumë për këtë temë libra të mirë. Por që nga vitet 1960, kompjuterët janë përdorur gjithnjë e më shumë për të zgjidhur probleme në të cilat numrat luajnë një rol dytësor. Tani aftësia e kompjuterit për të marrë vendime, dhe jo vetëm për të ekzekutuar, del në pah. veprimet aritmetike. Gjatë zgjidhjes së problemeve jo-numerike, ndonjëherë është e nevojshme të kryhen veprime të mbledhjes dhe zbritjes, por nevoja për shumëzim dhe pjesëtim ndodh mjaft rrallë. Por, sigurisht, edhe dikush që është i angazhuar kryesisht në numerikë programimi kompjuterik, do të përfitojë vetëm nga studimi i metodave jonumerike, pasi ato janë edhe baza e programeve numerike.

  Rezultatet e hulumtimit në fushën e analizave jonumerike janë të shpërndara në shumë revista teknike. Qëllimi im ishte të nxirrja nga kjo sasi e madhe informacioni vetëm metoda themelore që mund të aplikohen në lloje të ndryshme situatash programimi. Jam përpjekur të përgjithësoj informacionin e përzgjedhur për të marrë atë që pak a shumë mund të quhet "teori", si dhe të tregoj se si të zbatohet kjo teori në probleme të ndryshme praktike.

  Natyrisht, “analiza jo numerike” është një emër jashtëzakonisht fatkeq për këtë fushë të shkencës. Është për të ardhur keq, para së gjithash, sepse përmban vetëm mohimin e një koncepti tjetër; do të ishte shumë më mirë të zgjidhni një term më kuptimplotë që nuk ka parashtesën "jo". Emri "përpunimi i informacionit" mbulon një fushë më të gjerë sesa materiali i konsideruar këtu dhe "metodat e programimit" një zonë më të ngushtë. Besoj se për temën e trajtuar në këta libra, emri më i përshtatshëm është analiza e algoritmeve, e cila mund të deshifrohet si "teoria e vetive të algoritmeve të caktuara kompjuterike".

  Kompleti i plotë i librave, i titulluar Arti i Programimit, ka strukturën bazë të mëposhtme.

  Vëllimi 1. Algoritmet bazë

  Kapitulli 1. Konceptet bazë Kapitulli 2. Strukturat e informacionit

  Vëllimi 2. Algoritme të derivuara

  Kapitulli 3 Numrat e rastësishëm Kapitulli 4 Aritmetika

  Vëllimi 3. Renditja dhe kërkimi

  Kapitulli 5 Renditja Kapitulli 6 Kërkimi

  Vëllimi 4. Algoritme Kombinatore

  Kapitulli 7 Kërkimi Kombinator Kapitulli 8 Rekursioni

  Vëllimi 5 Algoritme sintaksore

  Kapitulli 9 Kërkimi leksikografik Kapitulli 10 Parsing

  Vëllimi 4 mbulon një temë shumë të madhe, kështu që në fakt përbëhet nga tre libra të veçantë (vëllimet 4A, 4B dhe 4C). Ka gjithashtu plane për të nxjerrë dy vëllime shtesë për tema më të specializuara: Vëllimi 6, Teoria e Gjuhëve (Kapitulli 11) dhe Vëllimi 7, Përpiluesit (Kapitulli 12).

  E fillova këtë punë në vitin 1962 me synimin për të shkruar një libër të vetëm që përmban të gjithë kapitujt e listuar, por shpejt kuptova se ishte e nevojshme të hyja thellë në temat e zgjedhura, dhe jo thjesht të "rrëshqisja nga sipërfaqja". Rezultati ishte një tekst kaq i gjatë sa që materiali i çdo kapitulli ishte më se i mjaftueshëm për të studiuar gjatë një semestri universitar. Dhe u bë e qartë se ishte e nevojshme të ndahej materiali në disa vëllime të veçanta. E di që një libër që përmban vetëm një ose dy kapituj duket mjaft i çuditshëm, por vendosa të mbaj numërimin e kapitullit origjinal për të thjeshtuar referencat e kryqëzuara. Një version i shkurtuar i Vëllimeve 1-5 është planifikuar të shërbejë si një referencë më e përgjithshme dhe/ose tekst shkollor për studentët; ai do të përmbajë pjesën më të madhe të materialit në këto vëllime, me informacion më specifik të hequr. Botimi i shkurtuar do të mbajë të njëjtin numërim të kapitujve si botimi i plotë.

  Vëllimi 1 mund të shihet si një "kryqëzimi" i grupit të plotë të kapitujve, në kuptimin që përmban informacionin bazë që përdoret në të gjithë librat e tjerë. Nga ana tjetër, vëllimet 2-5 mund të lexohen në mënyrë të pavarur nga njëri-tjetri. Vëllimi 1 nuk është vetëm një referencë për t'u përdorur si udhëzues kur lexoni vëllime të tjera; ai mund të shërbejë gjithashtu si një libër shkollor universitar ose udhëzues vetë-studimi mbi strukturën e të dhënave (përqendrohuni në kapitullin 2) ose matematikën diskrete (përqendrohuni në seksionet 1.1, 1.2, 1.3.3 dhe 2.3.4), ose programimin e gjuhës së makinës (përqendrohuni në seksionet 1.3 dhe 1.4).

  Këta kapituj janë shkruar nga një këndvështrim tjetër nga librat më modernë të programimit, d.m.th., nuk u përpoqa t'i mësoja lexuesit se si të përdorë softuerin e dikujt tjetër. Në vend të kësaj, unë synova t'i mësoja lexuesit se si të shkruanin programet e tyre të cilësisë më të lartë.

  Qëllimi im fillestar ishte t'i prezantoja lexuesit me avantazhet e fundit të kërkimit shkencor në secilën nga fushat e studimit në shqyrtim. Por është shumë e vështirë të mbash të informuar për punët e një industrie që është ekonomikisht fitimprurëse; rritje shpërthyese Shkenca Kompjuterike e bëri të pamundur ëndrrën time. E thënë në mënyrë figurative, e gjeta veten në bregun e një oqeani të pakufi që përmban dhjetëra mijëra rezultate të vogla që u morën nga dhjetëra mijëra njerëz të talentuar në mbarë botën. Kështu që më duhej t'i vendosja vetes një qëllim të ri - të fokusohesha në metodat "klasike" që do të mbeten të rëndësishme për shumë dekada dhe t'i përshkruaj ato sa më mirë që të mundem me të mirën e aftësisë sime. Në veçanti, jam përpjekur të gjurmoj historinë e secilës temë dhe të vendos një themel të fortë për të. zhvillimin e mëtejshëm. Jam përpjekur të përdor terminologji të saktë, në përputhje me atë të përdorur në botimet moderne, dhe jam përpjekur të raportoj mbi të gjitha idetë e njohura të programimit sekuencial që dallohen për thjeshtësinë dhe elegancën e formulimit të tyre.

  Tani disa fjalë për përmbajtjen matematikore të këtij botimi shumëvëllimësh. Materiali paraqitet në atë mënyrë që të jetë mjaft i aksesueshëm edhe për personat me arsim të mesëm; ata do të jenë në gjendje të shikojnë fragmente më komplekse ose thjesht t'i heqin ato. Në të njëjtën kohë, ata që kanë aftësi për matematikë do të mund të mësojnë metoda interesante matematikore në lidhje me matematikën diskrete. Një dual i tillë i paraqitjes së informacionit u arrit, nga njëra anë, duke i caktuar një vlerësim secilit ushtrim (në mënyrë që lexuesi të dallojë ushtrimet matematikisht komplekse nga ato të thjeshta), dhe nga ana tjetër, falë një organizimi të tillë të seksioneve. në të cilin rezultatet kryesore matematikore janë formuluar para provave. . Provat propozohen ose të kryhen në mënyrë të pavarur si ushtrime (përgjigjet e të cilave janë dhënë në një seksion të veçantë), ose të gjenden në fund të seksionit.

  Një lexues i cili është kryesisht i interesuar në programim dhe jo në matematikë, mund të dëshirojë të ndalojë së lexuari një pjesë sapo materiali matematikor bëhet shumë i vështirë për t'u kuptuar. Nga ana tjetër, lexuesi-matematicieni do të gjejë shumë për vete fakte interesante. Shumë botime matematikore mbi temën e programimit kanë qenë të gabuara, ndaj një nga qëllimet e këtij libri është t'i sigurojë lexuesit bazën e saktë matematikore për lëndën e prezantimit. Dhe meqenëse e konsideroj veten një matematikan, detyra ime e drejtpërdrejtë është të paraqes saktë (për aq sa mundem) materialin nga pikëpamja matematikore.

  Për të lexuar pjesën më të madhe të materialit matematikor, njohuritë e matematikës elementare janë mjaft të mjaftueshme, pasi pothuajse e gjithë pjesa tjetër e teorisë zhvillohet këtu. Por ndonjëherë kam nevojë për teorema më të thella në teorinë e variablave komplekse, teorinë e probabilitetit, teorinë e numrave, etj. Në raste të tilla, u referohem librave që përmbajnë një prezantim të detajuar të këtyre temave.

  Vendimi më i vështirë që më duhej të merrja në përgatitjen e këtyre librave ishte se si t'i prezantoja metoda të ndryshme. Përparësitë e grafikëve të rrjedhës dhe përshkrimeve hap pas hapi të algoritmeve janë të njohura; këto çështje janë diskutuar në artikullin "Computer-Drawn Flowcharts" në ACM Communications, Vol. 6 (shtator 1963), faqe 555-563. Për të përshkruar çdo algoritëm kompjuterik, nevojitet gjithashtu një gjuhë zyrtare dhe e saktë. Kështu që më duhej të vendosja se cilën gjuhë të përdorja: një algjebrike si ALGOL ose FORTRAN, ose një gjuhë e orientuar nga makina. Ndoshta shumë nga shkencëtarët e sotëm të kompjuterave nuk do të pajtohen me vendimin tim për të përdorur një gjuhë të orientuar nga makina, por u sigurova që të ishte zgjedhja e duhur. Ka arsyet e mëposhtme për këtë.

  a) Një programues ndikohet shumë nga gjuha në të cilën shkruhen programet. Aktualisht, tendenca mbizotëruese është zgjedhja e konstruksioneve gjuhësore më të thjeshta dhe jo më optimale për një kompjuter. Dhe një programues që njeh një gjuhë të orientuar nga makina ka tendencë të përdorë më shumë metoda efektive dhe kështu krijon programe më të mira.

  b) Të gjitha programet që na duhen, të shkruara në një gjuhë të orientuar nga makina, me përjashtime të rralla, do të jenë të vogla në përmasa. Dhe kjo do të thotë se nëse kemi një kompjuter me një fuqi minimale llogaritëse, nuk do të kemi probleme me përdorimin e programeve të tilla.

  c) Gjuhët e nivelit të lartë janë të papërshtatshme për të diskutuar detaje të rëndësishme të nivelit të ulët si komunikimi korutin, gjenerimi i numrave të rastësishëm, aritmetika me saktësi të lartë dhe shumë çështje të tjera të lidhura. përdorim efikas memorie.

  d) Kushdo që është seriozisht i interesuar për kompjuterët duhet të ketë njohuri të mira të gjuhës së makinës, pasi ajo qëndron në themel të funksionimit të një kompjuteri.

  e) Disa njohuri të gjuhës së makinës janë të nevojshme në çdo rast për të kuptuar rezultatin e programeve të dhëna në shumë shembuj.

  f) Gjuhët e reja algjebrike hyjnë dhe dalin nga moda rreth çdo pesë vjet, ndërsa unë përpiqem të flas për "të vërtetat e përjetshme".

  Nga ana tjetër, e pranoj se shkrimi i programeve në gjuhë të nivelit të lartë dhe korrigjimi i këtyre programeve është shumë më i lehtë. Në fakt, që nga viti 1970, unë vetë kam përdorur rrallë gjuhë makinerie të nivelit të ulët për programet e mia, sepse kompjuterët modernë kanë një sasi të madhe memorie dhe shpejtësi të lartë. Por për të zgjidhur shumë nga problemet e diskutuara në këtë libër, vlera më e lartë ka artin e programimit. Për shembull, disa llogaritje kombinuese duhet të përsëriten triliona herë, dhe ne do të kursejmë afërsisht 11.6 ditë pune duke reduktuar kohën e llogaritjes në lakun e brendshëm me vetëm një mikrosekondë. Në mënyrë të ngjashme, ka kuptim të bëni përpjekje shtesë për të shkruar një program që do të përdoret shumë herë çdo ditë në shumë kompjuterë, veçanërisht pasi programi duhet të shkruhet vetëm një herë.

  Dhe nëse vendosni të përdorni një gjuhë të orientuar nga makina, atëherë cila gjuhë duhet të preferohet? Mund të zgjidhja gjuhën për një makinë të veçantë X, por më pas ata që përdorin një kompjuter tjetër do ta mendonin këtë ky libër shkruar vetëm për pronarët e kompjuterit X. Për më tepër, makina X ndoshta ka shumë tipare karakteristike, për të cilin materiali i këtij libri është plotësisht i pazbatueshëm, por megjithatë është e nevojshme të konstatohet. Dhe së fundi, pas dy vitesh, prodhuesi i makinës X do të prodhojë makinën X+1 ose 10X, dhe kompjuteri X nuk do të jetë më me interes për askënd.

  Për të zgjidhur këtë problem, u përpoqa të zhvilloj një kompjuter "të përsosur" me një shumë rregulla të thjeshta vepra (të cilat mund t'i mësoni, të themi, vetëm në një orë) dhe shumë të ngjashme me makinat e vërteta. Nuk ka asnjë arsye që një student të shmangë të mësuarit e karakteristikave të kompjuterëve të ndryshëm; pasi të mësoni një gjuhë, të gjitha të tjerat do të asimilohen shumë më lehtë. Për më tepër, një programues serioz duhet të përgatitet për faktin se gjatë punës së tij ai do të duhet të merret me gjuhë të ndryshme makine. Prandaj, ekziston vetëm një disavantazh i përdorimit të një makinerie imagjinare - vështirësia e ekzekutimit të programeve të shkruara për të. Për fat të mirë, ky nuk është vërtet një problem, pasi shumë vullnetarë kanë dalë vullnetarë për të shkruar makina tallëse për makinën hipotetike. Këta simulatorë janë idealë për qëllime mësimore dhe janë edhe më të lehtë për t'u punuar me të sesa një kompjuter i vërtetë.

  Jam përpjekur të lidh me artikujt më të mirë të vjetër për secilën temë, si dhe të përmend punë më të reja. Kur u referohem burimeve letrare, kam përdorur shkurtesat standarde për titujt e periodikëve, me përjashtim të revistave më të cituara, për të cilat janë përdorur shkurtesat e mëposhtme.

  SACM - Komunikimet e Shoqatës për Makineri Kompjuterike

  JACM - Journal of Association for Computing Machinery

  Bashkëpunëtor J. - The Computer Journal (British Computer Society)

  Math. Bashkëpunëtor - Matematika e Llogaritjes

  AMM - Mujore Matematikore Amerikane

  SICOMP - SIAM Journal on Computing

  FOCS - Simpoziumi IEEE mbi Bazat e Shkencave Kompjuterike

  SODA - ACM-SIAM Simpozium mbi Algoritmet diskrete

  STOC - ACM Simpozium mbi Teorinë e Informatikës

  Crelle - Die lesh die reine und angewandte Mathematik

  Për shembull, "CACM 6 (1963), 555-563" nënkupton një referencë për ditarin e përmendur në një nga paragrafët e mëparshëm të kësaj parathënie. Unë kam përdorur gjithashtu shkurtesën "CMatA" për t'iu referuar Matematikës Konkrete, e cila është referuar në hyrje të seksionit 1.2.

  Shumica material teknik këto libra japin llogari për ushtrimet. Nëse ideja e një ushtrimi jo të parëndësishëm nuk më përkiste mua, atëherë u përpoqa të përmend autorin e tij. Referencat për literaturën zakonisht jepen në tekstin e seksionit ose në përgjigjen e ushtrimit. Por në shumë raste, ushtrimet bazohen në materiale të pabotuara që nuk mund të referohen.

  Gjatë viteve të gjata të punës për këto libra më ndihmuan shumë njerëz, të cilëve u jam mirënjohës nga zemra. Fillimisht, dua të shpreh mirënjohjen time për bashkëshorten time Jill) për durimin e saj të pafund, për përgatitjen e disa prej ilustrimeve dhe për ndihmë e vazhdueshme në çdo gjë. Gjithashtu i jam mirënjohës Floyd Robert W. që i kushtoi kaq shumë kohë në vitet 1960 përmirësimit dhe thellimit të këtij materiali. Mijëra njerëz të tjerë më dhanë gjithashtu ndihmë të çmuar. Do të duhej një libër tjetër si ky vetëm për të renditur emrat e tyre! Shumë prej tyre me dashamirësi më lejuan të përdor punën e tyre të vjetër të pabotuar. Hulumtimi im në Caltech dhe Universitetin Stanford u financua bujarisht nga National themeli shkencor(Fondacioni Kombëtar i Shkencës) dhe Departamenti i Kërkimeve Detare (Zyra e Kërkimeve Detare). Addison-Wesley ka qenë një ndihmë dhe mbështetje e madhe për mua që kur fillova projektin në 1962. Më duket se për të gjithë këta njerëz mirënjohja më e mirë është ky botim. Tregon se kontributet e tyre kanë çuar në libra në të cilët shpresoj të kem shkruar atë që ata prisnin.

  Parathënie e botimit të tretë

  Pasi kalova dhjetë vjet duke zhvilluar sistemet e shtypjes METAFONT dhe TEX, tani mund të përmbush ëndrrën time për të përdorur këto sisteme për të shtypur një libër. Arti i Programimit. Më në fund, munda ta fusja tekstin e plotë të këtij libri në një kompjuter personal dhe kështu ta merrja version elektronik, e cila do t'ju lejojë të bëni çdo ndryshim në teknologjinë e printimit dhe shfaqjes në ekran në të ardhmen. Kjo mënyrë pune më ka dhënë mundësinë për të bërë fjalë për fjalë mijëra përmirësime; Kam arritur atë që kam ëndërruar për kaq shumë kohë.

  Në këtë botim të ri, unë kam qenë në gjendje të kontrolloj çdo fjalë të tekstit, duke u përpjekur të ruaj energjinë rinore të kërkimit tim origjinal dhe në të njëjtën kohë të sjell një pjekuri më të madhe gjykimi. Janë shtuar dhjetëra ushtrime të reja dhe dhjetëra të vjetra janë dhënë përgjigje të reja ose të përmirësuara.

  Kështu vazhdon puna për librin “Arti i programimit”. Kjo është arsyeja pse disa pjesë të këtij libri fillojnë me ikonën "Në proces ndërtimi" (kjo është një lloj faljeje për faktin se informacioni i dhënë nuk është i fundit). Dosjet e mia janë plot me materiale të rëndësishme që planifikoj t'i përfshij në botimin e katërt përfundimtar, të lavdishëm të vëllimit 1; ndoshta do të dalë pas 15 vitesh. Por fillimisht më duhet të përfundoj vëllimet 4 dhe 5. Dua që ato të botohen sapo të jenë gati për shtypje.

  Pjesa më e madhe e punës së vështirë në përgatitjen e këtij botimi të ri u bë nga Phyllis Winkler dhe Silvio Levy, të cilët shtypën dhe redaktuan në mënyrë profesionale tekstin për edicionin e dytë, dhe nga Jeffrey Oldham, i cili konvertoi pothuajse të gjitha ilustrimet origjinale në formatin METAP0ST. Kam korrigjuar të gjitha gabimet që lexuesit vigjilentë (Barry) gjetën në botimin e dytë (si dhe gabimet që, mjerisht, askush nuk i vuri re) dhe u përpoqa të shmangte futjen e gabimeve të reja në materialin e ri. Megjithatë, e pranoj se ende mbeten disa të meta dhe do të doja t'i korrigjoja sa më shpejt të jetë e mundur. Prandaj, për çdo gabim shtypi*, si dhe një gabim në lidhje me përmbajtjen e materialit të paraqitur ose me informacionin historik të dhënë, me kënaqësi do t'i paguaj 2,56 dollarë personit të parë që do ta gjejë atë. Në faqen e internetit, adresa e së cilës është dhënë në anën e pasme Titulli i faqes, përmban një listë aktuale të të gjitha gabimeve të raportuara tek unë**.

  * I referohet origjinalit të këtij botimi. - Përafërsisht. ed.
  ** Gabimet e njohura në kohën e përgatitjes së botimit rus janë korrigjuar. - Përafërsisht. ed.

  D.E.K.
  Stanford, Kaliforni
  Prill 1997

  Bota ka ndryshuar në njëzet vitet e fundit.
  - Bill Gates (1995)

  
  KAPITULLI 1. KONCEPTET THEMELORE ...................................... ...................... 27
  1.1. ALGORITME ..................................................... ...... 27
  1.2. HYRJE MATEMATIKE................................................ 37
  1.2.1. Induksioni matematik................................................ 38
  1.2.2. Numrat, fuqitë dhe logaritmet................................... 49
  1.2.3. Shumat dhe produktet...................................... 56
  1.2.4. Funksionet e plota dhe teoria elementare e numrave .......... 68
  1.2.5. Permutacionet dhe faktorialet................................... 75
  1.2.6. Koeficientët binomialë................................ 82
  1.2.7. Numrat Harmonikë ................................................ 105
  1.2.8. Numrat e Fibonaçit................................................ 109
  1.2.9. Funksionet gjeneruese................................................ 118
  1.2.10. Analiza e Algoritmit................................................ 127
  *1.2.11. Paraqitjet asimptotike................................ 138
  *1.2.11.1. Simboli RRETH .......................................... 138
  *1.2.11.2. Formula e mbledhjes së Euler-it................................ 143
  *1.2.11.3. Zbatimi i formulave asimptotike ................. 148
  1.3. PËRZIHET ................................................ ............. 156
  1.3.1. Përshkrimi i përzierjes ................................ 156
  1.3.2. Gjuha e montimit të kompjuterit MIX .............................. 178
  1.3.3. Zbatimi te permutacionet................................ 198
  1.4. DISA TEKNIKA THEMELORE TË PROGRAMIMIT.......................... 221
  1.4.1. Nënprogramet ..................................................... 221
  1.4.2. Korutinat................................................ .. 229
  1.4.3. Programet e përkthyesve................................................ ... 237
  1.4.3.1. Simulatori MIX ................................... 239
  *1.4.3.2. Programet e rrugëzimit................................ 248
  1.4.4. Hyrja dhe Dalja ..................................................... .............. 251
  1.4.5. Historia dhe bibliografia ................................... 266

  KAPITULLI 2. STRUKTURAT E INFORMACIONIT ................................................... 271
  2.1. PREZANTIMI ................................................. .... 271
  2.2. LISTA LINEARE................................................ .... 277
  2.2.1. Raftet, Radhët dhe Kuvertat................................... 277
  2.2.2. Shpërndarja sekuenciale.............................. 283
  2.2.3. Shpërndarja e Asociuar................................... 295
  2.2.4. Listat ciklike ................................................ 315
  2.2.5. Dy herë listat e lidhura................................ 322
  2.2.6. Vargjet dhe listat ortogonale................................. 341
  2.3. PEMËT................................................ ..... 352
  2.3.1. Përshkimi i pemëve binare................................ 362
  2.3.2. Paraqitja e pemëve si pemë binare......... 380
  2.3.3. Paraqitje të tjera të pemëve................................ 395
  2.3.4. Vetitë themelore matematikore të pemëve...................... 410
  2.3.4.1. Pemët e lira................................ 410
  2.3.4.2. Pemët e orientuara ................................ 420
  *2.3.4.3. The Infinite Tree Lemma.......................... 431
  *2.3.4.4. Numërimi i pemëve................................ 435
  2.3.4.5. Gjatësia e shtegut .............................. 449
  *2.3.4.6. Historia dhe bibliografia .......................... 456
  2.3.5. Listat dhe grumbullimi i mbeturinave .......................................... 459
  2.4. STRUKTURA TË LIDHUR ME SHUMË .......................................... 476
  2.5. ALOKIMI I MEMORISE DINAMIKE ................................................... .. 488
  2.6. HISTORIA DHE BIBLIOGRAFIA ................................................ 512

  PËRGJIGJET E USHTRIMEVE ................................................ ...................... 521

  SHTOJCA A. TABELA E VLERAVE TË DISA KONSTANTAT .................................. 683
  A.I. Konstantet themelore (dhjetore) .......................................... 683
  A.2. Konstantet bazë (oktale) .............................................. 684
  A.Z. Vlerat e numrave harmonikë, numrat Bernoulli dhe numrat Fibonacci...... 685

  SHTOJCA B. SIMBOLET KRYESORE ................................................... ................. 687

  INDEKSI ................................................ ................................. 692
  
  

  27 dhjetor 2011 në orën 13:32

  Arti i programimit?

  • Programimi

  Më pëlqen të lexoj artikuj programimi që nuk përmbajnë asnjë rresht të vetëm kodi. Artikuj të tillë zhvillohen në mënyrë të përsosur "në thellësi" dhe shpesh japin një arsye për të parë gjërat e krijuara prej kohësh nga një këndvështrim tjetër. Prandaj, duke rrezikuar të shkaktoja zemërimin e një pjese të caktuar të publikut për karmën time tashmë të rrëgjuar, megjithatë vendosa ta botoj këtë artikull, me shpresën se do t'i japë dikujt jo vetëm ushqim për të menduar, por edhe të ndihmojë për të marrë një vështrim i freskët në aktivitetet e tyre.

  Filloni

  Kështu ndodhi që në vendin aktual të punës, programuesit lihen në pajisjet e tyre. Kjo është, natyrisht, ata kodojnë për të mirën e ndërmarrjes, por plotësisht në mënyrë të pakontrolluar, deri në mungesë të një testuesi banal. TOR edhe për programet "të rënda" rrallë tejkalon vëllimin e tre fletëve A4 (njëra prej të cilave është nënshkrimet e të gjithë atyre që janë përfshirë).

  Thirrjet për problemet e softuerit shkojnë drejtpërdrejt te programuesit. Që kur filloi gjithçka.
  
  Vura re që numri i thirrjeve me kolegun tim (një person që punon në specialitet dhe konkretisht në këtë vend është disa vjet më i gjatë se unë) është një renditje e madhësisë (pa ekzagjerim) më e lartë se numri i thirrjeve në softuerin tim. Në të njëjtën kohë, telefonatat janë zakonisht më "të rënda". Prevalenca dhe kompleksiteti i produkteve tona është afërsisht i njëjtë.

  Në procesin e komunikimit, u interesova për pikëpamjet e kolegëve për programimin, pas së cilës shikova kodet burimore disa programe dhe gjithçka ra në vend.

  Opus rreth personaliteteve krijuese

  Për arsye të ndryshme personale dhe biznesi, unë komunikoj me njerëz krijues. Në thelb, këta janë muzikantë dhe artistë të drejtimeve të ndryshme. Unë jam shpesh me ta në mjedise të ndryshme - nga habitatet e tyre te dyqanet dhe kafenetë.

  Në shtëpi, njerëz të tillë, si rregull, kanë një rrëmujë të një rrëmuje krijuese - nga një divan i spërkatur me bojë dhe mure të shkreta deri te një lloj i tmerrshëm i pajisjeve dhe veglave shtëpiake.

  Veprimet e njerëzve të tillë kanë një vektor të caktuar, por parametrat e tij nuk përcaktohen nga numrat me pikë lundruese, por nga drejtimi "jug-jug-perëndim". Kjo vlen jo vetëm për të shkuar në dyqan (të blesh diçka në listë me njerëz të tillë është thjesht joreale), por për gjithçka në përgjithësi, përfshirë kreativitetin.

  Kur punon në një pjesë, artisti/muzikanti zakonisht niset nga ky "vektor jug-jug-perëndim" - nga një humor, koncept i caktuar (i lindur brenda ose i nxjerrë nga klienti, ky është në këtë rast jo aq e rëndësishme). Rezultati përfundimtar është, në shumicën e rasteve, shumë i paqartë. Me drejtësi, vërejmë se kjo është pjesa më e madhe e kënaqësisë së krijimtarisë - të bësh ashtu siç bëhet. Kjo, në thelb, është një përpjekje për të "shprehur veten".

  programues krijues

  I kthehemi bisedës për programuesit. Gjatë komunikimit, rezultoi se disa kolegë, jo pa krenari, flasin për veten e tyre si përfaqësues të "profesionit krijues". Duke bërë këtë, ata përdorin vërtet një qasje krijuese (“vektor jug-perëndim-perëndim”) me praktikisht komplet i plotë atributet. Si rezultat, shfaqen module të lidhjes krejtësisht të çuditshme, klasa me një hierarki "Unë do të bëj një figurë të tillë këtu", metodat ndahen me magji në "interesante" (të dizajnuara mirë, me trajtim të qartë të gabimeve - si zbatimi i kriptimit dhe protokollet e rrjetit) dhe "jointeresante" (lista kilometrike të eksportit të të dhënave, me shumë copy-paste).

  Trajtimi i gabimeve bëhet siç rezulton - këtu kontrollojmë vlerat e kthimit, dhe në skedarin fqinj kemi mekanizma të trajtimit të përjashtimeve. Këtu përdorim tregues inteligjentë, atje punojmë drejtpërdrejt. Dhe një mori gjërash të tjera si kjo.

  Si rezultat vepra të ngjashme fitohet një produkt krejtësisht i paparashikueshëm. Problemi kryesor i një prej zhvilluesve tanë është rregullimi i gabimeve në version i ri vazhdimisht sjell shfaqjen e gabimeve të reja në modulet tashmë të korrigjuara në dukje, dhe tashmë është joreale ta parandalosh këtë pa një rishkrim të plotë të gjithçkaje dhe të gjithëve. Është shumë e vështirë të ruash një produkt të tillë - përsosja e pikave më elementare kërkon një meditim të gjatë mbi kodin në përpjekje për të kuptuar se si të bësh diçka në mënyrë që gjithçka të mos shembet, dhe mundësisht pa copy-paste të "krijimtarisë" ekzistuese. ".

  Morali i kësaj fabule

  Programimi nuk ka të bëjë me të shprehurit e vetes, pavarësisht se çfarë mund të pretendojnë të rinjtë romantikë. kod i mirë- është projektuar dhe ndërtuar qartë sipas rregulla të caktuara dokument. Fatkeqësisht për disa, një programues është një robot që, në varësi të cilësisë së udhëzimeve të ngulitura në të, i shpjegon një roboti tjetër me efikasitet të ndryshëm se çfarë duan këto masa proteinash prej tij. Nuk ka vend për kreativitet në programim - nga emërtimi i skedarëve dhe variablave te modelet, gjithçka i nënshtrohet logjikës së qartë dhe ka efikasitet maksimal. Si rezultat, për këtë efikasitet, programuesi merr jo vetëm paratë e punëdhënësit, por edhe qetësinë mendore kur shoqëron produktin dhe një ndjenjë kontrolli mbi situatën në rast të problemeve me programin.

  Edhe nëse programuesit nuk i jepet një TOR i shkruar mirë, ju duhet t'i jepni vetes një kuptim të qartë të asaj që do të ndodhë në fund. Nëse ekziston mundësia që ajo që shkruhet do të duhet të modifikohet thellësisht, aq më mirë - detyrat e shkrimit të softuerit me probabilitetin për t'u modifikuar shumë janë shumë emocionuese dhe aspak të lehta.

  Epo, si përfundim, fraza e Steve McConnell - "Shkruaj kodin sikur do të shoqërohet nga një psikopat i dhunshëm që e di se ku jetoni". Dhe një psikopat ndoshta do të zemërohet shumë nëse thyen kokën nga mungesa e logjikës dhe rregullit.

  Shënim për librin Arti i Programimit, Vëllimet 1-3:
  Shumë njerëz e dinë se programimi nuk është vetëm një punë komplekse mendore, por edhe një proces krijues. Autori i këtij libri, Donald Erwin Knuth, është profesor në Universitetin e Stanfordit dhe ka shkruar shumë libra për matematikën dhe shkencat kompjuterike. Vepra e famshme "Arti i Programimit", vëllimi i parë i së cilës u botua më shumë se 20 vjet më parë, i solli famë shkencëtarit. Në librin e tij, Donald Knuth shpjegon dhe analizon algoritmet bazë të përdorura në programim. Ky është edicioni i tretë i serisë së mirënjohur të librave Arti i Programimit.

  Ky botim përmban 3 vëllime të Artit të Programimit:

  Arti i programimit. Vëllimi 1. Algoritmet bazë.
  Arti i programimit. Vëllimi 2. Algoritme të derivuara.
  Arti i programimit. Vëllimi 3. Renditja dhe kërkimi.

  Vëllimi i parë i serisë së librave Arti i Programimit fillon me një përshkrim të koncepteve dhe metodave bazë të programimit. Autori më pas fokusohet në shqyrtimin e strukturave të informacionit - përfaqësimin e informacionit brenda një kompjuteri, marrëdhëniet strukturore midis elementeve të të dhënave dhe si punë efektive me ta. Janë dhënë shembuj të aplikacioneve elementare për metodat e simulimit, llogaritjet simbolike, metodat numerike dhe metodat e zhvillimit të softuerit. Krahasuar me botimin e mëparshëm, janë shtuar dhjetëra algoritme të thjeshta, por në të njëjtën kohë shumë të rëndësishme. Në përputhje me trendet moderne hulumtimi, seksioni i hyrjes matematikore gjithashtu u rishikua ndjeshëm.

  Vëllimi i dytë paraqet teorinë e algoritmeve të derivuara. Kapituj të veçantë përmbajnë një përshkrim të procesit të gjenerimit të numrave të rastësishëm dhe mënyrat për të punuar me ta në një mjedis kompjuterik. Autori i konsideron konceptet themelore të teorisë së probabilitetit siç zbatohen sistemet kompjuterike, duke i ofruar lexuesit algoritme të gatshme programet kompjuterike. Meriton vëmendje të veçantë metodë e re autori i gjenerimit të numrave të rastësishëm dhe një përshkrim i algoritmeve për llogaritjen e serive formale të fuqisë.

  Botimi i tretë i vëllimit të tretë përmban rishikim i plotë algoritme klasike të renditjes dhe kërkimit. Informacioni i paraqitur në të plotëson diskutimin e strukturave të të dhënave të dhëna në vëllimin e parë. Autori merr në konsideratë parimet e ndërtimit të bazave të të dhënave të mëdha dhe të vogla, si dhe memorien e brendshme dhe të jashtme. Libri përmban një përzgjedhje të algoritmeve kompjuterike të testuara me kujdes dhe analizon efektivitetin e tyre. Për më tepër, një seksion i veçantë i kushtohet metodave optimale të renditjes dhe një përshkrimi të teorisë së re të ndërrimit dhe hashimit universal.

  Emri: Arti i Programimit - Vëllimi 1.

  Vëllimi i parë i serisë së librave Arti i Programimit fillon me një përshkrim të koncepteve dhe metodave bazë të programimit. Më pas autori vazhdon të marrë në konsideratë strukturat e informacionit, përfaqësimin e informacionit brenda një kompjuteri, marrëdhëniet strukturore midis elementeve të të dhënave dhe si të punohet në mënyrë efektive me to. Për metodat e simulimit jepen llogaritjet simbolike, metodat numerike, metodat e zhvillimit të softuerit, shembuj të aplikacioneve elementare. Krahasuar me botimin e mëparshëm, janë shtuar dhjetëra algoritme të thjeshta, por në të njëjtën kohë shumë të rëndësishme. Në përputhje me tendencat moderne në kërkime, seksioni i hyrjes matematikore është rishikuar ndjeshëm.

  Çdo libër ka fatin e vet. Disa shfaqen në mënyrë të padukshme dhe po aq të padukshme zhduken në rrjedhën e kohës, të mbuluara me pluhur në raftet e bibliotekave. Të tjerë në një periudhë të caktuar janë të kërkuara mes një rrethi të ngushtë specialistësh, derisa librat e rinj të referencës vijnë për t'i zëvendësuar. Të tjerë akoma, duke u ngritur mbi kohën, ushtrojnë një ndikim të fuqishëm në zhvillimin teknologjik të shoqërisë. Nuk ka aq shumë libra që hyjnë në kategorinë e fundit. Lirimi i tyre është gjithmonë festë. Vitet kalojnë, teknologjitë ndryshojnë, por gjeneratat e reja i rilexojnë faqet e tyre me interes të vazhdueshëm. Pikërisht librave të tillë i përket vepra shumëvëllimore e shkencëtarit të famshëm amerikan Donald Erwin Knuth "Arti i Programimit" i ofruar lexuesit.
  Cili është suksesi i Artit të Programimit të D. E. Knuth:
  Së pari, ky libër është një libër i shkëlqyer për shkrimin dhe analizimin e algoritmeve kompjuterike. Seksionet e tij mund të përfshihen në shumë kurse universitare mbi teknologjitë e programimit, teorinë e algoritmeve dhe matematikën diskrete. Libri mund të studiohet edhe nga nxënës të shkollave të mesme që njohin bazat e programimit. Si gjuhë kryesore për shkrimin e algoritmeve, autori zgjodhi gjuhën e udhëzimeve të makinës të kompjuterit universal hipotetik MIX. Kjo ju lejon të ndërtoni programe optimale, duke marrë parasysh karakteristikat e kompjuterëve. Transferimi i programeve MIX në kompjuterë të vërtetë ose rishkrimi i tyre në gjuhë të nivelit të lartë nuk është i vështirë. Logjika sesi funksionojnë programet shpjegohet pothuajse gjithmonë me grafikët e thjeshtë të rrjedhës.
  Së dyti, materiali i zgjedhur me kujdes i përfshirë në libër përfshin klasat kryesore themelore të algoritmeve, të cilat në një formë ose në një tjetër hasen më shpesh në praktikën e programimit.
  Së treti, një faktor i rëndësishëm në suksesin e librit të D. E. Knuth është prezantimi enciklopedik. Profesor Knuth dallohet nga aftësia e tij unike për të gjurmuar një problem nga sfondi historik i origjinës së tij deri në gjendjen e tij aktuale. Referencat e shumta për veprat e mjeshtërve të vjetër (deri në kohërat e lashtësisë), të mbyllura në një kontekst modern, krijojnë te lexuesi një ndjenjë të veçantë përfshirjeje në zhvillimin historik të ideve dhe metodave shkencore.

  Shkarko falas e-libër në format i përshtatshëm, shikoni dhe lexoni:
  Shkarkoni librin Arti i Programimit - Vëllimi 1 - Knut D. E. - fileskachat.com, shkarkim i shpejtë dhe pa pagesë.

  Shkarkoni djvu
  Më poshtë mund ta blini këtë libër me çmimin më të mirë të zbritur me dërgesë në të gjithë Rusinë.