Рубрика «дональд кнут»

Burroughs B5000 — первый компьютер со стековой архитектурой - 1

Начало шестидесятых — эпоха мейнфреймов, время, когда вычислительные машины шагнули за пределы военных лабораторий, превратившись в рабочий инструмент ученых и инженеров. В 1961 году компания Burroughs представила один из самых новаторских компьютеров своего времени — Burroughs B5000. Эта машина радикально отличалась от других мейнфреймов благодаря примененному разработчиками необычному подходу к конструкции и программному обеспечению, и стала первой в истории ЭВМ, в которой была реализована стековая архитектура.
Читать полностью »

Красивый двоичный поиск без ветвления - 1

Недавно я прочитал пост Алекса Мускара Beautiful Binary Search in D. В нём описывается алгоритм двоичного поиска под названием «алгоритм Шора». Я никогда не слышал о нём и его невозможно загуглить, но увидев алгоритм, я думал только об одном: «он без ветвления». Кто знал, что может существовать двоичный поиск без ветвления? Поэтому я занялся его трансляцией в алгоритм для итераторов C++, не требующий индексации на основе единицы или массивов фиксированного размера.

В GCC он более чем в два раза быстрее, чем std::lower_bound, который сам по себе — очень высококачественный двоичный поиск. Цикл поиска прост, а генерируемый ассемблерный код красив. Меня потрясло, что он существует, но им, похоже, никто не пользуется.
Читать полностью »

84 года Дональду Кнуту - 1

На его книгах обучилось не одно поколение программистов, в том числе, и в нашей стране. Созданная им в 70-х годах прошлого века система набора текста TeX до сих пор активно используется по всему миру для верстки высококачественных документов, таких как исследовательские работы, технические руководства и учебники. Его называют пионером в области компьютерных технологий, особенно в сфере языков программирования, а также «отцом анализа алгоритмов». Речь идет о почетном профессоре Стэнфордского университета Дональде Эрвине Кнуте, известном ученом, математике и авторе популярной технической литературы.Читать полностью »

Самый простой (и неожиданный) алгоритм сортировки? - 1

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

1. Алгоритм

Большинству из нас хорошо известны такие простые алгоритмы сортировки, как сортировка пузырьком. По крайней мере, нам так кажется. Оказывались ли вы когда-нибудь в ситуации, когда вам нужно записать псевдокод сортировки пузырьком, и вы осознавали, что он не так прост, как кажется, и с первого раза правильно написать его не удаётся? Нужно внимательно следить за тем, чтобы индексы циклов начинались и заканчивались нужными значениями и не выходили за границы, а также правильно обрабатывать флаговые переменные. Разве не было бы здорово иметь простой алгоритм без всей этой возни? Ниже представлен такой алгоритм, сортирующий массив A из n элементов в неубывающем порядке. Для простоты доказательства массив начинается с 1, то есть имеет элементы A[1],..., A[n].

Алгоритм 1 ICan’tBelieveItCanSort(A[1..n]):

for i = 1 to n do
  for j = 1 to n do
    if A[i] < A[j] then
      swap A[i] and A[j]

Вот, собственно, и всё. Он просто обходит в цикле каждую пару значений (i, j) стандартным способом из двойного цикла for, выполняет сравнение и обмен значениями. Разве можно придумать что-то ещё более простое? Возможно первой реакцией увидевшего этот алгоритм будет что-то типа «это не может быть верно» или «знак неравенства направлен в другую сторону, да и индексы цикла указаны неверно». Но нет, он действительно правильно сортирует в возрастающем порядке.Читать полностью »

image

В течение четверти века великий стэнфордский почётный профессор проводит в декабре особую лекцию «У рождественской ёлки». Приближающийся к своим 82 годам Дональд Кнут снова провёл юбилейную 25-ю лекцию 5 декабря. Он напомнил аудитории, что по-прежнему усердно продолжает работать над книгой, которую пишет последние 57 лет.

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

Поэтому вдвойне необычно увидеть этого великого человека вживую.

У нашего сайта есть собственная рождественская традиция: мы публикуем обзоры и скриншоты с последних лекций Кнута. В 2017 году я описал это как «встречу с любимым родственником на праздники» и «шанс увидеть вживую великий ум».

Лекция этого года не стала исключением.
Читать полностью »

Дональд Кнут, мастер алгоритмов, размышляет над 50 годами работы над своим главным творением, книгой «Искусство программирования», которую не прекращает дополнять

Йода из Кремниевой долины - 1
Дональд Кнут в своём доме в Стэнфорде, Калифорния. Жуткий перфекционист, назначил награду за нахождение ошибки в своих книгах.

Уже полвека стэндфордский специалист по информатике Дональд Кнут, немного напоминающий Йоду – хотя ростом он 193 см и носит очки – занимает доминирующее положение духовного учителя в области алгоритмов.
Читать полностью »

От кипящего свинца до компьютеров: история математической типографики - 1

Математические шрифты шести разных систем печати, изображение Chalkdust

Я всегда считал, что создание печатных математических трудов больше похоже на вид искусства, чем на обычную полиграфию. Тот, кто печатает математические работы, скорее не «типограф», а художник, стремящийся изложить абстрактные данные на двухмерной поверхности. Математические символы сами по себе являются языком, но в основе своей это визуальное представление добытого человеком знания — знания, которое может быть слишком неэффективным, если передавать его через вербальные объяснения. Это делает печать математики ближе к форме визуализации данных, а не обычному печатному тексту.

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

Даже когда современные текстовые процессоры, например, Microsoft Word, обзавелись редакторами уравнений, они обычно были сложны в использовании и часто обеспечивали неудовлетворительные результаты. Хотя LaTeX и похожие на него системы обеспечивают высочайшее качество цифровой математической записи, эти фреймворки создают гораздо более высокий барьер в изучении, чем обычные текстовые процессоры.

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

Дональд Кнут: Я сидел на задних партах и травил шутки, а учителя смирились и не часто били по заднице (1,2,3,7-97) - 1

Дональд Кнут рассказывает про маму и папу, вспоминает о том, как он учился читать, как шкодил в школе. Откровенничает о первом писательском опыте и намекает на «пасхалки» со звездой эротики в своих книгах.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js