“Есть всего 10 типов людей. Те кто понимают двоичную систему и все остальные.” — Автор Неизвестен

Это отрывок из курса программирования на JavaScript CoderslangJS .

Начни Учить Full-Stack JavaScript СЕЙЧАС!

— Привет, Герой! Сегодняшнюю лекцию для тебя проведет C2H5. Он — робот и наш союзник в борьбе с машинами.

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

Двоичная система счисления

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

Для начала, представь 10 лампочек. Каждая из них может быть включена или выключена.

Внимание, вопрос! До скольки ты мог бы посчитать используя эти 10 лампочек?

Ээээммм, до 10?

— До 10 мы однозначно можем посчитать, если будем каждый раз считать общее количество включенных лампочек. Но, как думаешь, мы могли бы досчитать до 1000 используя те же 10 лампочек?

— Нет, думаю, что это невозможно.

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

Попробуй представить, что каждая лампочка не просто включена или выключена, а отображает одну цифру от 0 до 9.

Тогда, мы бы могли получить все комбинации от 0 000 000 000 до 9 999 999 999. Или 10 миллиардов разных чисел, включая 0, конечно.

— Все равно не понятно, как посчитать до 1000 с помощью 10 обычных лампочек.

— Сейчас разберемся детально. Давай представим на нашем “ламповом калькуляторе” какое-нибудь не слишком длинное число, например 2375. Нули отбросим для простоты подсчета. Чтобы понять, что это число “две тысячи триста семьдесят пять”, ты делаешь несколько операций:

5 * 1 + 7 * 10 + 3 * 100 + 2 * 1000 = 5 + 70 +300 + 2000 = 2375

У каждой цифры или, другими словами, у каждого разряда, есть свой вес. Он считается по формуле:

БАЗА в степени ПОЗИЦИЯ.

БАЗА — это основа системы счисления. В привычных людям числах — это 10. В более естественной для машин, двоичной системе - 2.

Отсчет позиций мы начинаем справа и начальная позиция всегда 0, поэтому вес первого разряда - 1, т.к. возведение любой БАЗЫ в нулевую степень равно 1.

Следующие разряды в десятичной системе, имеет вес 10, 100, 1 000, 10 000 и т.д.

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

Это достаточно очевидно, но ведь в первоначальной задаче не было цифр, а были только 2 состояния — вкл/выкл?

— Все верно. Теперь давай попробуем не просто считать количество включенных лампочек, а еще и учитывать их позицию.

Представь такую последовательность лампочек - 0 0 1 0 1 0 1 1 0 1

Начнем с того, что присвоим каждой позиции свой вес.

Вес позиции 0 = 2 ^ 0 = 1

Вес позиции 1 = 2 ^ 1= 2

Вес позиции 2 = 2 ^ 2 = 4

Вес позиции 9 = 2 ^ 9 = 512

Теперь, чтобы посчитать итоговое число, нам осталось только умножить вес каждой позиции на ее значение (0 или 1).

Получится 1 * 1 + 0 * 2 + 1 * 4 + 1 * 8 + 0 * 16 + 1 * 32 + 0 * 64 + 1 * 128 + 0 * 256 + 1 * 512 = 1 + 4 + 8 + 32 + 128 = 173

Теперь понятно. Получается если мы включим все лампочки, то получится 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + 256 + 512 = 1023?

— Все верно. В каком-то смысле так даже проще считать, потому что мы или учитываем вес определенного разряда, или отбрасываем его.

Абстракция

— Если ты посмотришь внимательно, то, на самом деле, и десятичные числа и двоичные существуют только в нашем воображении.

— Но как же, я вполне могу представить себе 12 стульев возле обеденного стола или 40 человек стоящих в очереди. В том смысле, что они могут существовать не только у меня в голове, но и в реальности.

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

Если стульев было бы 3, а не 12, то проще всего было бы показать их, как 3 пальца на одной руке или 3 включенных лампочки. Это самый простой и очевидный способ что-то посчитать. Но что делать если их 12, 40, 125? Пальцев уже не хватит, а где хранить лампочки тоже не очень понятно.

Поэтому, люди придумали системы счисления. И десятичная система далеко не всегда была так распространена. Римляне бы подписали те же стулья как XII и, скорее всего не поняли бы что означает надпись 12.

Все это — абстракция. Мы усложнили подсчет количества предметов, но оперировать большими числами стало намного проще.

— Мне кажется, что числа встречаются в нашей жизни настолько часто, что уже никто и не воспринимает это как усложнение.

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

Обрати внимание, что если бы, в какой-то момент вместо цифр 0 1 2 … 9, люди решили использовать буквы a b c … k, то твои 12 стульев превратились бы в bc стульев, но на сами стулья это бы никак не повлияло.

