Что умеет программа

Начнём сразу с кода. Под этим абзацем — программа из одной строки. Нажмите «Запустить».

Пока вы читали эту фразу, строка улетела на наш сервер. Там для неё поднялась песочница, маленький изолированный компьютер. Python выполнил команду, и ответ вернулся к вам. Две звёздочки ** значат «в степени». На экране произведение тысячи двоек, все 302 цифры до единой. Калькулятор в телефоне показал бы только первые цифры и перешёл бы на приблизительную запись.

Код в этом учебнике можно и нужно менять. Щёлкните по строке, поставьте вместо 1000 что-нибудь своё — хоть 10000 — и запустите ещё раз. Сломать ничего нельзя: каждая ячейка работает в одноразовой песочнице, которую сервер выбрасывает после запуска. Кнопка со стрелкой по кругу вернёт исходный текст.

Дальше пять удивлений. Объяснять их сейчас мы не будем, для этого есть остальные 65 глав. Пока достаточно увидеть, на что похожа computer science, прежде чем мы начнём её строить.

Удивление первое: двадцать вопросов

Загадайте целое число от одного до миллиона. Любое: номер квартиры, год рождения бабушки, число просмотров вашего последнего видео. Машина будет задавать вопросы вида «больше ли оно, чем…», а вы — честно отвечать. Спорим, ей хватит двадцати вопросов?

Двадцати вопросов на миллион вариантов хватает потому, что каждый ответ отбрасывает половину оставшихся чисел. После первого вопроса их полмиллиона, после второго — двести пятьдесят тысяч, после десятого — меньше тысячи, после двадцатого — одно. Удвойте единицу двадцать раз, и она перевалит за миллион: $2^{20} = 1\,048\,576$.

Вот та же игра в виде программы на Python. Запустите её, и сервер будет задавать вопросы в поле под кодом. Пока вы думаете, программа там, на сервере, стоит и ждёт вашего ответа.

В этой программе нет перебора. Если бы она спрашивала подряд, «это 1? это 2? это 3?», то в худшем случае задала бы миллион вопросов. А так ей хватает двадцати на том же компьютере: всё решает идея. У идеи есть имя, двоичный поиск, и вы встретите её ещё много раз: так ищут слово в словаре, коммит с ошибкой в истории git, строку в базе данных из миллиарда записей.

Удивление второе: гонка

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

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

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

Процессор вдвое быстрее ускорит пузырёк вдвое, а другая идея — в тысячи раз, и чем больше данных, тем больше выигрыш. Поэтому программисты так много думают об алгоритмах. Придумывают их люди, причём иногда раньше машин: сортировку слиянием Джон фон Нейман описал в 1945 году, когда компьютер, способный её выполнить, ещё не построили.

Удивление третье: дерево из десятка строк

Программы умеют не только считать. Следующая рисует у вас на странице, хотя выполняется на сервере. Python отправляет команды «шагни, повернись, подними перо», а браузер выводит черепашку, которая их исполняет.

Функция branch рисует ствол, а потом… вызывает саму себя дважды, для левой и правой ветки, каждая почти на треть короче. Те тоже вызывают себя, и так девять уровней, пока не получится 511 веток. Ни одна строка программы не говорит, где будет 300-я ветка: дерево вырастает из правила. Приём называется рекурсией, и через несколько глав вы будете рисовать такие картинки сами. Пока попробуйте поменять 25 на 40, а 0.72 — на 0.6.

Удивление четвёртое: программа, которая печатает себя

Над этой задачей когда-то ломали голову студенты: написать программу, которая выводит собственный текст символ в символ. Читать файл с диска нельзя, это жульничество. На первый взгляд задача невыполнима: чтобы напечатать свой текст, программа должна содержать его внутри, а значит, быть длиннее себя.

Тем не менее такая программа на Python занимает две строки. Запустите её, и под выводом появится сравнение с исходником.

Строка s — это шаблон программы с дыркой посередине, а в дырку программа подставляет… саму эту строку. Такие программы называют куайнами: имя придумал Дуглас Хофштадтер в книге «Гёдель, Эшер, Бах» в честь философа Уилларда Куайна, который изучал предложения, говорящие о самих себе. Попробуйте изменить в программе хоть один символ и убедитесь, что совпадение ломается, а потом подумайте, как его починить. Подробно мы разберём куайн в главе 7: это первый из больших вопросов курса.

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

Удивление пятое: три строки, которые никто не понимает

Возьмите любое натуральное число. Если оно чётное — разделите пополам. Если нечётное — умножьте на три и прибавьте единицу. С результатом сделайте то же самое. И так далее.

