Раздел 2.3. Алгоритмический фундамент: Священные войны

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

Спасение пришло не от инженеров, а от двух академиков, которые решили превратить этот хаос в строгую науку.

Время чтения: ~35–40 минут.

Раздел 2.3. Алгоритмический фундамент: Священные войны

К 1968 году индустрия IT оказалась в тупике.

На конференции НАТО в Гармише впервые прозвучал термин «Software Crisis» (Кризис ПО).

Суть кризиса была проста: «железо» развивалось по закону Мура (быстро), а способности программистов — нет. Проекты, подобные OS/360 от IBM, опаздывали на годы и превышали бюджеты в сотни раз.

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

Нужна была Реформация. И её Мартином Лютером стал голландец Эдсгер Дейкстра.

А. Эдсгер Дейкстра: Высокомерие, Перо и Структура

1. Портрет Героя

Эдсгер Вибе Дейкстра был, пожалуй, самым высокомерным и блестящим умом в истории информатики.

Он был физиком-теоретиком. Когда в 1957 году он женился, в графе «Профессия» он написал «Программист». Голландские власти заставили его переписать документы, заявив: «Такой профессии не существует». Ему пришлось написать «Физик-теоретик».

Дейкстра ненавидел компьютеры. Он считал, что они портят чистоту мысли.

Он почти не пользовался клавиатурой. Свои великие труды (знаменитые EWD-рукописи) он писал от руки, перьевой ручкой Montblanc, идеальным каллиграфическим почерком.
Он считал, что отладка (debugging) — это грех. Если вам нужно запустить программу, чтобы найти ошибку, значит, вы плохо подумали. Код должен быть доказан математически, как теорема, еще до того, как он коснется перфокарты.

2. Враг государства №1: Оператор GOTO

В 60-е годы языки программирования (Fortran, COBOL, BASIC) были линейными. Строки нумеровались: 10, 20, 30...

Чтобы управлять логикой («Если А, то сделай Б»), использовался оператор GOTO (Перейти к).

Пример логики тех лет:

Basic

10  ПРОЧИТАТЬ ДАННЫЕ
20  ЕСЛИ ОШИБКА, GOTO 100
30  ВЫЧИСЛИТЬ X
40  ЕСЛИ X > 10, GOTO 10
50  ...
100 НАПЕЧАТАТЬ "ОЙ" И GOTO 10

Это выглядело безобидно в программе на 50 строк.

Но в банковской системе на 100 000 строк это превращалось в ад. Тысячи нитей GOTO переплетались друг с другом. Вы не могли прочитать код сверху вниз. Вам приходилось прыгать глазами по листингу, как кузнечику.

Этот стиль назвали «Спагетти-код».

Бизнес-проблема: Такой код невозможно поддерживать. Исправление ошибки в строке 500 могло случайно сломать логику в строке 10, потому что кто-то прыгнул туда через GOTO из строки 8000. Это делало софт одноразовым.

3. Письмо, начавшее войну (1968)

В марте 1968 года Дейкстра отправляет письмо в редакцию журнала Communications of the ACM.

Редактор Никлаус Вирт (создатель Pascal), желая разжечь дискуссию, дает письму провокационный заголовок, которого не было у Дейкстры:

«Go To Statement Considered Harmful» (Оператор GOTO считается вредным).

Дейкстра писал жестко:

«Качество программистов является обратной функцией от плотности операторов GOTO в их коде».

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

Реакция: Это была ядерная бомба. «Старая гвардия» программистов была в ярости.

«Кто этот академик, чтобы учить нас работать?»
«GOTO — это свобода! Я хочу прыгать куда хочу!»
«Без GOTO код будет работать медленнее!» (В то время каждый такт процессора был на счету).

4. Рождение Структурного программирования

Дейкстра не просто критиковал. Он предложил математическое доказательство (Теорема Бома — Якопини), что любой алгоритм во Вселенной можно записать, используя всего три конструкции:

SEQUENCE: Последовательность (делай А, потом Б).
SELECTION: Ветвление (IF ... THEN ... ELSE).
ITERATION: Цикл (WHILE, FOR).

Вам не нужно прыгать. Вам нужно вкладывать блоки друг в друга, как матрешки.

Это навсегда изменило облик кода. Он стал читаться как проза: сверху вниз. Появились блоки { ... }.

Экономический итог:

Дейкстра спас индустрию от коллапса сложности.

Структурный код можно разбить на изолированные модули.
Это позволило нанимать на проект не 5 гениев, а 500 средних программистов.
Один пишет модуль «Печать», другой — «Расчет», и они не мешают друг другу.
Результат: Появление гигантских систем (Windows, SAP, Oracle), которые не разваливаются под собственным весом.

Б. Дональд Кнут: Монах алгоритмов

