Последствия бага в военном ПО

Вечером 25 февраля 1991 года на американскую авиабазу в саудовском Дахране прилетела ракета Р-17 «Скад». Она разнесла казарму 475-го отряда квартирмейстерской службы армии США, ответственного за очистку воды. Взрыв убил 28 человек — это пятая часть всех погибших американцев за всё время войны в Заливе. Ещё около сотни получили ранения. «Скад» был обнаружен радаром дежурной батареи зенитного ракетного комплекса «Patriot», прикрывавшей Дахран. Ракету засекли и ничего не сумели сделать. Софт «Патриота» не смог правильно отреагировать на угрозу и посчитал, что ракета проблем не представляет.

Баг в нём был простой, как кирпич. Не баг даже, а математическая фича: разработчики и военные о ней знали, и все на неё плевали, как на чепуховину ничего не значащую.

Внутренний таймер ЗРК Patriot устроен как счетчик количества интервалов времени, прошедшего с момента включения системы. Длина такого интервала — 0,1 секунды. Чтобы перевести количество этих отрезков в секунды, его, понятное дело, нужно разделить на 10. Что для этого предложили разработчики? Естественно, умножить на 0,1.

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

Raytheon начал спешно улучшать систему. И, как оно бывает, доулучшался. Некое кодирующее туловище невыясненного системно-аналитического образования придумало устранить баг с неточным определением 0,1 и написало новую процедуру умножения.

Это была хорошая новость, потому что погрешность удалось снизить ещё больше. Плохая новость состояла в том, что туловище, когда переписывало старый код, вставило вызов этой процедуры не во всех случаях, где требовалось. Кое-где остался старый расчёт времени.
Вуаля! В системе завелось ДВА внутренних значения времени, используемых при расчёте РАЗНЫХ параметров. Различие между ними накапливалось тем сильнее, чем больше времени прошло с момента включения.

Теперь погрешности в математике ЗРК уже начали что-то решать, но об этом никто не думал. Потому что штатные проверки комплекса после переделки показывали, что всё ОК. Согласно программе испытаний: «Пункт 1: включили систему. Пункт 2: выставили режимы. Пункт 3: всё работает. Пункт 4: выключили. Переходим к следующему разделу».
Но никто не проводил «endurance test»: проверку на длительное дежурство на одном месте да против скоростных целей. А оно и зачем, если Patriot — это мобильный войсковой ЗРК для прикрытия боевых порядков? На одном месте ему по всем наставлениям стоять не следует, в том числе, в интересах собственной выживаемости.

Первыми за аномалию в работе комплекса зацепились не в США, а в Израиле. Развёртывающиеся боевые порядки страна прикрывать особо не собиралась, а вот собственная территория Израиль интересовала. Ну и по причине обычной национальной запасливости.
У ЗРК Patriot нет своих собственных накопителей для «логов» работы, поэтому комплексам полагались внешние. Но в армии США накопители не любили. Ходило вполне обоснованное мнение, что их софт какая-то очередная вавилонская ключница делала, и накопители периодически вешают всю систему. Поэтому операторы американских ЗРК на Ближнем Востоке их обычно не подключали, а вот в ЦАХАЛе всё сделали по инструкции.

Теперь вторая часть Марлезонского кодирования. Числа-то двоичные.
Точного представления десятичной дроби 0,1 в двоичном виде не существует — оно может быть только приблизительным.
Поэтому бодрые наследники древнего Вавилона из корпорации Raytheon вместо десятичного 0,1 загнали в систему двоичное число 0,00011001100110011001100. Оно немногим меньше требуемых 0,1 — примерно на одну десятимиллионную. Вот на это число радостно и умножили, полагая, что проблема решена.

