Дональд Кнут про перші кроки у програмуванні: Як я провів літо з комп'ютером, а не з дівчатами (19,20,21,22/97)

«Суть в тому, що це керівництво по експлуатації IBM Model 650 було досить дурним. Воно й підштовхнуло мене до програмування.»

image

Як я зацікавився комп'ютерами? У мене була стипендія на навчання в Кейсовском Технологічному інституті, але вона покривала не повну вартість навчання, а лише частину, і тому мені довелося влаштуватися на роботу на неповний робочий день. У моїх батьків не було грошей, і я пішов працювати в Департамент статистики. Однією з моїх обов'язків було управління сортувальної машиною, механічною машиною IBM для сортування перфокарт, і це було досить захоплююче. Потрібно було взяти перфокарти і помістити в машину, яка направляла їх по різних кишенях, потім дістати перфокарти в певному порядку і після перевірити результати і накреслити графіки. Так що, я креслив графіки для Департаменту статистики.

Переклад: Юлія Хаїтова
Підтримка публікації — компанія Edison, яка розробляє геолокаційні ігри з орками і демонами і CRM-системи для координації роботи філіалів.

My interest in graphs and my first experience of a computer


Думаю, я повинен ще щось додати з приводу графіків, поки думка не вислизнула. У старшій школі ціле літо я витратив на… я був захоплений графіками в математиці, знаєте, є аргумент х і функція y, і треба накреслити графік, який на y одиничних відрізків вище, ніж вісь, власне виходить графік функції. З того моменту мені подобаються наочні зображення.

Я був дуже захоплений думкою, що зможу почати з зображення, яке б хотів отримати в результаті, і підібрати таке рівняння, графік якого дозволили б це зробити. Так що, я витратив літо на те, щоб розбиратися в побудові графіків. Я креслив сотні і сотні графіків в той час. В якості рівняння я міг взяти, наприклад, квадратний корінь з x^3 + 5x мінус ще яке-небудь число, і будував його графік.

У мого батька була маленька рахункова машина, на якій я міг обчислювати корені. Вона навіть распечатывала результат. Батько був бухгалтером, так що машинка навіть распечатывала підсумок. Я користувався нею для множення і інших арифметичних дій. Потім, скажімо, я міняв x^3 + 5x x^3 + 4x і креслив вже новий графік, запам'ятовуючи, як виглядають різні графіки.

У мене не було математичного аналізу в школі, я цього просто не знав, але зате я вмів будувати графіки рівнянь. Це приводило мене в захват. Я так наполегливо працював над цим, будував графіки на помаранчевій міліметровому папері, від цього навіть починала боліти голова. Я думаю, що приблизно в цей час я почав носити окуляри, все за графіків. Але я отримав хоч якийсь досвід в побудові, і мені подобався цей розділ математики, навіть коли я вчився в старшій школі.

А потім я отримав першу роботу на півставки в Кейсовском Технологічному Інституті, на якій я повинен був креслити графіки для фахівців за статистикою. Це було здорово, і недалеко від сортувальної машини стояв новий комп'ютер або, як тоді називали «штучний інтелект», IBM Model 650.

Це була перша модель комп'ютера масового виробництва: їх випустили понад 1000. Ну, а до цього, комп'ютери не випускалися партіями, в яких було б більше 30 примірників. І коли цей комп'ютер привезли, це було в середині мого першого року навчання в інституті, його встановили в кімнаті, на поверх нижче кабінету, в якому я працював. Я міг навіть бачити комп'ютер через вікно кабінету.

Одного разу один працівник помітив мене, заглядывающегося на комп'ютер, і запросив увійти. Він пояснив мені, як працює цей пристрій. Я був вражений, адже цей комп'ютер міг робити стільки речей, на відміну від лічильної машини, яку мені показував батько, тому і вирішив ознайомитися з керівництвом по експлуатації.

Незабаром він дозволив мені пробивати отвори на перфокарти, які призначалися для комп'ютера. Розумієте, я знав, як керувати сортувальної машиною, але в той момент я робив перфокарти з комп'ютерними програмами. І так я почав дізнаватися про те, що ж знаходиться всередині цього апарату.

How I got interested in programming


