Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Мистецтво програмування (англ. The Art of Computer Programming (TAOCP)) — фундаментальна монографія відомого американського фахівця в галузі комп'ютерних наук та математика Дональда Кнута, присвячена розгляду та аналізу найважливіших алгоритмів, що застосовуються в інформатиці. 1999 року книгу було визнано однією з дванадцяти найкращих фізико-математичних монографій століття.
 | |
| Автор | Дональд Кнут |
|---|---|
| Назва мовою оригіналу | The Art of Computer Programming |
| Мова | англійська |
| Тема | алгоритм |
| Жанр | Інформатика |
| Видавництво | Вільямс / Addison–Wesley |
| Видано | 1968—видання продовжується |
Написання книги було розпочате автором 1962 року. Спочатку планувалося випустити її одним томом, але обсяг матеріалу виявився настільки великим, що кількість томів було збільшено до семи. Перші три томи було видано досить швидко: перший том — 1968 р., другий том — 2 1969 року, та третій — 1973 року, після чого було зроблено перерву до лютого 2005 року, в якому автор опублікував першу частину четвертого тому. Було прийнято рішення випускати інші частини четвертого тому приблизно по дві на рік окремими випусками, після чого офіційно видати весь четвертий том. Протягом 2005—2009 років було видано випуски 0, 1, 2, 3 і 4, а 2011 року було видано том 4А, до якого увійшла інформація цих випусків. Також 2005 року було видано випуск 1 «MMIX — RISC-комп'ютер для нового тисячоліття», інформація з якого увійде до нового (четвертого) видання першого тому. У 2015 році був виданий випуск 6 Satisfiability, що містив середню третину майбутнього тому 4B. 2019 року було видано випуск 5 Mathematical Preliminaries Redux; Introduction to Backtracking; Dancing Links, що містив першу третину майбутнього тому 4B. У 2022 році був виданий том 4B.
Час, необхідний на повне завершення книги, сам автор оцінює в 20 років безперервної щоденної роботи. Оскільки Кнут завжди вважав «Мистецтво програмування» основним проектом свого життя, 1990 року він вийшов на пенсію, з наміром повністю сконцентруватися на написанні відсутніх частин і приведення до ладу існуючих.
Історія
Як визнаний експерт зі створення компіляторів, Кнут почав писати книгу для їх проектування 1962 року. Незабаром він усвідомив, що охоплення матеріалу має бути набагато ширшим. У червні 1965 року він завершив написання першої версії того, що він спочатку хотів видати однією книжкою з дванадцяти розділів. Обсяг рукописного тексту склав 3000 сторінок. За розрахунками Кнута, цей обсяг мав вміститися на 600 сторінках друкованого тексту, але, як повідомив йому його видавець, реальний обсяг склав би 2000 сторінок[]. У зв'язку з цим структуру книги було переглянуто на користь кількох томів, по 1-2 розділи кожен. Відтоді, у зв'язку з постійним зростанням матеріалу, було вирішено, що четвертий том також буде розбито на окремі книги: 4A, 4B, 4C, а можливо, і 4D. Але і цей поділ мабуть не буде остаточним, оскільки розділи 7,1 і 7.2.1 вже в сумі займають понад 650 сторінок.
1976 року Кнут підготував друге видання другого тому, що зажадало повторного набору. Але типографське оформлення, яке застосовувалося в першому виданні, на той час вже було недоступним. Щоб уникнути подібних прикростей у майбутньому, 1977 року Кнут почав розробляти власну типографську систему комп'ютерного набору. За його розрахунками, робота мала тривати не більше шести місяців, але знадобилося близько десяти років, перш ніж її було завершено. Система отримала назву TeX, і наразі застосовується для верстки всіх томів «Мистецтва програмування». Крім того, згодом, TeX став фактичним стандартом для написання статей та монографій з природничих наук[].
Як і інші книги Кнута, «Мистецтво програмування» відзначено його «фірмовим знаком»: за кожну помилку, знайдену в тексті, автор виплачує один шістнадцятковий долар, тобто $2,56 (0x100 центів, в системі числення за основою 16). Іншою відмітною особливістю книги є велика кількість вправ для самостійного виконання, різного ступеня складності, починаючи від простих задачок «для розігріву» і закінчуючи проблемами, вирішення яких взагалі невідомо. Складність кожної вправи оцінено за числовою шкалою від 0 до 50. Так, у ранніх виданнях оцінкою 50 було позначено Велику теорему Ферма, але в третьому виданні ця оцінка «девальвувала» до 45, оскільки на той час теорему вже було доведено.
Зміст
Початковий план написання книги припускав таку розбивку матеріалу.
- Том 1. Основні алгоритми.
- Розділ 1. Основні поняття.
- Розділ 2. Інформаційні структури.
- Том 2. Напівчисельні алгоритми.
- Розділ 3. Випадкові числа.
- Розділ 4. Арифметика.
- Том 3. Сортування і пошук.
- Розділ 5. Сортування.
- Розділ 6. Пошук.
- Том 4. Комбінаторні алгоритми.
- Розділ 7. Комбінаторний пошук.
- Розділ 8. Рекурсія.
- Том 5. Синтаксичні алгоритми.
- Розділ 9. Лексикографічний пошук.
- Розділ 10. Синтаксичний пошук.
- Том 6. Теорія мов.
- Том 7. Компілятори.
Фактично ця схема була реалізована аж до третього тому включно.
Наразі видано том 4А, який містить перші розділи 7 глави. Нові розділи планується спочатку видавати окремими випусками (приблизно по 128 сторінок), орієнтовно по два випуски на рік (перед виходом тому 4А подібним чином були видані випуски 0, 1, 2, 3 і 4).
Машинно-орієнтована мова прикладів
Приклади програм, наведені в книзі, використовують «MIX-асемблер», призначений для роботи на гіпотетичному MIX-комп'ютері. У третьому виданні морально застарілий MIX був замінений на MMIX, що має повноцінну RISC-архітектуру. Існує програмне забезпечення, що забезпечує емуляцію (M)MIX-машини на стандартних IBM-сумісних комп'ютерах. GNU Compiler Collection має можливість компіляції C/ коду на цільову архітектуру MMIX.
Багатьох читачів відштовхує факт використання мови низького рівня, але Кнут вважає свій вибір виправданим, оскільки прив'язка до архітектури необхідна для того, щоб можна було точно судити про такі характеристики алгоритму, як швидкість, використання пам'яті та ін. Однак, внаслідок такого вибору, цільова аудиторія сильно звужується. Крім того, обмежується галузь її застосування як «книги рецептів» для програмістів-практиків, багато з яких не знають асемблера, а якщо і знають, то не відчувають бажання перекладати низькорівневі алгоритми з книги на мови високого рівня. Численні практичні керівництва, в яких той же матеріал викладається більш популярно, видають саме з цієї причини[].
Критика
Основною рисою монографії Кнута, що вигідно відрізняє її від інших книг, присвячених програмуванню, є надзвичайно високо піднята планка якості матеріалу й академічності викладу, а також глибина аналізу розглянутих питань. Завдяки цьому вона стала справжнім бестселером і настільною книгою кожного професійного програміста. Журнал American Scientist включив «Мистецтво програмування» до списку 12 найкращих фізико-математичних монографій XX-го століття разом з роботами Дірака з квантової механіки, Ейнштейна з теорії відносності, Рассела і Уайтхеда з основ математики та деякими іншими.
Обкладинка третього видання першого тому книги містить цитату Білла Гейтса: «Якщо ви вважаєте себе справді добрим програмістом …, прочитайте „Мистецтво програмування“ Кнута … Якщо ви зможете зрозуміти всю цю працю, то вам, безумовно, слід надіслати мені резюме». Втім, фольклор приписує ці слова Стіву Джобсу.
Видання
Поточне видання:
- Volume 1: Fundamental Algorithms. Third Edition (Reading, Massachusetts: Addison-Wesley, 1997), xx+650pp.
- Volume 1, Fascicle 1: MMIX — A RISC Computer for the New Millennium. (Addison-Wesley, February 14, 2005) (will be in the fourth edition of volume 1)
- Volume 2: Seminumerical Algorithms. Third Edition (Reading, Massachusetts: Addison-Wesley, 1997), xiv+762pp.
- Volume 3: Sorting and Searching. Second Edition (Reading, Massachusetts: Addison-Wesley, 1998), xiv+780pp.+foldout.
- Volume 4A: Combinatorial Algorithms, Part 1 (Upper Saddle River, New Jersey: Addison-Wesley, 2011), xvi+883pp.
- Volume 4B: Combinatorial Algorithms, Part 2 (Upper Saddle River, New Jersey: Addison-Wesley, 2023), xviii+714pp.
Див. також
Виноски
- http://www-cs-faculty.stanford.edu/~knuth/taocp.html [ 4 вересня 2008 у Wayback Machine.] The Art of Computer Programming
| Ця стаття не містить . (червень 2011) |
 | Це незавершена стаття про програмування. Ви можете проєкту, виправивши або дописавши її. |
 | Це незавершена стаття з видавничої справи. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Mistectvo programuvannya angl The Art of Computer Programming TAOCP fundamentalna monografiya vidomogo amerikanskogo fahivcya v galuzi komp yuternih nauk ta matematika Donalda Knuta prisvyachena rozglyadu ta analizu najvazhlivishih algoritmiv sho zastosovuyutsya v informatici 1999 roku knigu bulo viznano odniyeyu z dvanadcyati najkrashih fiziko matematichnih monografij stolittya Mistectvo Programuvannya AvtorDonald KnutNazva movoyu originaluThe Art of Computer ProgrammingMovaanglijskaTemaalgoritmZhanrInformatikaVidavnictvoVilyams Addison WesleyVidano1968 vidannya prodovzhuyetsya Napisannya knigi bulo rozpochate avtorom 1962 roku Spochatku planuvalosya vipustiti yiyi odnim tomom ale obsyag materialu viyavivsya nastilki velikim sho kilkist tomiv bulo zbilsheno do semi Pershi tri tomi bulo vidano dosit shvidko pershij tom 1968 r drugij tom 2 1969 roku ta tretij 1973 roku pislya chogo bulo zrobleno perervu do lyutogo 2005 roku v yakomu avtor opublikuvav pershu chastinu chetvertogo tomu Bulo prijnyato rishennya vipuskati inshi chastini chetvertogo tomu priblizno po dvi na rik okremimi vipuskami pislya chogo oficijno vidati ves chetvertij tom Protyagom 2005 2009 rokiv bulo vidano vipuski 0 1 2 3 i 4 a 2011 roku bulo vidano tom 4A do yakogo uvijshla informaciya cih vipuskiv Takozh 2005 roku bulo vidano vipusk 1 MMIX RISC komp yuter dlya novogo tisyacholittya informaciya z yakogo uvijde do novogo chetvertogo vidannya pershogo tomu U 2015 roci buv vidanij vipusk 6 Satisfiability sho mistiv serednyu tretinu majbutnogo tomu 4B 2019 roku bulo vidano vipusk 5 Mathematical Preliminaries Redux Introduction to Backtracking Dancing Links sho mistiv pershu tretinu majbutnogo tomu 4B U 2022 roci buv vidanij tom 4B Chas neobhidnij na povne zavershennya knigi sam avtor ocinyuye v 20 rokiv bezperervnoyi shodennoyi roboti Oskilki Knut zavzhdi vvazhav Mistectvo programuvannya osnovnim proektom svogo zhittya 1990 roku vin vijshov na pensiyu z namirom povnistyu skoncentruvatisya na napisanni vidsutnih chastin i privedennya do ladu isnuyuchih IstoriyaYak viznanij ekspert zi stvorennya kompilyatoriv Knut pochav pisati knigu dlya yih proektuvannya 1962 roku Nezabarom vin usvidomiv sho ohoplennya materialu maye buti nabagato shirshim U chervni 1965 roku vin zavershiv napisannya pershoyi versiyi togo sho vin spochatku hotiv vidati odniyeyu knizhkoyu z dvanadcyati rozdiliv Obsyag rukopisnogo tekstu sklav 3000 storinok Za rozrahunkami Knuta cej obsyag mav vmistitisya na 600 storinkah drukovanogo tekstu ale yak povidomiv jomu jogo vidavec realnij obsyag sklav bi 2000 storinok dzherelo U zv yazku z cim strukturu knigi bulo pereglyanuto na korist kilkoh tomiv po 1 2 rozdili kozhen Vidtodi u zv yazku z postijnim zrostannyam materialu bulo virisheno sho chetvertij tom takozh bude rozbito na okremi knigi 4A 4B 4C a mozhlivo i 4D Ale i cej podil mabut ne bude ostatochnim oskilki rozdili 7 1 i 7 2 1 vzhe v sumi zajmayut ponad 650 storinok 1976 roku Knut pidgotuvav druge vidannya drugogo tomu sho zazhadalo povtornogo naboru Ale tipografske oformlennya yake zastosovuvalosya v pershomu vidanni na toj chas vzhe bulo nedostupnim Shob uniknuti podibnih prikrostej u majbutnomu 1977 roku Knut pochav rozroblyati vlasnu tipografsku sistemu komp yuternogo naboru Za jogo rozrahunkami robota mala trivati ne bilshe shesti misyaciv ale znadobilosya blizko desyati rokiv persh nizh yiyi bulo zaversheno Sistema otrimala nazvu TeX i narazi zastosovuyetsya dlya verstki vsih tomiv Mistectva programuvannya Krim togo zgodom TeX stav faktichnim standartom dlya napisannya statej ta monografij z prirodnichih nauk dzherelo Yak i inshi knigi Knuta Mistectvo programuvannya vidznacheno jogo firmovim znakom za kozhnu pomilku znajdenu v teksti avtor viplachuye odin shistnadcyatkovij dolar tobto 2 56 0x100 centiv v sistemi chislennya za osnovoyu 16 Inshoyu vidmitnoyu osoblivistyu knigi ye velika kilkist vprav dlya samostijnogo vikonannya riznogo stupenya skladnosti pochinayuchi vid prostih zadachok dlya rozigrivu i zakinchuyuchi problemami virishennya yakih vzagali nevidomo Skladnist kozhnoyi vpravi ocineno za chislovoyu shkaloyu vid 0 do 50 Tak u rannih vidannyah ocinkoyu 50 bulo poznacheno Veliku teoremu Ferma ale v tretomu vidanni cya ocinka devalvuvala do 45 oskilki na toj chas teoremu vzhe bulo dovedeno ZmistPochatkovij plan napisannya knigi pripuskav taku rozbivku materialu Tom 1 Osnovni algoritmi Rozdil 1 Osnovni ponyattya Rozdil 2 Informacijni strukturi Tom 2 Napivchiselni algoritmi Rozdil 3 Vipadkovi chisla Rozdil 4 Arifmetika Tom 3 Sortuvannya i poshuk Rozdil 5 Sortuvannya Rozdil 6 Poshuk Tom 4 Kombinatorni algoritmi Rozdil 7 Kombinatornij poshuk Rozdil 8 Rekursiya Tom 5 Sintaksichni algoritmi Rozdil 9 Leksikografichnij poshuk Rozdil 10 Sintaksichnij poshuk Tom 6 Teoriya mov Tom 7 Kompilyatori Faktichno cya shema bula realizovana azh do tretogo tomu vklyuchno Narazi vidano tom 4A yakij mistit pershi rozdili 7 glavi Novi rozdili planuyetsya spochatku vidavati okremimi vipuskami priblizno po 128 storinok oriyentovno po dva vipuski na rik pered vihodom tomu 4A podibnim chinom buli vidani vipuski 0 1 2 3 i 4 Mashinno oriyentovana mova prikladivDokladnishe MIX ta MMIX Prikladi program navedeni v knizi vikoristovuyut MIX asembler priznachenij dlya roboti na gipotetichnomu MIX komp yuteri U tretomu vidanni moralno zastarilij MIX buv zaminenij na MMIX sho maye povnocinnu RISC arhitekturu Isnuye programne zabezpechennya sho zabezpechuye emulyaciyu M MIX mashini na standartnih IBM sumisnih komp yuterah GNU Compiler Collection maye mozhlivist kompilyaciyi C C kodu na cilovu arhitekturu MMIX Bagatoh chitachiv vidshtovhuye fakt vikoristannya movi nizkogo rivnya ale Knut vvazhaye svij vibir vipravdanim oskilki priv yazka do arhitekturi neobhidna dlya togo shob mozhna bulo tochno suditi pro taki harakteristiki algoritmu yak shvidkist vikoristannya pam yati ta in Odnak vnaslidok takogo viboru cilova auditoriya silno zvuzhuyetsya Krim togo obmezhuyetsya galuz yiyi zastosuvannya yak knigi receptiv dlya programistiv praktikiv bagato z yakih ne znayut asemblera a yaksho i znayut to ne vidchuvayut bazhannya perekladati nizkorivnevi algoritmi z knigi na movi visokogo rivnya Chislenni praktichni kerivnictva v yakih toj zhe material vikladayetsya bilsh populyarno vidayut same z ciyeyi prichini dzherelo KritikaOsnovnoyu risoyu monografiyi Knuta sho vigidno vidriznyaye yiyi vid inshih knig prisvyachenih programuvannyu ye nadzvichajno visoko pidnyata planka yakosti materialu j akademichnosti vikladu a takozh glibina analizu rozglyanutih pitan Zavdyaki comu vona stala spravzhnim bestselerom i nastilnoyu knigoyu kozhnogo profesijnogo programista Zhurnal American Scientist vklyuchiv Mistectvo programuvannya do spisku 12 najkrashih fiziko matematichnih monografij XX go stolittya razom z robotami Diraka z kvantovoyi mehaniki Ejnshtejna z teoriyi vidnosnosti Rassela i Uajtheda z osnov matematiki ta deyakimi inshimi Obkladinka tretogo vidannya pershogo tomu knigi mistit citatu Billa Gejtsa Yaksho vi vvazhayete sebe spravdi dobrim programistom prochitajte Mistectvo programuvannya Knuta Yaksho vi zmozhete zrozumiti vsyu cyu pracyu to vam bezumovno slid nadislati meni rezyume Vtim folklor pripisuye ci slova Stivu Dzhobsu VidannyaPotochne vidannya Volume 1 Fundamental Algorithms Third Edition Reading Massachusetts Addison Wesley 1997 xx 650pp ISBN 0 201 89683 4 Volume 1 Fascicle 1 MMIX A RISC Computer for the New Millennium Addison Wesley February 14 2005 ISBN 0 201 85392 2 will be in the fourth edition of volume 1 Volume 2 Seminumerical Algorithms Third Edition Reading Massachusetts Addison Wesley 1997 xiv 762pp ISBN 0 201 89684 2 Volume 3 Sorting and Searching Second Edition Reading Massachusetts Addison Wesley 1998 xiv 780pp foldout ISBN 0 201 89685 0 Volume 4A Combinatorial Algorithms Part 1 Upper Saddle River New Jersey Addison Wesley 2011 xvi 883pp ISBN 0 201 03804 8 Volume 4B Combinatorial Algorithms Part 2 Upper Saddle River New Jersey Addison Wesley 2023 xviii 714pp ISBN 0 201 03806 4Div takozhVstup do algoritmivVinoskihttp www cs faculty stanford edu knuth taocp html 4 veresnya 2008 u Wayback Machine The Art of Computer Programming Cya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno cherven 2011 Ce nezavershena stattya pro programuvannya Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi Ce nezavershena stattya z vidavnichoyi spravi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi