Математика для программистов: от основ CS50 до алгоритмов Тьюринга

Ошибка на бирже Ванкувера, стоившая индексу более половины его стоимости за 22 месяца, произошла из-за банальной математической погрешности — усечения цифр вместо их округления. Как подчеркивают Дэвид Малан и Том Кроуфорд в новом курсе CS50 по математике для программистов, залог надежности любого алгоритма кроется в понимании фундаментальных числовых множеств, от нуля в натуральных числах до вычисляемых концепций Алана Тьюринга.

🔢 Математика для CS50: От мифов к основам счисления 36:42

На протяжении многих лет одним из самых популярных вопросов к команде курса CS50 был: «Какая математическая база необходима, чтобы начать изучение компьютерных наук?» . Многие потенциальные студенты опасались, что, не будучи «математиками» по складу ума, они не справятся с программированием . Профессор Дэвид Малан (David J. Malan) неизменно отвечал на это уверенным «да» , однако долгое время у курса не было собственного специализированного ресурса, который бы закрывал пробелы в школьных знаниях. Ситуация изменилась с анонсом нового курса «Math for Introductory CS», созданного совместно с популяризатором науки и преподавателем Оксфорда и Кембриджа Томом Кроуфордом (Tom Crawford) .

Введение в курс математики для CS50 36:42

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

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

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

Базовые классификации и множества чисел 41:40

Для работы с данными программисту важно понимать, с каким типом чисел он имеет дело. Том Кроуфорд предлагает начать с самого интуитивно понятного множества — натуральных чисел (Natural numbers) .

Натуральные числа ($\mathbb{N}$): Это числа, используемые для простого счёта объектов: 0, 1, 2, 3 и так далее . Кроуфорд делает важное замечание: в математическом сообществе ведутся споры о включении нуля в это множество, однако для целей данного курса и CS50 ноль официально считается натуральным числом . Для обозначения этого множества используется стилизованная буква $\mathbb{N}$ .
Целые числа ($\mathbb{Z}$): Следующим шагом становится добавление отрицательных значений. Целые числа включают в себя все натуральные числа и их отрицательные копии (кроме нуля, который остается нейтральным) . Это множество обозначается буквой $\mathbb{Z}$ (от немецкого Zahlen — числа) .

Между целыми числами на числовой прямой остаются огромные «пробелы», которые заполняются рациональными числами (Rational numbers) . По определению, рациональное число — это любая дробь, где и числитель, и знаменатель являются целыми числами . Примерами служат $1/2$, $-3/2$ или известное приближение числа Пи — $22/7$ . Критически важным правилом здесь является запрет на деление на ноль: знаменатель всегда должен быть отличным от нуля, иначе «математика ломается» . Множество рациональных чисел обозначается буквой $\mathbb{Q}$ .

Кроуфорд наглядно демонстрирует иерархию этих множеств: любое целое число можно представить как рациональное, просто добавив единицу в знаменатель (например, $-2 = -2/1$) . Таким образом, каждое последующее множество как бы «поглощает» предыдущее, увеличиваясь в объёме .

За пределами рациональных чисел лежат иррациональные числа (Irrational numbers) . Это числа, которые принципиально невозможно представить в виде простой дроби из двух целых чисел . Объединение рациональных и иррациональных чисел образует действительные (вещественные) числа (Real numbers), обозначаемые буквой $\mathbb{R}$ . Это множество охватывает абсолютно все точки на числовой прямой . Любое действительное число может быть представлено в виде десятичной дроби .

Завершая этот обзор, Том отмечает, что существуют и более экзотические категории — алгебраические, трансцендентные и даже «вычислимые» (computable) числа, которые особенно важны в контексте информатики . Но перед тем как углубляться в них, необходимо детально разобрать десятичную систему счисления, основанную на латинском корне dec («десять») .

🔢 Архитектура десятичной системы и научная нотация 1:05:01

Десятичная система и магия разрядов 1:05:01

Основой нашего понимания чисел является позиционная десятичная система счисления, где значение каждой цифры зависит от её положения относительно десятичной запятой. Том Кроуфорд (Tom Crawford) демонстрирует это на примере числа 1234,567. Само название этого числа в английском (и русском) языках уже содержит в себе подсказку к его структуре: когда мы произносим «одна тысяча двести тридцать четыре», мы фактически перечисляем содержимое соответствующих разрядов .

Каждый разряд представляет собой степень десятки . Том подробно разбирает структуру целой части числа:

Тысячи: $10^3$ ($10 \times 10 \times 10 = 1000$). В примере это одна единица в разряде тысяч .
Сотни: $10^2$ ($10 \times 10 = 100$). У нас две сотни .
Десятки: $10^1$ (просто 10). В числе три десятка, что мы называем «тридцать» .
Единицы: $10^0$ (любое число в нулевой степени равно единице). Здесь у нас четыре единицы .

Как только мы переходим за десятичную запятую, паттерн зеркально меняется . Вместо умножения на десять мы начинаем делить на него, переходя к отрицательным степеням: десятым ($10^{-1}$), сотым ($10^{-2}$) и тысячным ($10^{-3}$) . Чтобы не путаться в названиях и написании дробных разрядов, Том Кроуфорд предлагает оригинальный мнемонический прием, основанный на количестве цифр .

Например, число «десять» (10) состоит из двух цифр. Следовательно, десятичная дробь «одна десятая» также должна состоять из двух цифр — 0,1 . Число «тысяча» (1000) содержит четыре цифры . Значит, «одна тысячная» в виде десятичной дроби тоже записывается четырьмя цифрами — 0,001 (считая ноль перед запятой) . В качестве примера из реальной жизни Том упоминает гонки «Формулы-1», где борьба за поул-позицию часто идет на тысячные доли секунды . Ранее в разговоре они с Дэвидом Маланом (David J. Malan) уже касались того, как важно точно классифицировать числа , и понимание разрядов — первый шаг к этому.

Научная нотация: стандарт представления чисел 1:11:24

Когда математикам или программистам приходится работать с очень большими или экстремально малыми величинами, стандартная запись становится громоздкой. Здесь на помощь приходит научная нотация (scientific notation), которую в Великобритании также называют «стандартным видом» (standard form) . Суть этого метода — представить любое число как произведение числа, находящегося в определенном диапазоне, на степень десятки .

В ходе дискуссии Том Кроуфорд и Дэвид Малан (David J. Malan) уточняют строгое правило записи . Число перед степенью десятки (мантисса) должно быть больше или равно единице, но строго меньше десяти . Математически это записывается как интервал $[1, 10)$ .

Том демонстрирует процесс преобразования на примерах:

Число 11: Оно больше десяти, поэтому мы переносим запятую на один знак влево, получая $1,1$. Чтобы сохранить исходное значение, мы умножаем его на $10^1$. Итог: $1,1 \times 10^1$ .
Число 314: Переносим запятую на два знака влево, чтобы получить число в диапазоне от 1 до 10. Итог: $3,14 \times 10^2$ (где $10^2$ — это сотни) .
Число 0,123: Это число меньше единицы. Чтобы привести его к стандартному виду, мы двигаем запятую на один знак вправо. Итог: $1,23 \times 10^{-1}$ .

Отрицательная степень здесь указывает на деление на десять или, иными словами, на перенос разряда в сторону десятых долей . Такая система записи позволяет мгновенно оценить масштаб (порядок) числа, что критически важно в компьютерных науках при оценке сложности алгоритмов или объемов памяти.

Классификация десятичных дробей: от конечных до периодических 1:20:47

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

Первый тип — конечные (терминирующиеся) десятичные дроби . Это числа, которые имеют конечное количество знаков после запятой и просто «заканчиваются». В качестве примеров Том приводит 0,123 и 0,125 . В этих числах всего три позиции после запятой, и дальше за ними ничего не следует.

Второй тип — бесконечные непериодические дроби . Они продолжаются вечно, не имея какой-либо повторяющейся структуры. Самым известным примером является число Пи ($\pi$). Том записывает его как 3,141592... и подчеркивает, что многоточие в конце — это стандартный математический символ, указывающий на бесконечную природу числа, которое никогда не остановится .

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