Я прочитав керівництво по експлуатації від IBM, і воно містило в собі приклади програм, і я задумався про те, як можна поліпшити процес написання програм. Я подумав: «Ну, так, ці програми працюють, але якщо дещо змінити, то стане навіть краще». Це додало мені впевненості в тому, що може бути, у мене є талант до програмування.

Якщо б тоді в керівництві не було тих невдалих прикладів, я б, швидше за все, навіть не зацікавився написанням програм, тому що не був так упевнений в собі і, злякавшись, просто відмахнувся: «О, я не коли не додумався до такого». Але суть в тому, що це керівництво по експлуатації було досить дурним. Воно й підштовхнуло мене до програмування, адже я, скажімо, міг досягти успіху в цьому.

Так я і почав цікавитися комп'ютерами під час першого року навчання в інституті. І потім, коли я вступив у братство, у одного з учасників була проблема із завданням, яку йому треба було терміново вирішити: знайти корінь рівняння 5 ступеня. Я тоді вже знав про програму під назвою « Bell Interpretive System », яка легко зможе вирішити його проблему, т. к. він, знаєте, не хотів зробити самостійно.

Так що, я написав програму для свого «брата», яка б зробила одне з його завдань за нього. І програма працювала. Мені важко було в це повірити, але це було так. І він був щасливий з-за цього. До того ж, я почав більше спілкуватися з людьми з Комп'ютерного центру, коли вони стали дозволяти мені використати цей IBM апарат ночами.

І десь між першим і другим курсом я підробляв в Комп'ютерному центрі. Вони насправді дозволяли нам писати програмне забезпечення, яким інші люди — інші студенти будуть користуватися.

Перша комп'ютерна програма, яку я написав, полягала в наступному: розкладання числа на прості множники. Введіть число через консоль, а саме поворотний перемикач, який можна було пересунути до числа, наприклад, 100, і потім відбувався висновок наступних даних: 100=2*2*5*5. Так можна було обчислити прості множники числа, які було введено через консоль.

У мене до цих пір збереглася копія цієї моєї програми. Спочатку все починалося з приблизно 60 або 70 команд у програмі, а через 2 тижні, коли вона нарешті правильно запрацювала, в ній було 130, думаю, що я виправив близько 200 помилок за цей час.

Я маю на увазі, що навчався не тільки програмування, але і виправлення помилок. Що може піти не так, коли ти просто… Ну, я не так вже й багато знав про програмуванні тоді, але я багато чому навчився завдяки цій практиці, написання програми обчислення простих множників числа.

Learning how to program on the IBM 650


Так само я зрозумів деякі речі, наприклад, був десятковий комп'ютер, який працював не в двійковій системі числення, а в десятковій; і в підсумку могли вийде навіть десятизначні числа. Я зміг навчиться користуватися таким комп'ютером, хоча він був дуже повільним.

Процес поділу займав у нього, приблизно, близько 4 мілісекунд, в той час, як зараз комп'ютери працюють у мільйони разів швидше. За сьогоднішніми стандартами це був неймовірно повільний комп'ютер, у якого навіть не було можливості виробляти кілька процесів поділу одночасно.

І знаходження множників відбувалося наступним чином: спочатку розділити це число на два — не підходить. На три? Немає. На чотири? Немає. І так до тих пір, поки не вийде. Зараз же можна досить просто підібрати найбільшу десятизначне просте число, а тоді це займало купу часу, тому потрібно було хоч трохи прискорити програму.

Мені не слід було ділити спочатку на два, потім на три, чотири, п'ять, я ж міг пропустити всі парні числа, якщо вихідне число не ділиться на 2 і на 4. І я повинен був виконати такого роду речі, щоб прискорити процес. Спочатку я не розумів, що мені не потрібно ділити на всі можливі числа, адже якщо у числа взагалі є множники, то найменший множник буде менше квадратного кореня цього числа або мати приблизно однакове значення. Саме так я зрозумів, що мені треба трохи змінити алгоритм у програмі.

Однією з найбільш явних помилок в програмі, яка зайняла у мене багато часу на виправлення, полягала в тому, що раптом у кількості є багато простих множників? Як виявилося, я міг пробити тільки 9 множників на перфокарте, я мені довелося переробляти програму, адже у чисел може бути і більше 30 множників. І я змінив так, що тепер відповіді пробивалися не на одній карті, а на чотирьох.