Первые иракские «Скады» стартовали в сторону Израиля 18 января 1991 года. Израильские офицеры, однако, нашли время отсмотреть «логи». Уже 11 февраля от них в США прилетел первый «багрепорт»: после нескольких часов непрерывной работы ЗРК наблюдается необъяснимый дрейф параметров при переходе от режима обнаружения к сопровождению цели.
Радар при работе «на сопровождение» смотрит во вполне определенную узкую область пространства, где должна быть цель — так называемую «Range Gate Area», RGA. А ракета «Скада» быстрая, и надо чётко понимать, где она будет на следующем такте работы. Положение RGA определяется опережающим расчётом в зависимости от координат и скорости цели. А эта математика прямо завязана на точный отсчёт времени. А время у нас отсчитывается… ну, вы уже видели, как.

И с каждым часом отсчитывается всё косячнее. Израильтяне увидели, что границы окна, обсчитанные на этом косячном времени, начали ехать. Цель уже не посередине RGA, а ближе к краю, за 8 часов смещение процентов на 20 от центра окна.

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

«Да ну, фигня, — отмахнулись генералы в Штатах. — У системы нормальный аптайм всего несколько часов. Зачем её вообще держать включённой постоянно? Ладно, по мере сил всё пропатчим и заапдейтим».
Надо заметить, что софтину ЗРК Patriot за тот нервный период с осени 1990 года перепатчивали уже аж шесть раз. Причем в пожарном порядке: надо было обучить аппарат противостоять иракским «Скадам» и «Аль-Хусейнам», и какая-то идиотская проблема многочасовой работы никого не волновала. Тем более, что накатывался один такой патч пару часов минимум, и всё это время комплекс должен стоять мёртвым куском железа. Кому это надо прямо во время войны?

Но 16 февраля патч таки написали и начали помаленьку ставить на комплексы. 21 февраля военное начальство, испытав нехорошее предчувствие в области собственных кресел, дополнительно разослало дежурную инструкцию для операторов ЗРК. Она состояла из одной фразы: не держите систему включённой «слишком долго», а то будут проблемы с захватом цели.

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

… Дежурная батарея «Альфа», принадлежавшая батальону, что прикрывал авиабазу Дахран, на вечер 25 февраля 1991 года имела аптайм больше четырёх суток. За этот период накопленная ошибка составляла уже 0,343 секунды. Для баллистической цели типа «Скада» это означало смещение центра RGA почти на 700 метров относительно реального положения ракеты. И это при габарите самого RGA около 300 метров. Проще говоря, собственный софт заставлял радар смотреть в гарантированно пустое пространство, и захват наблюдаемой в обзорном режиме цели не происходил. Ракета «Скад» своё дело сделала.

Мастер на все руки — разработка сайта

Вы понимаете, о скольких вещах приходится одновременно переживать, когда работаешь над сайтом?

Знаете, когда хочешь сделать хороший продукт, но у тебя на всё просто не хватает рук…

Как думаете, большая ли команда разработчиков работает над сайтом? Может быть дизайн-студия?

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

  • Структурного дизайнера,
  • UI-дизайнера,
  • Клиентского Программиста,
  • Серверного Программиста
  • Верстальщика,
  • Редактора,
  • Художника,
  • Фоторедактора,
  • Ретушёра,
  • Аниматора,
  • Оптимизатора,
  • Тестировщика…

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

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

С фотографиями швах. Приходится работать с тем, что есть.
Абсолютно не хватает времени на ретушь, не говоря уже о более серьёзной обработке.

Идейный замысел сайта уже был переигран множество раз.

 

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

Подкорректировал двойку. Поколдовал немного с прозрачностью. Без анимации, конечно, не то.

Но вы представляете, сколько времени занимает анимация изображения? Тут нужна работа художника на 10 часов, не меньше!

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

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

Вот вчера, меня и вовсе добили фразой «а что, если нам попробовать тильду, у них очень красивые шаблоны выходят?»

Наверное, я про него не знал? Стоит посмотреть?
Да чёрт возьми, я уже хренову кучу сайтов сделал на этом конструкторе для безруких, у которых нет навыков вёрстки «от слова совсем». А они предлагают им воспользоваться?
Ну ок, выкидываем половину наработок и идей, которые бы нам были очень кстати, и делаем статичный сайт на тильде. Замечательно. Вот после таких предложений и руки опускаются делать что-то в этом поле.

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

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