В качестве примера Том приводит дробь, где после запятой следует последовательность 142857 . Если над всеми этими шестью цифрами стоит черта, это означает, что число выглядит как 0,142857142857142857... и так до бесконечности . Понимание этих различий подводит итог базовым знаниям о десятичной системе и степенях десятки, необходимым для дальнейшего изучения математики в CS50 . Сразу после этого Том переходит к обсуждению того, как исторические ошибки в округлении влияли на реальный мир , но детальный разбор правил округления и значащих цифр традиционно выносится в отдельный блок теории.

🔢 Точность и упрощение: от биржевых крахов до основ работы с дробями 1:34:52

Значащие цифры и цена ошибки округления 1:34:52

Математическая точность в программировании — это не просто вопрос эстетики кода, а фактор, способный влиять на реальную экономику. Том Кроуфорд приводит в пример поучительную историю открытия Фондовой биржи Ванкувера . При расчёте биржевого индекса была допущена критическая ошибка: вместо корректного округления программа просто отсекала (транквизировала) лишние знаки после запятой . В результате число вида 500.129, которое должно было превратиться в 500.13, превращалось в 500.12 . Из-за того, что значения обновлялись до 3000 раз в день, ошибка накапливалась с огромной скоростью . Спустя всего 22 месяца после запуска индекс потерял более 50% своей реальной стоимости исключительно из-за некорректной математики .

Чтобы избежать подобных катастроф, Том Кроуфорд и Дэвид Малан формулируют три фундаментальных правила работы со значащими цифрами (significant digits, или SD) :

Точка отсчёта: подсчёт значащих цифр всегда начинается с первой ненулевой цифры слева .
Сохранение разрядов: нельзя просто отбрасывать цифры, если они определяют масштаб числа; необходимо использовать нули в качестве заполнителей (placeholders) .
Правила округления: если следующая за последней значащей цифрой — 0, 1, 2, 3 или 4, число округляется в меньшую сторону. Если это 5, 6, 7, 8 или 9 — в большую .

Рассматривая пример с числом 121, которое нужно привести к двум значащим цифрам, Том показывает, что мы сохраняем «1» и «2», а стоящая следом единица заставляет нас округлить значение вниз . Однако результатом будет не 12, а 120, так как ноль необходим для сохранения разрядности . В случае с числом 129 при тех же условиях мы получим 130, так как девятка диктует округление вверх .

Особое внимание Том уделяет случаям, когда ноль сам становится значащей цифрой. Это происходит, когда он «зажат» между другими ненулевыми числами . Например, в числе 1042 при округлении до трёх значащих цифр мы получим 1040: здесь ноль важен, так как он стоит между единицей и четвёркой .

Самый яркий пример — скорость света, составляющая 299 792 458 м/с . Если округлить это «знаменитое число» до трёх значащих цифр, то из-за каскадного округления девяток вверх мы получим 300 000 000 . В данном контексте первые два нуля после тройки считаются значащими в соответствии с математической конвенцией . При работе с десятичными дробями, такими как 0.136, правила остаются теми же: при сокращении до двух значащих цифр мы ориентируемся на первую ненулевую цифру (единицу) и округляем её соседа (тройку) вверх из-за шестёрки, получая 0.14 . Ранее в разговоре они касались десятичной системы, и здесь эти знания помогают понять, почему нули в начале дроби (например, 0.0011987) служат лишь для указания разряда и не считаются значащими до появления первой единицы .

Упрощение дробей и магия простых чисел 1:54:37

Переходя к работе с рациональными числами, которые ранее были определены как отношения целых чисел, Том Кроуфорд подчеркивает важность навыка упрощения дробей . Для этого используются два ключевых правила. Первое гласит: если умножить или разделить числитель и знаменатель на одно и то же число, значение дроби не изменится . Так, дробь 1/2 эквивалентна 3/6, поскольку мы просто умножили обе части на 3 .

Второе правило опирается на понятие простых чисел (prime numbers) — целых положительных чисел, которые делятся только на единицу и на самих себя . Том приводит пример: 3 — простое число, так как его можно получить только как 3 × 1, а 6 — нет, так как у него есть и другие множители, например, 3 × 2 .