І тим не менш, це було… Я просто хочу пояснити чому ця програма по знаходженню множників була настільки корисна для мене в той час. І я ж написав її в кінці першого курсу, мені дозволяли проводити ночі, сидячи за цим апаратом, перемикаючи важелі, натискаючи на кнопки, і адже Кейсовский Технологічний інститут дозволяє студентам практикуватися. Викладачі дозволяли нам користуватися комп'ютерами самостійно, працювати ночами, засипати в кабінетах і писати програми, якими б користувалися інші студенти.

В Стенфордському університеті все було інакше. В Стенфорді, як я пізніше з'ясував, були працівники від IBM, яким треба було здавати роботу, щоб вони пропустили її безпосередньо через апарат, тому отримати результати можливо було тільки на наступний день.

У Кейсовском інституті було дозволено робити все самостійно, вони навіть не переживали, що ми можемо що-небудь зламати, адже ми відкривали панелі, коли папір або карти застрягали і все таке. А ми були тільки першокурсниками! Я думаю, що Кейс і Дартмут були єдиними університетами в ті дні, які так ліберально відносилися до своїх студентів і дозволяли користуватися технікою самостійно.

Writing a tic-tac-toe program


Влітку я працював у Комп'ютерному центрі, так що я не був удома в Мілуокі, хіба що тільки пару днів. Та це було до того, як я зустрів тих дівчат на другому курсі, про які я вже говорив. Так що, я провів літо з комп'ютером. Моєю другою програмою було перетворення з десяткової системи у інші системи числення, але це було досить швидко. Третя програма, над якою я витратив більшу кількість часу, була гра «Хрестики-нулики».

Пізніше я дізнався, що багато вчені працювали на цій грою. Чарльз Беббідж, англійський математик, який винайшов першу машину, яка могла б грати в «Хрестики-нулики» в 1800-х. Денні Хілліс зробив автомат для гри в «Хрестики-нулики» з дитячого конструктора «Tinkertoys», який зараз виставлений в бостонському Музеї науки. І тим не менше, я вирішив, що напишу комп'ютерну програму для цієї гри. це було досить проблематично.

Я не використовував «Tinkertoys», але у IBM 650 була інша цікава особливість: він працював не тільки в десятковій системі, з 10-ти значними числами, але у нього було всього 2000; загальна пам'ять його була, дайте подумати, скільки? 5 байтів? Так, всього 10 Кбайт пам'яті. А зараз якщо у вас немає 10 Гбайт, або хоча б 10 Мбайт, то це кінець. Ви навіть не зможете скачати Microsoft Windows, якщо у вас немає сотень Мбайт, а у нас тоді загальної пам'яті було всього 10 Кбайт.

І я хотів, щоб машина могла грати в хрестики-нулики проти мене. І я написав три рівня складності. Перший рівень- «експерт», зі стратегією, в якій я був упевнений.

Який же був другий? Я вже і не пам'ятаю, але ось третій був найцікавіший. Це була «навчається версія»: машина починала гру, не знаючи нічого, і вона сама навчалася під час гри, запам'ятовувала всі можливі позиції на полі.

Чи можна було вмістити це в 10Кбайт. Кожен раз при програші під час гри, вона говорила щось на кшталт: «я зробив помилку, ходи супротивника були хороші», а при виграші: «Мої ходи були гарні, а ходи супротивника — ні». Вона могла підлаштовуватися.

Кожному рівню складності відповідала певна цифра, гра могла початися на 4, і якщо ви виграли, то наступна буде вже 5, а якщо програли, то 3. І якщо ви починали використовувати різні стратегії, то вона підбирала ті ходи, які здавалися найбільш підходящими.

У мене пішов місяць на написання цієї програми… Я багато чому навчився за цей час, і після я намагався навчити «навчальну версію» грі, використовуючи версію «експерт». Як багато раз «експерт» грав з «навчальної версією»? Я думаю, близько 120, і потім «навчальна версія» перестала програвати «експерту».

Хрестики-нулики досить нудна гра, адже ви знаєте, як у неї грати і кожна гра закінчувалася нічиєю: ніхто не виграв ніхто не програв. Але коли ви помиляєтеся — це захоплює. І я вирішив, що створю дві «навчаються версії» і вони будуть грати один з одним: спочатку вони не будуть знати нічого про гру, і перші їх кроки будуть зроблені навмання, наосліп.