Но ничего, скоро вернусь снова к работе, необходимо уже встретиться с этим человеком, и понять, что за взгляд они такой декларируют за моей спиной, и почему обговаривают, не обговаривая с тем, кто собственно делает всю систему?

Не кажется ли это странным, что люди: заказчики, любители крутых идей и красивой картинки, совсем не думают о том, как это технически должно быть реализовано внутри,  и почему всё складывается так, как оно получается?

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

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

Сайт «Вернувшихся» — статичное дерьмо, с одним единственным видео, встроенным на главную страницу.

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

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

И больше всего расстраивает в этом то, что несмотря на то, что меня назначили главного по медиа-продукту (и я этому очень рад!), но всё таки все основные решения как-то проплывают мимо (например тот факт, что от электронной голосовалки отказались, меня уведомили постфактум), а визуальные составляющие обсуждают опять же без тебя, не очень то погружая в суть вещей. Да, эти чёртовы сроки горят. Я вообще ожидал, что к началу февраля мы сможем запустить рекламу на то, что у нас есть, а часть деталей можно доделать до определённого уровня позже, когда будет время. Но рекламу не запустили, поскольку проще свалить на «недостаточный уровень дизайна», который теперь отодвинул срок рекламы на неделю, а то и дольше. И придётся начинать с группы,  ведь «сайт совершенно ещё не готов!». А я что. Расстраиваюсь, успокаиваюсь. Сержусь непонятно на что. На ситуацию, на людей, которые со мной работают. И иду делать работу дальше. Потому что я, чёрт возьми, люблю своё дело.

Фух, накипело. Половину этой писанины можно смело выкинуть в мусорку, или сжечь в пламени, как излишне эмоциональное чтиво. Но есть и объективные моменты. Возможно их стоит обсудить с нашим продюсером, или с заказчиком, при очной встрече.

Иди-ка ты на !@# со своей «токсичностью»

IT — не детский садик. Это место для взрослых, руководствующихся логикой и здравым смыслом. Их не надо опекать, не надо следить за словами, не надо переживать, что у них сформируются комплексы. Если человек некомпетентен, надо дать ему об этом явно понять, а не беречь его нежные чувства в ущерб всем остальным.

Так какого же чёрта моё прекрасное IT превращается в детский сад «Весёлый Програм-Мишка»?

Я в корне не согласен ни c активно насаждаемым представлением о рабочей этике, ни представлениями о её последствиях. Мне не нравятся эти карамельные рельсы, смазанные розовыми соплями, на которые пытаются направить отрасль различные мечтатели и популисты. Они ведут вовсе не к молочным рекам с кисельными берегами а к джунглям интриг и пустыне кадрового голода через тунель отрицательного отбора.

Что, собственно, постулируется сейчас как норма рабочей этики? Вот цитата из CoC одной конференции, которая это объясняет

Мы хотим, чтобы среда была безопасной и дружелюбной…

Ну вроде ничего плохого, да? Что не так-то?

Всё в порядке. Это правильно. Проблемы с пониманием этого.

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

Почему это под безопасностью надо подразумевать отсутствие любых отрицательных эмоций? Почему та же безопасность среды рапространяется только в одну сторону? Мне кажется каким-то садомазохизмом. Человек может раз за разом отправлять вам на ревью код с одними и теми же ошибками и надо отвечать на это вежливостью и улыбкой? Я бы определённо не назвал это безопасностью. Тут скорее подходит «находиться в состоянии постоянного стресса».

Пусть программирование это не стройка, но всё же ты не куличики в песочнице лепишь. Ты работаешь с реальными людьми, зачастую с реальными деньгами, кое-кто так и вовсе с самолётами или башенными кранами. Это ТЫ должен делать окружение безопасным, понимаешь? Не потерять чей-то аккаунт, не лишить кого-то купленной лицензии, не уронить самолёт.

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

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