Процесс упрощения (сокращения) дроби — это поиск общих множителей в её верхней и нижней частях:

Пример с 9/12: Мы раскладываем 9 на 3 × 3, а 12 — на 3 × 4 . Общий множитель «3» сокращается, оставляя нам 3/4 . Это и есть простейший вид, так как 3 — простое число, и дальнейшее разложение знаменателя (4 = 2 × 2) не даст совпадений с числителем .
Пример с 28/42: Том замечает, что оба числа четные, а значит, имеют общий множитель 2 . Разделив обе части на два, мы получаем 14/21 .

Хотя на этом этапе 14/21 выглядит проще, Том Кроуфорд призывает всегда проверять, не являются ли полученные числа производными других множителей, чтобы достичь максимально лаконичной формы записи рационального числа .

➗ Арифметика дробей: от конкретных примеров к общим алгоритмам 2:01:05

Работа с рациональными числами не ограничивается их определением или сокращением, которое Том Кроуфорд и Дэвид Малан обсуждали ранее . Для полноценного использования математического аппарата в программировании необходимо понимать, как эффективно манипулировать дробями: умножать, делить и складывать их, переводя конкретные числовые примеры в универсальные формулы .

Умножение и деление: метод взаимности 2:01:33

Умножение дробей Том Кроуфорд называет самой простой операцией из всех . Правило здесь максимально прозрачное: нужно перемножить числа «сверху» (числители) и «снизу» (знаменатели) . Например, при умножении 1/2 на 3/4 мы получаем 3 в числителе (1 × 3) и 8 в знаменателе (2 × 4), что дает итог 3/8 .

Чтобы превратить этот процесс в алгоритм, пригодный для написания кода, Том вводит переменные $a, b, c$ и $d$ . Общая формула умножения выглядит так: $$\frac{a}{b} \times \frac{c}{d} = \frac{ac}{bd}$$ .

Деление дробей, хотя и кажется более сложным, на самом деле сводится к тому же умножению . Основная концепция здесь — использование «обратной величины» (reciprocal) . Том Кроуфорд объясняет это простым термином: «переверните дробь» . Если нам нужно разделить 1/2 на 1/3, мы берем делитель (1/3), переворачиваем его, превращая в 3/1, и просто умножаем на первую дробь . В результате 1/2 × 3/1 дает 3/2 .

В общем виде для любых рациональных чисел операция деления записывается следующим образом: $$\frac{a}{b} \div \frac{c}{d} = \frac{a}{b} \times \frac{d}{c} = \frac{ad}{bc}$$ .

Сложность сложения и поиск общего знаменателя 2:06:01

В отличие от целых чисел, где сложение является базовым навыком, в мире дробей эта операция считается самой трудной . Главное ограничение заключается в том, что складывать (или вычитать) дроби можно только в том случае, если у них одинаковые знаменатели .

Если знаменатели разные, как в примере 1/2 + 1/3, их необходимо привести к общему виду, не меняя при этом значения самих дробей . Том предлагает «безотказный метод», который всегда сработает в программировании: умножить числитель и знаменатель каждой дроби на знаменатель другой дроби .

Процесс выглядит так:

Берем 1/2 и умножаем «верх» и «низ» на 3 (знаменатель второй дроби), получая 3/6 .
Берем 1/3 и умножаем «верх» и «низ» на 2 (знаменатель первой дроби), получая 2/6 .
Поскольку теперь у нас один и тот же знаменатель (6), мы просто складываем числители: 3 + 2 = 5 . Знаменатель при этом остается прежним . Итоговый результат — 5/6.

Этот метод универсален, так как умножение дроби на число в виде $n/n$ (например, 3/3 или 2/2) по сути является умножением на единицу и не искажает исходную величину .

Выведение универсальной формулы для Computer Science 2:09:31

Завершая разбор арифметики, Том Кроуфорд подчеркивает, почему так важно уметь переходить от чисел к буквам. В Computer Science программист часто не знает заранее, какие именно данные введет пользователь, поэтому он должен задать общую логику обработки переменных .

