Начало шестидесятых — эпоха мейнфреймов, время, когда вычислительные машины шагнули за пределы военных лабораторий, превратившись в рабочий инструмент ученых и инженеров. В 1961 году компания Burroughs представила один из самых новаторских компьютеров своего времени — Burroughs B5000. Эта машина радикально отличалась от других мейнфреймов благодаря примененному разработчиками необычному подходу к конструкции и программному обеспечению, и стала первой в истории ЭВМ, в которой была реализована стековая архитектура.
Читать полностью »
Рубрика «дональд кнут»
Burroughs B5000 — первый компьютер со стековой архитектурой
2024-10-25 в 7:47, admin, рубрики: algol, apl, B5000, Burroughs, COBOL, fortran, дональд кнут, Чарльз ХоарКрасивый двоичный поиск без ветвления
2023-05-02 в 6:41, admin, рубрики: binary search, алгоритм Шора, Алгоритмы, двоичный поиск, дональд кнут, ПрограммированиеНедавно я прочитал пост Алекса Мускара Beautiful Binary Search in D. В нём описывается алгоритм двоичного поиска под названием «алгоритм Шора». Я никогда не слышал о нём и его невозможно загуглить, но увидев алгоритм, я думал только об одном: «он без ветвления». Кто знал, что может существовать двоичный поиск без ветвления? Поэтому я занялся его трансляцией в алгоритм для итераторов C++, не требующий индексации на основе единицы или массивов фиксированного размера.
В GCC он более чем в два раза быстрее, чем std::lower_bound, который сам по себе — очень высококачественный двоичный поиск. Цикл поиска прост, а генерируемый ассемблерный код красив. Меня потрясло, что он существует, но им, похоже, никто не пользуется.
Читать полностью »
Самый простой (и неожиданный) алгоритм сортировки?
2022-02-09 в 10:35, admin, рубрики: алгоритм, Алгоритмы, Блог компании Sportmaster Lab, дональд кнут, Программирование, сортировкаПредставляем вашему вниманию чрезвычайно простой алгоритм сортировки. Может показаться, что он очевидно ошибочен, но мы докажем, что на самом деле он корректен. Мы сравним его с другими простыми алгоритмами сортировки и проанализируем некоторые его любопытные свойства.
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, выполняет сравнение и обмен значениями. Разве можно придумать что-то ещё более простое? Возможно первой реакцией увидевшего этот алгоритм будет что-то типа «это не может быть верно» или «знак неравенства направлен в другую сторону, да и индексы цикла указаны неверно». Но нет, он действительно правильно сортирует в возрастающем порядке.Читать полностью »
Юбилейная лекция Дональда Кнута «У рождественской ёлки»
2020-01-06 в 18:07, admin, рубрики: donald knuth, the art of programming, дональд кнут, Занимательные задачки, Искусство программирования, математика, число пиВ течение четверти века великий стэнфордский почётный профессор проводит в декабре особую лекцию «У рождественской ёлки». Приближающийся к своим 82 годам Дональд Кнут снова провёл юбилейную 25-ю лекцию 5 декабря. Он напомнил аудитории, что по-прежнему усердно продолжает работать над книгой, которую пишет последние 57 лет.
Книга «Искусство программирования» в среде программистов считается одним из самых комплексных исследований алгоритмов. Согласно веб-сайту Стэнфордского университета, эту книга является одним из лучших научных трудов века. «Из-за моего насыщенного писательского графика мне приходится вести отшельническую жизнь», — пишет Кнут на своём личном сайте.
Поэтому вдвойне необычно увидеть этого великого человека вживую.
У нашего сайта есть собственная рождественская традиция: мы публикуем обзоры и скриншоты с последних лекций Кнута. В 2017 году я описал это как «встречу с любимым родственником на праздники» и «шанс увидеть вживую великий ум».
Лекция этого года не стала исключением.
Читать полностью »
Йода из Кремниевой долины
2019-01-04 в 9:00, admin, рубрики: дональд кнут, Искусство программирования, ПрограммированиеДональд Кнут, мастер алгоритмов, размышляет над 50 годами работы над своим главным творением, книгой «Искусство программирования», которую не прекращает дополнять
Дональд Кнут в своём доме в Стэнфорде, Калифорния. Жуткий перфекционист, назначил награду за нахождение ошибки в своих книгах.
Уже полвека стэндфордский специалист по информатике Дональд Кнут, немного напоминающий Йоду – хотя ростом он 193 см и носит очки – занимает доминирующее положение духовного учителя в области алгоритмов.
Читать полностью »
От кипящего свинца до компьютеров: история математической типографики
2017-11-28 в 7:05, admin, рубрики: гутенберг, дональд кнут, история печати, линотип, монотип, Научно-популярное, печатьМатематические шрифты шести разных систем печати, изображение Chalkdust
Я всегда считал, что создание печатных математических трудов больше похоже на вид искусства, чем на обычную полиграфию. Тот, кто печатает математические работы, скорее не «типограф», а художник, стремящийся изложить абстрактные данные на двухмерной поверхности. Математические символы сами по себе являются языком, но в основе своей это визуальное представление добытого человеком знания — знания, которое может быть слишком неэффективным, если передавать его через вербальные объяснения. Это делает печать математики ближе к форме визуализации данных, а не обычному печатному тексту.
Неважно, насколько тяжело было создавать печатный текст — создание печатных математических символов всегда было сложнее. В доцифровую эпоху наполненные уравнениями тексты называли «штрафной копией», потому что подготовка математической записи для печатных прессов требовала значительных лишних затрат времени и денег.
Даже когда современные текстовые процессоры, например, Microsoft Word, обзавелись редакторами уравнений, они обычно были сложны в использовании и часто обеспечивали неудовлетворительные результаты. Хотя LaTeX и похожие на него системы обеспечивают высочайшее качество цифровой математической записи, эти фреймворки создают гораздо более высокий барьер в изучении, чем обычные текстовые процессоры.
Но все эти современные «трудности» в гораздо большей степени вина гедонистической адаптации, чем любого из доступных нам инструментов. Нам намного легче, чем любой другой ступени цивилизации, и я считаю, что для пишущих математические тексты очень важно иметь хотя бы базовое знание истории математической печати.
Читать полностью »
Дональд Кнут: Я сидел на задних партах и травил шутки, а учителя смирились и не часто били по заднице (1,2,3,7-97)
2016-10-13 в 11:53, admin, рубрики: edisonsoftware, Блог компании Edison, дональд кнут, Карьера в IT-индустрии, обучение, Программирование, чтение, чувство юмора, метки: дональд кнут
Дональд Кнут рассказывает про маму и папу, вспоминает о том, как он учился читать, как шкодил в школе. Откровенничает о первом писательском опыте и намекает на «пасхалки» со звездой эротики в своих книгах.
Читать полностью »