Дружелююбность среды тоже почему-то рассматривается только в одну сторону. Уважение и хорошее отношение довольно легко приобрести и сложно потерять. Заслужить его можно только отношением к коллегам и своей работой. С чего это вдруг появится уважение к человеку, который игнорирует критику и советы? К человеку, который плохо выполняет свои обязанности?

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

Что, вообще, такого надо делать на работе, чтобы приходилось ЗАСТАВЛЯТЬ коллег быть вежливыми? Не могу себе такого представить.

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

Без критики нельзя совершенствоваться. Только взгляд со стороны позволит оценить свой навык. Многие вещи тяжело усвоить без менторства. Можно ли убедить человека учиться новому и исправлять ошибки без отрицательного подкрепления? Конечно. Но его наличие сильно ускоряет учебный процесс. Несомненно, оскорблять коллегу из за недостатка знаний недопустимо, но очевидный формат «Твой код плохой, я сейчас подробно изложу причины и дам советы» уже считается токсичным поведением.

Аврал в работе программиста если и не норма, то явление частое и надо быть к нему готовым. Нельзя отловить все баги на деве, обязательно случаются ситуации, требующие срочного решения. Надо быть готовым к тому, что хотя бы день в году будет проведён в экстремальном режиме, возможно это будет экстремальная ночь, если всё плохо то и экстремальная неделя. Но откуда взяться стрессоустойчивости в дружелюбной и безопасной среде? Что будет делать наш программист-детсадовец, когда ему раз в полчаса пишет директор и спрашивает «Ну как? Готово?».

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

Давайте посмотрим вокруг, первые ростки этого зла уже дают плоды. Вот вам немного реальности, данной нам в ощущениях.

Происходит активная девальвация статусов. Сейчас очень легко найти вакансии сеньоров, тимлидов, архитекторов с опытом от года. ОТ ГОДА. Не может быть, чтобы HR поголовно сошли с ума, кто-то и в самом деле верит, что с годом опыта можно быть специалистом высшего уровня в профессии. Хм… А зачем тогда все эти институты на несколько лет, не говоря уже про школу?..

Неожиданный факт — программисты не хотят работать без печенек. Вы, что серьёзно? Какого чёрта в каждой вакансии на сеньора указывают эти грёбаные печеньки? Твоя зарплата в 200к не позволяет тебе купить их? Да ты пекаря себе личного можешь нанять! Это просто какой-то сюрреализм. Описать в вакансии интересные задачи, стек технологий — да твоё рабочее железо в конце-то концов, многие как-то забывают, зато печеньки все указывают. Без этого сеньор не снизойдёт. Понятно, что пишут это чтобы показать, что кандидат будет работать в комфортной среде, но все печеньки мира не заменят нормальной машины. На заметку всем, кто в поиске работы — характеристики рабочего места, на всякий случай, стоит уточнять.

Относительно подковёрных интриг тоже много историй, вот одна от лично знакомого мне человека. Разработчик приходит в компанию, работает три месяца, все с ним вежливы и обходительны. Через три месяца разговор с HR, в результате которого выясняется, что команда его ненавидит. После этого запой, переход в другую команду и паранойя. Хотя не знаю, можно ли называть паранойей то состояние, когда тебя и в самом деле окружают двуличные ублюдки.

Мне хочется считать программистов субкультурой. Определённо, к этому есть все предпосылки — достаточно закрытое сообщество по интересам со своей мифологией и неформальными лидерами, со своими критериями оценки человека. Не надо пытаться всё это устранить под надуманным предлогом «токсичности». То, что предлагается взамен не выглядит даже близко равноценным. Отрасль инфантильных двуличных дилетантов? Спасибо, всё как я и мечтал!

Идите-ка вы в жопу с вашей «токсичностью»! Я говорю это потому, говорить друг другу такое могут могут позволить себе только друзья. А то, что пытаются продавливать как «дружелюбную и безопасную среду» выглядит как секта.

 

Взято с Хабрахабра: https://habr.com/post/432700/

Какие алгоритмы нужно знать, чтобы стать хорошим программистом?