Применяя описанный выше метод «взаимного умножения знаменателей» к абстрактным дробям $a/b$ и $c/d$, Том выводит финальную формулу сложения на доске : $$\frac{a}{b} + \frac{c}{d} = \frac{ad + cb}{bd}$$ .

Эта формула объединяет в себе все необходимые шаги: поиск общего знаменателя ($bd$) и пропорциональное изменение числителей . Теперь, имея четкие уравнения для всех четырех операций, можно корректно реализовать работу с рациональными числами в любой программной среде . Далее в разговоре Том и Дэвид переходят к вопросу о том, как распознать рациональное число в его десятичной форме, но детальный разбор конвертации десятичных дробей в обыкновенные останется темой для последующего обсуждения .

🧮 От цифр к дробям: алгебраический метод конвертации 2:24:58

Преобразование конечных десятичных дробей 2:25:11

Процесс перевода десятичной дроби в обыкновенную часто кажется интуитивным, но Том Кроуфорд (Tom Crawford) настаивает на строгом алгоритмическом подходе, который исключает ошибки . Ранее в разговоре лекторы уже касались классификации дробей, однако именно здесь Кроуфорд демонстрирует механику «превращения» на конкретном примере — числе $0,0625$ .

Для конечных десятичных дробей алгоритм базируется на разрядной сетке. Число $0,0625$ имеет четыре знака после запятой, что соответствует десятитысячным долям. Следовательно, его можно записать как $625/10000$ . Основная работа здесь заключается в упрощении полученного выражения. Том Кроуфорд последовательно сокращает дробь, разделяя числитель и знаменатель на общие множители. Сначала он выносит пятерку: $625$ превращается в $5 \times 125$, а $10000$ — в $5 \times 2000$ . После сокращения получается $125/2000$.

Процесс продолжается итеративно:

Дробь $125/2000$ сокращается на $5$ до $25/400$ .
Следующий шаг упрощения дает $5/80$ .
Финальное сокращение на $5$ приводит к результату $1/16$ .

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

Магия бесконечных повторений: случай 0.111… 2:27:36

Переход к периодическим (повторяющимся) дробям требует более сложного алгебраического трюка. Том Кроуфорд вводит концепцию использования переменной $x$ для представления бесконечного числа . В качестве примера берется простейшая периодическая дробь $0,111...$, которую также можно записать как $0,(1)$ или $0.1$ с чертой сверху .

Суть метода заключается в «сдвиге» десятичной запятой таким образом, чтобы бесконечная часть после запятой осталась идентичной оригиналу . Поскольку в данном случае повторяется всего одна цифра, Том предлагает умножить $x$ на $10$ .

Математически это выглядит так:

Пусть $x = 0,111...$
Тогда $10x = 1,111...$

Теперь наступает «умная часть» метода: вычитание исходного уравнения из нового . Если из $10x$ вычесть $x$, получится $9x$ . С правой стороны уравнения происходит нечто удивительное: бесконечные «хвосты» из единиц полностью аннигилируют друг друга при вычитании . Уравнение принимает вид $9x = 1$ . Разделив обе части на $9$, мы получаем $x = 1/9$ . Этот элегантный способ позволяет превратить бесконечный процесс в конечный результат, доказывая, что периодическая дробь является полноценным рациональным числом .

Работа с длинными циклами и определение рациональности 2:30:34

Алгебраический метод универсален и подходит для периодов любой длины. Том Кроуфорд демонстрирует это на примере гораздо более сложной дроби: $0,142857142857...$ . Здесь цикл состоит из шести цифр. Чтобы «совместить» бесконечные хвосты, необходимо сдвинуть запятую на шесть позиций вправо . Для этого число умножается на $10$ в шестой степени ($10^6$), то есть на один миллион .

Уравнение трансформируется следующим образом:

$x = 0,142857...$
$1,000,000x = 142,857,142857...$
При вычитании $x$ из $1,000,000x$ получается $999,999x$ .
На правой стороне остается целое число $142,857$, так как вся дробная часть сократилась .

