“Есть всего 10 типов людей. Те кто понимают двоичную систему и все остальные.” — Автор Неизвестен
Это отрывок из курса программирования на JavaScript CoderslangJS.
— Привет, Герой! Сегодняшнюю лекцию для тебя проведет 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 + 0 * 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.