Из 6 получится 3, потом 10, 5, 16, 8, 4, 2, 1. Из 7: 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Похоже, любое число рано или поздно скатывается к единице. Попробуйте 27.

Скромная двадцать семёрка взлетает до 9232 и только через 111 шагов падает к единице. У соседних чисел пути совсем другие:

Доходит ли до единицы каждое число? Это гипотеза Коллатца, ей почти девяносто лет. Компьютеры проверили все числа до $2^{71}$ — это больше двух триллионов миллиардов, — и каждое дошло. Только перебор ничего не доказывает: где-то дальше может найтись число, которое улетит в бесконечность или зациклится. Пал Эрдёш, один из самых плодовитых математиков XX века, по рассказам коллег говорил о ней: «Математика ещё не готова к таким задачам».

Вопрос здесь странный: мы спрашиваем не о том, что вычислит программа, а о том, закончит ли она когда-нибудь работу. Для трёх строк про числа ответа никто не знает. Можно ли отвечать на такой вопрос для любой программы, вы узнаете в главе 56, и это один из главных сюрпризов курса.

Так что же такое computer science

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

Про это есть фраза, которую обычно приписывают Эдсгеру Дейкстре: «Компьютерная наука занимается компьютерами не больше, чем астрономия — телескопами». В текстах Дейкстры её не нашли, и кто её автор, неизвестно, но мысль верная. Computer science изучает вычисление: что можно вычислить, как сделать это быстро и надёжно, как устроены машины, которые вычисляют, и где у вычислений проходят пределы.

Этот курс построен как спуск и подъём. Сначала вы научитесь писать программы и думать алгоритмами. Потом спуститесь от строчки на Python к процессору и выключателям, из которых он сделан. Потом подниметесь обратно: операционная система, сети, базы данных, языки программирования. В части VIII вы напишете компилятор для собственного учебного компьютера «Искра-8», который соберёте в части IV. А под конец спросите, чего не сможет никакой компьютер, и узнаете, как на этом держатся шифры.

Одиннадцать вопросов, на которые ответит курс

У каждой части курса есть свой большой вопрос, похожий на головоломку, и часть заканчивается ответом на него. Ждать до конца не придётся: первый ответ будет уже в седьмой главе, дальше — примерно каждые шесть глав.

1. Может ли программа напечатать саму себя? Вы только что видели, что может. Как она устроена, разберём в главе 7, когда научимся работать с текстом.
2. Почему одна программа решает задачу за секунду, а другая не справится и до конца Вселенной? Вы видели это в гонке. Считать скорость заранее научимся в главе 13.
3. Как навигатор за секунду находит кратчайший путь среди миллионов дорог? Мы сами построим такой — в главе 24.
4. Как из выключателей получается компьютер? Соберём его из логических вентилей — в главе 32.
5. Как сотня программ работает на двух ядрах и не ломает друг другу данные? Глава 39.
6. Как миллиарды компьютеров работают вместе, если ни один из них не главный? Глава 44.
7. Как поисковик за долю секунды находит нужное среди миллиардов страниц? Построим поисковик по учебникам этого сайта — глава 48.
8. Как программа понимает другую программу? Вы напишете интерпретатор и компилятор для своей машины — глава 52.
9. Есть ли задачи, которые не решит никакой компьютер? Да, такие есть, и доказательство помещается на страницу — глава 56.
10. Как договориться о секрете, если каждое слово подслушивают? Глава 60.
11. Может ли машина научиться тому, чему её не учили? Глава 63.

Как устроены ячейки и задачи

Всё, что нужно для курса, — этот браузер. Ничего устанавливать не надо: код выполняет наш сервер.

• Запустить отправляет код на сервер; вывод приходит построчно, по мере работы программы. Сочетание Ctrl+Enter (на Mac — ⌘+Enter) делает то же самое из редактора.
• Если программа спрашивает что-то через input(), под кодом появляется поле для ответа.
• Шаги записывает выполнение программы и даёт пройти её строка за строкой: видно, какая строка сейчас выполняется, какие переменные существуют и на что они указывают. Особенно она пригодится в главах о функциях и рекурсии.
• На каждую программу у сервера есть лимиты: десять секунд, 256 МБ памяти, никакого интернета. Бесконечный цикл не повесит ни страницу, ни сервер: его остановят по лимиту времени.
• Задачи отличаются от ячеек кнопкой «Проверить»: сервер прогоняет ваше решение по скрытым тестам и показывает, на каком входе оно ошиблось. Прогресс сохраняется в этом браузере и виден на странице всех задач.

Первая задача совсем лёгкая, попробуйте.

Куда дальше

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