В результате получается дробь $142,857 / 999,999$ . Том признает, что процесс сокращения такой дроби вручную занял бы слишком много времени, но подтверждает, что после всех упрощений она превращается в $1/7$ . Это число уже упоминалось ранее в лекции Дэвидом Маланом (David J. Malan) как классический пример рационального числа с длинным периодом.

В завершение этого блока Том Кроуфорд формулирует ключевое определение рациональности через десятичную запись . Он подводит итог: если десятичная дробь либо конечна (терминирована), либо имеет повторяющийся цикл (период), её всегда можно представить в виде дроби $a/b$, а значит, она рациональна . В противном случае — если цифры после запятой никогда не заканчиваются и не образуют устойчивого повторения — число классифицируется как иррациональное . Таким образом, алгебраический метод служит не просто инструментом расчетов, но и фундаментальным критерием классификации чисел в математике.

🧶 Наглядная иерархия и «цифровая» вселенная Тьюринга 2:57:54

Для того чтобы упорядочить знания о различных типах чисел и их взаимосвязях, Том Кроуфорд использует оригинальный метод визуализации с помощью цветных веревок, выложенных на демонстрационном столе . Этот подход позволяет буквально увидеть, как одни множества поглощают другие и где проходят границы между фундаментальными математическими категориями. Ранее в разговоре они уже касались базовых определений натуральных и целых чисел, но теперь акцент смещается на их топологическую вложенность .

Математика на веревках: визуализация вложенности множеств 2:58:08

Демонстрация начинается с самого простого — натуральных чисел, которые Том Кроуфорд обозначает кольцом из желтой веревки . В этот круг попадают числа, используемые для счета: 0, 1, 2, 3 и далее . Однако математика требует расширения этой системы, что приводит к появлению целых чисел (integers). Чтобы показать их связь, Том берет розовую веревку и выкладывает круг большего диаметра вокруг желтого . Это наглядно иллюстрирует, что любое натуральное число автоматически является целым, но в розовом кольце появляются новые элементы — отрицательные числа, такие как $-3$ или $-42$ .

Следующий уровень — рациональные числа (дроби), представленные фиолетовой веревкой . Это кольцо охватывает и целые, и натуральные числа, поскольку любое целое число можно представить в виде дроби со знаменателем 1 . Внутри фиолетового контура, но за пределами розового, оказываются такие значения, как $1/2$ или $22/7$ .

Ситуация кардинально меняется при переходе к иррациональным числам. Том Кроуфорд подчеркивает их уникальность, выкладывая красное кольцо отдельно от предыдущих: иррациональные числа по определению не могут быть записаны в виде дроби, а значит, эти множества не пересекаются . Сюда попадают такие константы, как $\sqrt{2}$ и число $\pi$ . Чтобы завершить картину, Том использует длинную белую веревку для обозначения вещественных (реальных) чисел .

Важный нюанс визуализации:

Белая веревка должна плотно облегать и фиолетовое (рациональные), и красное (иррациональные) кольца .
Между ними нет «пустого места»: любое вещественное число обязано быть либо рациональным, либо иррациональным .
В качестве финального штриха Том заменяет символ $\pi$ на столе настоящим круглым пирогом (игра слов: pi и pie), подчеркивая «вкус» математических абстракций .

От древнегреческих чертежей до алгоритмов Тьюринга 3:04:37

За пределами базовой школьной программы лежат более сложные классификации, которые Том Кроуфорд демонстрирует уже на графической схеме. Первое из них — построимые числа (constructible numbers) . Эта концепция уходит корнями в Древнюю Грецию, где геометры пытались создавать отрезки заданной длины, используя только циркуль и линейку без делений . Любое рациональное число является построимым, но к ним добавляются и некоторые иррациональные, например, $\sqrt{2}$ .

Более широкий класс — алгебраические числа. Это любые числа (включая все построимые), которые могут быть корнями полиномиального уравнения с целыми коэффициентами . Том приводит пример: корень кубический из двух ($\sqrt[3]{2}$), который является решением уравнения $x^3 = 2$ .

