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

 

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

Автор: admin от 31-10-2016, 15:30, посмотрело: 322

«Суть в том, что это руководство по эксплуатации IBM Model 650 было довольно глупым. Оно и подтолкнуло меня к программированию.»

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


Как я заинтересовался компьютерами? У меня была стипендия на обучение в Кейсовском Технологическом институте, но она покрывала не полную стоимость обучения, а только лишь часть, и поэтому мне пришлось устроиться на работу на неполный рабочий день. У моих родителей не было денег, и я пошел работать в Департамент статистики. Одной из моих обязанностей было управление сортировальной машиной, механической машиной 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, и затем «обучающая версия» перестала проигрывать «эксперту».

Крестики-нолики довольно скучная игра, ведь вы знаете, как в нее играть и каждая игра заканчивалась ничьей: никто не выиграл — никто не проиграл. Но когда вы ошибаетесь — это увлекает. И я решил, что создам две «обучающиеся версии» и они будут играть друг с другом: сначала они не будут знать ничего об игре, и первые их ходы будут сделаны наугад, вслепую.

Конечно, они будут совершать ошибку за ошибкой, но в итоге кто-нибудь из них выиграет, а кто-то проиграет, и их стратегия немного изменится. И как я выяснил, после сыгранных партий, они начали играть довольно консервативно, партии стали скучными. Вместо того, чтобы совершать обдуманные и рискованные ходы, они играли очень осмотрительно. И тем не менее, написание этой программы стало полезным опытом.

Читать еще





Источник: Хабрахабр

Категория: Программирование

Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

Добавление комментария

Имя:*
E-Mail:
Комментарий:
Полужирный Наклонный текст Подчеркнутый текст Зачеркнутый текст | Выравнивание по левому краю По центру Выравнивание по правому краю | Вставка смайликов Выбор цвета | Скрытый текст Вставка цитаты Преобразовать выбранный текст из транслитерации в кириллицу Вставка спойлера
Введите два слова, показанных на изображении: *