Если Дейкстра был пророком, требующим покаяния, то Дональд Кнут стал летописцем, который решил записать все знания мира.

Кнут — человек-легенда. Он живет в Стэнфорде, не пользуется электронной почтой с 1990 года («Моя задача — писать книги, а не отвечать на письма») и обладает аурой дзен-буддистского монаха.

1. Как написать Библию

В 1962 году издательство Addison-Wesley предложило молодому математику Кнуту написать учебник по написанию компиляторов. Контракт был на одну книгу в 12 главах.

Кнут начал писать и ужаснулся. Он понял, что в информатике нет фундамента. Есть набор «хаков» и трюков, которыми обмениваются инженеры IBM и Univac, но нет единой теории. Никто не мог толком объяснить, почему один способ сортировки лучше другого.

Он решил создать эту теорию с нуля.

Проект разросся. Вместо одной книги он запланировал семь томов под названием «Искусство программирования» (The Art of Computer Programming).

Он пишет этот труд уже 60 лет.
На данный момент вышло 4 тома.
Билл Гейтс сказал: «Если вы считаете себя программистом, попробуйте прочесть Кнута. Если вы сможете прочесть всё, пришлите мне резюме».

2. Технический прорыв: Big O Notation

Главный вклад Кнута не в книгах, а в идее «Анализа сложности».

В 60-е годы машинное время стоило безумных денег. Аренда мейнфрейма стоила $500–1000 в час.

Программисты часто писали код, который работал быстро на 10 карточках, но вешал систему на 10 000 карточках.

Кнут популяризировал математическое понятие Big O (О-большое).

Это способ предсказать будущее. Как поведет себя алгоритм, если данных станет в миллион раз больше?

Пример: Поиск в телефонной книге

Представьте, что вам нужно найти человека в телефонной книге Нью-Йорка (1 000 000 номеров).

Алгоритм 1: Линейный поиск ($O(N)$)

Вы открываете первую страницу, читаете имя. Не то. Вторую. Не то. И так до конца.
- В худшем случае вы сделаете 1 000 000 операций.
- Если книга удвоится, время поиска удвоится.
Алгоритм 2: Бинарный поиск ($O(\log N)$)

Вы открываете книгу посередине. Имя на букву "M". Вам нужно "K". Значит, вторая половина книги не нужна. Вы рвете книгу пополам и выкидываете правую часть.

Берете оставшуюся половину. Снова открываете посередине. Снова рвете.
- Чтобы найти имя среди 1 000 000 записей, вам нужно всего 20 разрывов (операций).
- Если книга удвоится (2 млн), вам нужно всего 21 операция.

Бизнес-урок:

Кнут показал, что разница между плохим ($O(N)$) и хорошим ($O(\log N)$) алгоритмом — это не секунды. Это разница между «работает за мгновение» и «не закончит работу до тепловой смерти Вселенной».

Для банка 60-х это означало разницу между прибылью и банкротством из-за счетов за электричество.

3. История с чеками: $2.56

Кнут — перфекционист. Он настолько уверен в своих книгах, что предложил награду.

За каждую найденную ошибку (опечатку или неточность) в его книгах он выплачивает чек на $2.56.

(Почему 2.56? Потому что это "один шестнадцатеричный доллар" — 256 центов).

Эти чеки стали самыми ценными трофеями в мире IT.

Их никто не обналичивает. Их вешают в рамку на стену. Иметь чек от Кнута — значит доказать, что ты умнее самого умного человека в индустрии.

Кнут выписал чеков на тысячи долларов, но со своих счетов он потерял единицы.

4. Перфекционизм: История TeX

Когда в 1976 году вышло второе издание его книги, Кнут был в ярости. Новые методы фотонабора испортили шрифты. Математические формулы выглядели уродливо.

Что сделал Кнут?

Он остановил написание книги на 10 лет.

Он сказал: «Я не буду писать, пока не смогу напечатать это красиво».

Он сел и написал программу TeX (предтеча LaTeX). Он оцифровал шрифты, придумал алгоритмы для кернинга и верстки формул.

Результат: Сегодня 99% всех научных статей в мире (по физике, математике, химии) верстаются в LaTeX. Кнут создал стандарт научной печати просто как побочный продукт своего перфекционизма.

Итог раздела 2.3

В этом разделе мы увидели, как программирование повзрослело.

Дейкстра выбил из голов программистов дурь и научил их дисциплине (Структура).
Кнут дал им линейку, чтобы измерять эффективность своего труда (Алгоритмы).

Эти двое превратили «шаманство с лампами» в Computer Science.

Теперь, когда у нас есть надежный фундамент, мы готовы строить на нем небоскребы. В следующем разделе мы увидим, как на базе этой науки выросла самая мощная монополия XX века — IBM.