Любопытный исторический факт: задача об «удвоении куба» (построение $\sqrt[3]{2}$) занимала греков веками, пока в XIX веке не было доказано, что это число алгебраическое, но не построимое .
Числа, не являющиеся алгебраическими, называются трансцендентными .

Особое значение для компьютерных наук имеет классификация, предложенная британским математиком Аланом Тьюрингом в 1936 году — вычислимые числа (computable numbers) . Том определяет их как любые вещественные числа, которые можно вычислить с любой желаемой точностью с помощью конечного завершающегося алгоритма . Это точка пересечения чистой математики и Computer Science.

Ярким примером вычислимого числа является $\pi$ . Несмотря на его трансцендентность и бесконечную десятичную дробь, существуют алгоритмы (например, алгоритм братьев Чудновских), позволяющие вычислять его знаки . На момент записи интервью мировой рекорд составляет 314 триллионов десятичных знаков, а на расчет этой последовательности ушло 110 дней . Последняя известная человечеству цифра в этой цепочке на данный момент — 8, но Том уверен, что прогресс не остановится . Подобные классификации показывают, что мир чисел гораздо богаче и сложнее, чем простая числовая прямая .

🏁 Завершение обзора: от вычисляемых чисел к теории множеств 3:23:17

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

Вещественные числа: заполнение пустот 3:23:56

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

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

Иерархия сложности: от геометрии до алгоритмов Тьюринга 3:26:44

Хотя натуральные, целые, рациональные и иррациональные числа составляют костяк школьной программы, Том Кроуфорд расширяет обзор для студентов CS50, вводя более продвинутые классификации :

Построимые числа (Constructible numbers). Эта категория уходит корнями в математику Древней Греции . Число считается построимым, если с помощью циркуля и линейки (без делений) можно построить отрезок соответствующей длины . Примером является квадратный корень из двух: его легко получить, проведя диагональ в квадрате со стороной единица . Построимые числа занимают уникальную нишу, включая в себя все рациональные числа и часть иррациональных .
Алгебраические числа (Algebraic numbers). Это числа, которые могут быть корнями многочленов с целыми коэффициентами . В эту группу входит, например, кубический корень из двух, являющийся решением уравнения $x^3 = 2$ . Том отмечает исторический факт: античная задача об «удвоении куба» оказалась невыполнимой именно потому, что кубический корень из двух, будучи алгебраическим, не является построимым .
Трансцендентные числа (Transcendental numbers). Числа, которые не являются алгебраическими . К ним относятся такие фундаментальные константы, как число $\pi$ (пи) .
Вычисляемые числа (Computable numbers). Это важнейшее связующее звено между математикой и Computer Science, предложенное британским математиком Аланом Тьюрингом в 1936 году . По определению Тьюринга, число является вычисляемым, если существует конечный алгоритм, способный вычислить его с любой заданной точностью за конечное время .

Том приводит впечатляющий пример с числом $\pi$: несмотря на его иррациональность, оно абсолютно вычисляемо . С помощью современных алгоритмов, таких как формула Чудновских, мировые рекорды вычисления $\pi$ достигли 314 триллионов знаков после запятой . Любопытно, что на вычисление такого объема данных ушло 110 дней, а 314-триллионной цифрой оказалась «8» .

Итоги первой главы и анонс теории множеств 3:40:22

Подводя итог масштабному введению в мир чисел, Дэвид Малан и Том Кроуфорд резюмируют пройденный путь. В этой главе были подробно разобраны как минимум девять различных типов чисел . Исследование началось с самых простых — натуральных чисел, используемых для счета, затем расширилось до целых чисел за счет отрицательных значений и пришло к рациональным числам (дробям) .

В ходе лекции преподаватели затронули следующие ключевые аспекты:

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

Однако, как отмечает Том, для более глубокого понимания того, как эти группы взаимодействуют друг с другом, математикам недостаточно простого описания . Необходим строгий формальный язык, который позволит описывать отношения включения, пересечения и объединения этих групп. Таким языком является теория множеств (Set Theory) . Именно этой теме — операциям над множествами и их роли в логике программирования — будет посвящена следующая глава курса .