Pull to refresh
0
Edison
Изобретаем успех: софт и стартапы

Дональд Кнут о первых шагах в программировании: Как я провел лето с компьютером, а не с девушками (19,20,21,22/97)

Reading time11 min
Views16K
Original author: Web of Stories
«Суть в том, что это руководство по эксплуатации IBM Model 650 было довольно глупым. Оно и подтолкнуло меня к программированию.»

image


Как я заинтересовался компьютерами? У меня была стипендия на обучение в Кейсовском Технологическом институте, но она покрывала не полную стоимость обучения, а только лишь часть, и поэтому мне пришлось устроиться на работу на неполный рабочий день. У моих родителей не было денег, и я пошел работать в Департамент статистики. Одной из моих обязанностей было управление сортировальной машиной, механической машиной IBM для сортировки перфокарт, и это было довольно увлекательно. Нужно было взять перфокарты и поместить в машину, которая направляла их по разным карманам, затем достать перфокарты в определенном порядке и после проверить результаты и начертить графики. Так что, я чертил графики для Департамента статистики.

EDISON Software - web-development
Мы рады как уже состоявшимся профи, так и амбициозным новичкам.


Определение уровня программиста — крайне важная задача, к которой мы подходим со всей серьёзностью.

Центр разработки программного обеспечения EDISON — это российские таланты и научно-исследовательский потенциал.


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 projective planes
33. Inception of The Art of Computer Programming
34. 1967: a turbulent year
35. Work on attribute grammars and the Knuth-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 emergence 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 any rights to 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. Chess master 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 Knuth-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
Tags:
Hubs:
Total votes 21: ↑19 and ↓2+17
Comments6

Articles

Information

Website
www.edsd.ru
Registered
Founded
Employees
31–50 employees
Location
Россия