Данная статья содержит не только самые распространенные алгоритмы и структуры данных, но и более сложные вещи, о которых вы могли не знать. Читаем и узнаем!

Я предполагаю, что вы знаете как минимум один язык программирования и такие понятия, как объект и указатель. Алгоритмы и структуры данных будут перечисляться по степени их сложности.

Для начала давайте начнем с линейных структур данных и алгоритмов

  • Массивы
  • Связный список
  • Стек
  • Очереди

Перейдем к базовым алгоритмам

  • Сортировка — Сортировка слиянием, Сортировка вставками, Быстрая сортировка, Несколько взаимных перестановок.
  • Умножение матриц (Не обязательно реализовывать, главное — знать алгоритм)
  • Основные алгоритмы просеивания
  • Беззнаковая математика, включая умножение и деление
  • Алгоритм Евклида для нахождения НОД (наибольший общий делитель), Модульная инверсия, Быстрое возведение в степень
  • Числа Фибоначчи с матричным умножением
  • Нормальное распределение и математическое ожидание
  • Статистика – среднее вероятностное значение случайной величины, медиана, дисперсия, теорема Байеса

Также можно изучить популярные алгоритмические методы:

  • Алгоритмы декомпозиции – Бинарный поиск, Нахождение подмассива с наибольшей суммой элементов
  • Жадные алгоритмы – Выбор задач, кодирование по алгоритму Хаффмана
  • Динамичное программирование – Цепное матричное умножение, Алгоритм решения задачи по укладке ранца
  • Линейное программирование – Максимизация параметра, Линейное время сортировки
  • Криптографические алгоритмы – Алгоритм Манакера по нахождению длиннейшей подстроки-палиндрома, алгоритм нахождения наибольшей общей подпоследовательности (LSC), расстояние Левенштейна

Теперь перейдем к типичным нелинейным структурам данных

  • Деревья – Бинарное дерево, Дерево общего вида, Наименьший общий предок
  • Бинарное дерево поиска – Симметричный обход, Обход по уровням, Нахождение k’ого наибольшего элемента, Диаметр, Глубина, Количество узлов и т.д.
  • Динамическая память – Динамический массив, Двоичная куча, Пирамидальная сортировка
  • Алгоритм объединения-поиска
  • Хеш-таблица – Метод нахождения коллизий (Linear Probing), Открытая адресация, Предотвращение коллизий

Рассмотрим графы

  • Список смежных вершин графа, Матрица смежности графа, Взвешенные рёбра графа
  • Основные алгоритмы обхода – Поиск в ширину, Поиск в глубину и т.д.
  • Алгоритмы нахождения кратчайшего пути — Алгоритм Дейкстры, Алгоритм Флойда-Уоршелла, Алгоритм Беллмана-Форда
  • Минимальное остовное дерево — Алгоритм Крускала, Алгоритм Прима

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

Усложнённые деревья и графы

  • Сбалансированные деревья – AVL-дерево, Красно-черное дерево
  • Heavy-light декомпозиция, Б-деревья, Дерево квадрантов
  • Усложнённый граф – Минимальный разрез, Максимальный поток
  • Максимальное покрытие – Теорема о свадьбах
  • Гамильтонов цикл
  • Рёберный граф/ Линейный граф
  • Сильно связные компоненты
  • Главный подграф, Покрытие вершин, Задача коммивояжёра – Алгоритм аппроксимации

Продвинутые криптографические алгоритмы:

  • Алгоритм Кнута-Морриса-Пратта
  • Алгоритм Рабина-Карпа
  • Префиксные и суффиксные деревья
  • Автоматизация суффиксов – Алгоритм Укконена

Высшая математика

  • Быстрое преобразование Фурье
  • Проверка простоты
  • Вычислительная геометрия – Задача поиска ближайшей пары, Диаграмма Вороного, Выпуклая оболочка множества точек

Общие продвинутые темы:

  • Выполнение обхода всех комбинаций/перестановок
  • Поразрядная обработка

Ссылка на оригинальную статью
Перевод: Александр Давыдов
Источник