Звичайно, вони будуть робити помилку за помилкою, але в підсумку хто-небудь з них виграє, а хтось програє, і їх стратегія трохи зміниться. І як я з'ясував, після зіграних партій, вони почали грати досить консервативно, партії стали нудними. Замість того, щоб робити обдумані і ризиковані ходи, вони грали дуже обачно. І тим не менш, написання цієї програми стало корисним досвідом.

Читати ще
Список 97 відеороликів з історіями Дональда КнутаПлейлист на Youtube

1. Family history
2. Learning to read and school
3. My mother
4. My parents' finances
5. Interests in high school
6. Being a nerd of nerds at high school
7. My sense of humor
8. The Potrzebie System of Weights and Measures
9. Feeling the need to prove myself
11. University life: my basketball management system
12. University life: the fraternity system
13. Meeting my wife Jill
14. Bible study at university and a time of personal challenge
15. Extra-curricular activities at Case
16. Taking graduate classes at Case
17. Physics, welding, astronomy and mathematics
18. My maths teacher at Case and a difficult problem
19. My interest in graphs and my first experience of a computer
20. How I got interested in programming
21. Learning how to program on the IBM 650
22. Writing a tic-tac-toe program
23. Learning about Symbolic Optimum Assembly programs
24. The Internal Translator
25. Adding more features to RUNCIBLE
26. Wanting to be a teacher and why I chose to go to Caltech
27. Writing a compiler for the Burroughs Corporation
28. Working for the Burroughs Corporation
29. Burroughs Corporation
30. My interest in context-free languages
31. Getting my PhD and the problem of symmetric block designs with…
32. Finding a solution to an open problem about проективної planes
33. Inception of The Art of Computer Programming
34. 1967: a turbulent year
35. Work on attribute grammars and the Батіг-Bendix Algorithm
36. Being creative in the forest
37. A new field: analysis of algorithms
38. The Art of Computer Programming: underestimating the size of the...
39. The successful first release of The Art of Computer Programming
40. Inspiration to write Surreal Numbers
41. Writing Surreal Numbers in a hotel room in Oslo
42. Finishing the Surreal Numbers
43. The є поява of computer science as an academic subject
44. I want to do computer science instead of arguing for it
45. A year doing National Service in Princeton
46. Moving to Stanford and wondering whether i'd made the right choice
47. Designing the house in Stanford
48. Volume Three of The Art of Computer Programming
49. Working on Volume Four of The Art of Computer Programming
50. Poor quality typesetting on the second edition of my book
51. Deciding to make my own typesetting program
52. Working on my typesetting program
53. Mathematical formula for letter shapes
54. Research into the history of typography
55. Working on my letters and problems with the S
56. Figuring out how to typeset and the problem with specifications
57. Working on TeX
58. Why the designer and the implementer of a program should be the…
59. Converting Volume Two to TeX
60. Writing a users' manual for TeX
61. Giving the Gibbs lecture on my typography work
62. Developing Metafont and TeX
63. Why I chose not to retain rights to any TeX and transcribed it to…
64. Tuning up my fonts and getting funding for TeX
65. Problems with Volume Two
66. Literate programming
67. Re-writing TeX using the feedback I received
68. The importance of stability for TeX
69. LaTeX and ConTeXt
70. A summary of the TeX project
71. A year in Boston
72. Writing a book about the Bible
73. The most beautiful 3:16 in the world
74. Master Chess playing at Adobe Systems
75. Giving a lecture series on science and religion at MIT
76. Back to work at Stanford and taking early retirement
77. Taking up swimming to help me cope with stress
78. My graduate students and my 64th birthday
79. My class on Concrete Mathematics
80. Writing a book on my Concrete Mathematics class
81. Updating Volumes One to Three of The Art of Computer Programming
82. Getting started on Volume Four of «The Art of Computer...
83. Two final major research projects
84. My love of writing and a lucky life
85. Coping with cancer
86. Honorary doctorates
87. The importance of awards and the Kyoto Prize
88. Pipe organ music is one of the great pleasures of life
89. The pipe organ in my living room
90. Playing the organs
91. An international symposium on algorithms in the Soviet Union
92. The Батіг-Morris-Pratt algorithm
93. My advice to young people
94. My children: John
95. My children: Jenny
96. Working on a series of books of my collected papers
97. Why I chose analysis of algorithms as a subject

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.