Метка: книги

Объяснял программисту в одном чатике разницу между тестированием и формальной верификацией кода, для пущего издевательства притащил книжку для семиклассников — «Программирование: вводный курс» за авторством Д. Школьника, Н. Авданина и А. Суханова, и более того — издевался, приводя в качестве примера третью (!) программу в этой книжке — 1.3 на вот этом развороте:

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

Есть на всяких околоайтишных специальностях в вузах предмет под названием «Сети передачи данных» или как-то типа того, где про модель OSI рассказывают, TCP/IP всякое, маршрутизацию и тому подобные вопросы. Есть по нему масса учебников — Олиферы всякие, Таненбаум книжку написал, Куроуз-Росс, Горальски, Стивенс — в общем, на любой вкус, айтишники любят. Содержание в целом более-менее стандартное — вот вам модель OSI, вот вам кучка протоколов с каждого из уровней, вот так работает маршрутизация… — разница в нюансах, где-то больше теории, где-то добавляется практика какая-то. В целом, конечно, это в основном беллетристика и перечисление готовых сетевых протоколов, которые кем-то придуманы — а понимать, почему это все работает — это не вашего айтишного ума дело.

А есть старая (1993 год! а первое издание даже издательство «Мир» в 1989 году перевело) книжка Бертсекаса и Галлагера: http://web.mit.edu/dimitrib/www/datanets.html. Чем она отличается? На первый взгляд, все начинается довольно культурно — модель OSI в первой главе с описанием ее уровней, дальше — немного про всякие протоколы (в основном представляющие собой чисто исторический интерес, из более-менее актуального во второй главе можно назвать только TCP) — но вот в третьей и четвертой главе начинается самое веселье! Внезапно плотность формул на страницу текста становится запредельной, возникает «тяжелая» математика — прежде всего тервер и слупы, но мало не покажется.

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

Нет, многим, возможно, никогда не потребуется лепить управление очередями, алгоритмы множественного доступа или маршрутизации — но когда за это пытаются браться «чистые айтишники», получается крайне печально. Скажем, посмотрел на днях на Meshtastic — протокол организации mesh-сетей на основе «физики» LoRa. Мало того, что сам по себе протокол толком не документирован — так еще и реализация производит впечатление «слышали звон, да не знают, где он». Элементарнейший пример — используемый алгоритм конкурентного доступа явно сделан «по мотивам» используемой в WiFi distributed coordination function, которая неплохо обоснована с теоретической точки зрения — но упрощен настолько, что утрачена вся суть исходного алгоритма. Да, он выглядит довольно просто — но за этой простотой стоит довольно строгий анализ, и «лишнего» в нем нет. Вишенка на торте — этот важнейший элемент протокола нигде толком не документирован, и для того, чтобы понять, как он работает, приходится лезть в исходники.

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

Люблю я истории про O(N²), ничего не могу с собой поделать. Так как в этот раз все пока что держится на слухах — пусть это будет сказочка про республику Анчурия, где-то в Латинской Америке.

Анчурия — республика демократическая, в ней есть аж четыре партии — Пиратов, Жуликов, Воров и Коммунистов, и даже иногда проводятся выборы в парламент. Более того, Анчурия не чужда высоким технологиям и решила применить на очередных выборах модную новинку — электронную голосовалку на блокчейне, скачав ее прямо с гитхаба.

Одного не знали бедные любители высоких технологий из Анчурии — писал ту голосовалку не очень образованный программист Вася, и время подсчета результатов в той голосовалке зависело от количества избирателей квадаратично. Но Министерство Информационных Технологий Анчурии — люди прошаренные, и даже провели тестовое голосование — выбирали, что лучше, леденцы с ментолом или менты с леденцами. В голосовании приняли участие самые прошаренные граждане Анчурии, коих набралось аж 10 000, результаты подсчитались достаточно быстро — и систему решили внедрить на будущих парламентских выборах с десятью миллионами избирателей.

И вот поздно вечером в воскресенье закрылись электронные избирательные участки, и сам Министр Информационных Технологий нажал на самом мощном компьютере Анчурии кнопочку Enter, запустив процедуру подсчета. Долго ли ждать результатов? Ну полчаса-час, ответил министр — и все решили подождать. Сначала два часа ждали, потом четыре, восемь… — в общем, и к утру не дождались. Зато проснулись коммунисты и с криком «Дурят капиталисты нашего брата!» собрали митинг на Главной площади. К вечеру собрался уже не митинг, а целый майдан, кто-то обозвал цифрового министра пiдрахуем (не обошлось без украинского следа), пираты подрались с коммунистами, жулики с ворами — но все вместе пошли от Главной площади по Главной улице к Президентскому дворцу (география столицы Анчурии проста и понятна).

Ну дальше как всегда — Эль Президенте почуял, что пахнет жареным, и сбежал, в Анчурии случилась маленькая гражданская война, к власти пришла военная хунта и от греха подальше запретила все выборы, компьютеры и на всякий случай — украинский язык. Жуликов посадили, воров постреляли, пиратов развесили на реях, коммунистов отправили в тайные тюрьмы ЦРУ. Говорят, что где-то в начале гражданской войны бывший министр даже вылез из своего дата-центра в подземном бункере со словами «Мы все посчитали!» — но всем это было настолько безразлично, что никто про него и не вспомнил.

Так вот, господа программисты, вся беда случилась из-за того, что случайно найденная на гитхабе голосовалка имела сложность подсчета голосов O(N²) — то есть если для подсчета 10 000 бюллетеней требовалась всего 1 секунда — то подсчет 10 000 000 бюллетеней занял не 1 000 секунд, как надеялся цифровой министр, а гораздо больше — 1 000 000 секунд, или целых 11 дней — как раз хватит на то, чтобы не дождавшиеся итогов выборов анчурийцы начали гражданскую войну. O(N²) — очень «хорошая» оценка сложности, она, с одной стороны, достаточно мала, чтобы успешно проходить тесты на небольших наборах данных (это вам не перебор всех подмножеств, и даже не какие-нибудь числа Белла) — а с другой стороны, очень плохо ведет себя, когда данных становится много.

А чтобы не спровоцировать гражданскую войну в латиноамериканской стране — не делайте алгоритмы со сложностью O(N²), а читайте книжки Скиены, Седжвика, Дасгупты и Кормена, можно еще поставить на полочку многотомник Кнута.