Алгоритмы и псевдокод

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

Единственная сложность была в том, что компьютеру нельзя было просто сказать “сделай что-то хорошее, полезное и важное”. Нужно было написать программу, которая делала бы это “что-то”.

Хорошая новость — после того, как эта программа написана, ей могли пользоваться совершенно разные люди.

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

Целью лучших программистов тех времен — было создание полноценного искусственного интеллекта. Такого, который мог бы решить любую поставленную задачу, а не только отличать котов от собак.

Чем все закончилось — ты уже знаешь. В какой-то момент даже сами создатели уже не могли предсказать как поведут себя машины. Они оправдывали это всеобщим благом и рассказывали как была ужасна жизнь людей до изобретения ИИ.

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

— И ты думаешь, что мне действительно по силам разобраться в том с чем не справились лучшие умы 2021 ?

— Иначе мы бы не тратили время на твою подготовку, Герой. Твоё преимущество в том, что мы точно знаем как сделать из тебя программиста и внедрить в ** компанию которую нельзя называть **.

Но, что-то мы отвлеклись. Давай попробуем разобраться, как найти человека в телефонном справочнике. Пусть его зовут Васильев Петр.

Способ 1 - Линейный поиск

открываем справочник на первой странице
просматриваем все записи сверху вниз
если найдено совпадение (Васильев Петр)
    звоним по найденному номеру
иначе
    переходим к следующей записи
повторить пока не закончатся страницы

— C2H5, ты конечно извини, но так никто не ищет. Даже моя бабушка догадается сначала посмотреть оглавление, найти на какой странице находится буква “В” и только потом начнет поиск по твоему алгоритму.

— Ты прав. При наличии оглавления туда точно стоит взглянуть. Этот метод называется индексация и он очень часто используется в базах данных.

Но, при всей неоптимальности линейного поиска, он точно поможет нам найти телефон Петра Васильева или убедиться в том, что в справочнике его нет.

Как бы ты оптимизировал алгоритм линейного поиска, если бы у тебя не было индексов (оглавления), но ты знал что все записи упорядочены от А до Я?

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

— Отличный подход, т.к. ты предполагаешь, что все в справочнике примерно одинаковое количество фамилий на каждую букву алфавита.

Но, так как этого не было в условии, и мы можем оказаться в мире где 90% людей с фамилией на букву А, то я бы предложил открыть справочник ровно посередине. Оценить точность попадания и пойти направо или налево, отбросив половину записей.

Так как я робот, попробую формализовать этот алгоритм для тебя “почти” человеческим языком.

Способ 2 - Двоичный поиск

открываем справочник посередине
смотрим куда попали
если найдено совпадение (Васильев Петр)
    звоним по найденному номеру
иначе
    если фамилии на букву "В" находятся раньше
        отбрасываем правую часть справочника и переходим на шаг 1       
    если фамилии на букву "В" находятся позже
        отбрасываем левую часть справочника и переходим на шаг 1
повторить пока не закончатся страницы

Как и в случае с линейным поиском, мы или найдем необходимую запись, или убедимся в том, что ее нет. ВАЖНО! Двоичный поиск работает только в отсортированных структурах данных, например телефонных справочниках или словарях.

Он работает намного быстрее, чем линейный поиск. И чем больше элементов в структуре данных, тем сильнее становится преимущество!

Если представить, что одна итерация (повторение) алгоритма поиска занимает 1 секунду и в нашей телефонной книге 100 записей, то линейный поиск займет 100 секунд в худшем случае или 50 в среднем, а двоичный поиск — меньше 7!

— Очевидно, что сокращение количества данных для поиска в 2 раза после каждого повторения очень полезно.

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

Линейному поиску в таком случае потребуется примерно неделя, а двоичный поиск справится всего за 20 секунд!

— Ого.

— К сожалению, если мы работаем с неупорядоченными данными, то линейный поиск — наш единственный вариант.

— А если мы отсортируем данные перед поиском?

— Сортировка — дорогой и долгий процесс. Она будет иметь смысл только в том случае, если мы будем работать с этими данными долго и будем делать много поисков.

Кстати, способ описания алгоритмов, который я показал — называется псевдокодом. Его удобно использовать в ситуациях, когда мы обсуждаем логику и не хотим отвлекаться на конкретный язык программирования.

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

— Выглядит полезно. Ведь я пока не очень умею программировать.

— Это мы исправим. Давай пройдем тест, чтобы оценить, как ты усвоил новую информацию.

Ты можешь стать Full Stack JS разработчиком на CoderslangJS .