А.А. Степанов. Наибольшая общая мера: последние 2500 лет.
Это стенограмма сделанная мной на лекции Александра Степанова 19 апреля 2010.
Из википедии:
Алекса́ндр Алекса́ндрович Степа́нов (Alexander A. Stepanov) - русско-американский учёный в области информатики и вычислительной техники. Был топ-менеджером компаний SGI, AT&T и Compaq. Наиболее известен как разработчик STL (Standard Template Library) - части стандарта языка C++.
Эта лекция про историю алгоритмов, про их истоки. Александр Александрович очень хороший докладчик, у него завораживающая, размеренная дикция. Может быть местами сумбурно, это стенограмма, но в этом и соль.
Наибольшая общая мера: 2500 лет
View more presentations from sixtyone.
Первый алгоритм изобрел Пифагор (570ВС - 475ВС). В каком-то смысле мы все пифагористы. Родился на острове Самос. Там был тиран Полиграт. И он решил что-то сделать. Нужно поехать искать мудрость. Сперва поехал в Египет, учился у Египетских жрецов. Потом он каким-то образом попал в Вавилон. Там были продвинутые ребята.
Когда он вернулся в Грецию, он основал монастырь. Давайте будем жить вместе "жить чисто, будем верить в переселение душ, не есть мясо". Люди собираются и начинают с ним жить. Особенный монастырь. Вместо того чтобы говорить "Хали Кришна", он говорит давайте изучать "Матэма". Он был первым человеком который сказал что математику нужно изучать. Это очень важно.
Он придумал квадрилиум: четыре дисциплины
- сперва нужно изучить движение звезд: астрономия
- потом нужно изучить как они двигаются: геометрию
- потом мы должны выразить арифметикой геометрию: "теория чисел"
- потом мы эту арифметизацию будем слышать: "Музыка". Музыку сфер.
Он создал математическую теорию музыки. Математически объяснил октаву, устройство гармонии. Когда он это все описал он обнаружил, что одна из этих стрелок не работает. Это средняя стрелка, то что ее очень сложно представить в виде целых чисел.
У Вавилонян были таблички где они собирали числа. Табличка Плимптон 322. Пифагорийцы изобрели идею "доказательства". Они доказали что чего то "нельзя сделать". Они доказали невозможность арифмитезации геометрии. Нашли процесс как можно взять два отрезка и найти общую меру. Возьмем А и Б. Если они равны один из них меряет другой, если не равны тогда возьмем меньший отрезок и отделим от большего. Остановимся ли мы? Остановиться ли алгоритм - обсуждали люди.
Они доказали что он часто не останавливается. Почти никогда не останавливается. Надо очень очень быть "lucky". Они доказали это быстро. Давайте предположим. Изобрели доказательство "от противного". Если взять последовательность нат. чисел, которая уменьшается то она конечна. Давайте возьмем наименьший квадрат и посмотрим что получиться. Сможем ли построить самый наименьший квадрат? Отложим далее на рисунке (см. слайд с геом. построениями). Достраиваем квадрат, отмеряя половину на диагонали и строя перпендикуляр.
Александр Александрович редко читает лекции и говорит по русски. Плохо помнит некоторые слова. Поэтому все время спрашивал у аудитории русский перевод терминов.
Достраивается квадрат. Через равнобедренный треугольник.
Диагональ - d, сторона - s
d/s = (2s-d)/(d-s) оказывается такое отношение
Субтрактивный алгоритм нахождения наибольшего общего делителя. Пифагор открыл и доказал, что корень из 2 - иррационален. Мир кончился! Пифагорийцы нашли алгоритм который не кончается, это плохая вещь. Пифагорийцы развили теорию иррациональности, но они это все считали невероятно секретным. Математика была эзотерической дисциплиной (как программирование сейчас ;) и держалась в секрете. За разглашения выгоняли из свиты. Требовался следующий шаг. Чтобы кто-то сделал математику из секретного учения чем то открытым.
Этого человека звали Платон. (427ВС - 347ВС). Принадлежал замечательной семье, происходил от царей. Был невероятно талантливым, хорошим борцом. Некоторые говорят что выиграл олимпийские игры. Он был замечательный поэт. Некоторые стихи вошли в энциклопедию и вдохновили многих людей.
Вдруг он встретил грязного человека, который ходил по Афинам и задавал вопросики. Люди возмущались. Этого человека звали Сократ. Потом его схватили, и хотели чтобы он выпил яду. А Платон раздавлен и бежит из Афин и опять же как Пифагор едет в Египет, учиться математике, потом в Италию, потом в Вавилонию, много учиться. Потом едет назад в Афины. И открывает в саду Академию. Он сказал что геометрию и математику, все эти дисциплины нужно изучать открытым образом . В Академии учились бесплатно. Это была революционная идея.
Вся математика построена на процессе постоянного вычитания. Платон говорил что никто не должен изучать политические науки пока он не пройдет курс математики. Пифагорийцы сказали что математика центральна. Платон решил прочитать лекцию о Добре. Люди думал что получат денег, станут сильней. А он им начал рассказывать про математику. Они были разочарованы и не дождались конца.
Евклид, взял учебники Платоновской академии и собрал их вместе. Написал "Начало". Эта книга до сих пор актуальна: как тренировать свое мышление.
Делать деньги хорошо, но это не всегда самое главное. Один из царей желая изучить математику сказал Евклиду: "Я хочу executive path", на что Евклид ему ответил "Нет царской дороги в геометрию".
Евклид был хитер. Он решил написать алгоритм как алгоритм, он конечно не читал Кнута. Он знал что алгоритм это процедура которая заканчивается. Он сказал что нужно взять такие отрезки которые соизмеримы, тогда алгоритм закончиться. Жульничество. Алгоритм останавливается когда отрезки равны. Он обнаружил что алгоритм ничего не знает про ноль. Более интересный факт что алгоритм все время вычитает, нельзя ли быстрее. Подумайте как греки писали числа? Буквами писали. Римскими числами (V IV, XX). Попробуйте разделить с остатком (только отнимать, иначе никак). Идея была, но в теории.
Математика в 3-м веке находит высоты, они умеют интегрировать. Захватывают Сиракузы, случайно убивают Архимеда. Рост математики прекращается на 1500 лет.
"Мы Римляне не хотим теорию нам нужно строить империю" - Цицерон. Он нашел могилу Архимеда. А там была нарисована сфера вписанная в цилиндр (правило про 2/3 объема). Римляне переводят Евклида, они сохраняют теоремы и выбрасывают доказательства. Типа они практичные люди.
Следующий шаг нашей истории в ~1000 году. В порту находиться Леонардо Пизанский, отец его работал торговым представителем. Он тоже говорит что нужно учиться. Уезжает к Арабам, тогда они были самые продвинутые. Пишет книгу "Абака", книгу счетов. Пишет там об умножении столбиком. Нашел ноль у арабов, и придумал десятичную систему записи чисел. Придумал все алгоритмы которые сейчас учат в школе: сложение, вычитание, деление. До сих пор это центральная книга в Европейской истории. Его не убили, его даже очень ценили - поразительный факт! Даже назначили большую пенсию.
Император ... когда услышал о работе Пизанского. Сказал ехать из Палермо в Пиза?, чтобы устроить математические соревнования. Пизанский меняет наш алгоритм. Теперь цикл while. Попрежнему беззнаковый тип, нет отрицательного.
Александр Александрович на каждом витке истории приводил код алгоритма определения НОД на С внося всякий раз изменения, в соответствии с контекстом.
Симон Стевин (1548 - 16..) Он был замечательный военный инженер. Нидерланды, когда воевали с Испанией: маленькая республика победила большую империю. Он придумал как управлять шлюзами чтобы топить корабли. Придумал десятичные дроби, векторные вычисления, статику.
Теперь у Стивена появился беззнаковый тип в коде.
Стевин придумал полином. Все знали полином как алгоритм. Вдруг Стевин сказал, что к этому можно относиться как к данным, их можно закодировать позиционно. Как десятичные доли. Их тоже можно складывать, умножать и т.п. Также вы можете их делить с остатком. Уголком. Этот алгоритм оказывается работает для полиномов.
Теперь рациональные числа в алгоритме. Алогритм может быть перенесен из чисел в нечто другое, более обобщенное.
Карл Фридрих Гаусс (1777 - 1855). Начинает играть с делителями. В 6 лет сложил числа от 1 до 100 за одну минуту. По окончании школы был тот же учитель математики что и у Лобачевского. Гаусс его тогда называли принцом математики. В то время Германия становится великим интеллектуальным центром. Когда ему было 18 лет он решил одну из самых интересных задач греков. У Евклида есть как строить с помощью циркуля и линейки можно строить квадрат и другие фигуры. Гаусс узнал что можно и нельзя построить. Узнал что можно построить правильный 17-ти угольник. Число Феруа, Перуа. "Когда умру нарисуйте мне на могиле правильный 17-ти угольник". Немного еще живет. Пишет революционную книгу "Исследования в арифметике" по теории чисел. В книге много нового. Правильные доказательства о фундаментальной теореме арифметики, простое число разбивается на НОД простым образом.
Но не описывает Евклидов алгоритм. Со временем открывает гауссовские числа, выходит в теорию комплексных чисел. Он обнаруживает, что их тоже можно складывать вычитать делить и т.п. и с этими числами тоже. Гаусс расширяет область применения алгоритма, но скрывает его важность.
Лежен Дирихле (1805 - 1857). Работает на кафедре Гаусса. Спит с книгой Гаусса. До тех пор пока он ее полностью не поймет. Со временем он становиться великим математиком. Пишет такую вещь: "Этот алгоритм централен для всей математики". Он понял что вся теория делимости происходит из теории Евклида. Он внезапно понимает то что мы называем "Гаусовскими кольцами". Они тяжелее чем "Евклидовы кольца". Он знает что этот алгоритм существует. Он выясняет что то что Гаусс сделал с комплексными числами можно делать со множеством других систем. "Лекции по теории чисел". Он делает очень много.
Его слушал Рикер Дедекинд. (1831 - 1916) Общая теория алгебраических чисел.
Эмми Нётер. Не получала признания. Слышали про группы, кольца поля - абстрактная алгебра. Это все она. "Она программировала на концепции". Она поняла что можно выбросить все имплементации и можно это все писать на моделях. Город Гетттинген, там было кучу народу связанного с Евклидом. Академик Александров говорил что Эмми Нётер всему всех научила. В Германии не брали женщин преподавать математику. Она была еврейка, ее в америке тоже не взяли в вуз.
Либо Стивен обобщенное программирование придумал либо она. И в алгоритме появляются шаблон функции и тип с объектами. Дедекинд, Нётер, ван дер Варден.
Дональд Кнут. "Знаете это совершенно не трививально, когда вы читаете лекцию и Кнут немножко ругается". "Алгоритм у тебя совершенно не правильный". Если вставить 1 и -1. То он вернет -1, а -1 не является НОД. 1 больше. Я придумал обобщенный ответ: "Зависит от определения". А потом Кнут предложил проверь меньше нуля или больше.
В коде появляется проверка "if (m< 0) m = -m;". Публика в восторге.
И так получается, что переопределяется понятие НОД.
Йосиф Штейн (1961) придумал новый алгоритм. "Мой алгоритм - паблик пропети, а лицо нет" - ответил Иосиф в ответ на запрос о фотографии. Он обнаружил что если два числа четные, то двойку можно забрать. Если одно четное а другое нечетное, то одно можно сдвинуть. Если оба нечетные то одно можно сдвинуть.
"Никогда не думайте что все решено!"
Вариант для многочленов. Числа полиномы, гаусовы числа. Что с ними делать? Как сделать сдвиг? Тут приходит немец Вейлерт. Использовать 1+i как 2! 2-ка самое маленькое простое число. Коэффициенты они units, не интересны. 2-ка не простое в Гаусовских числах. На самом деле мы можем передвинуться к очень глубокой математике.
Два датчанина говорят что этот алгоритм работает для чисел Эйзенштейна.
Зачем все это? Информатика это Математика. Есть только одна серебрянная пуля - математика. Потому что для любой науки единственная сильвер буллет это математика. Отделение социальных навыков то науки. В квадриллиуме первой идет астрономия. Как мы можем знать математику если не знаем природу? Реальность - основание математики. "Потом от астрономии идем к математике". Почему я говорил про Штейна "я верю что в любом хаке есть глубокая теория".
Математика отделилась от физики и люди занимаются не весть знаешь чем. И от расчетов. Потом я узнал что великие математики могли считать. Гаусс мог посмотреть на планету и сказать куда она прилетит.
Владимир Арнольд пишет хорошие книжки по истории математики, читая их можно научиться думать гораздо лучше чем книги о CS.
Читайте Евклида. Евклид построил здание. Книжка о построении правильных многогранников. У Евклида есть архитектура. И она тоже полезна в ПО.
Книга Вирта лучшая книга для начинающих программистов.
UPD: http://clubs.ya.ru/company/replies.xml?item_no=25068&ncrnd=8167 пост в блоге Яндекса со ссылками на видео.