Pull to refresh
47
0

Здесь могла бы быть моя специализация

Закономерности в распределении простых чисел

Reading time 7 min
Views 29K

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

Первостепенная задача, решение которой автоматически привело бы к решению большинства вопросов связанных с простыми числами заключается в следующем:

Получить рекуррентную формулу для очередного простого числа.

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

Читать далее
Total votes 27: ↑25 and ↓2 +23
Comments 15

Динамическое программирование. Классические задачи

Reading time 8 min
Views 322K
Здравствуй, Хабрахабр. В настоящий момент я работаю над учебным пособием по олимпиадному программированию, один из параграфов которого посвящен динамическому программированию. Ниже приведена выдержка из данного параграфа. Пытаясь объяснить данную тему как можно проще, я постарался сложные моменты сопроводить иллюстрациями. Мне интересно ваше мнение о том, насколько понятным получился данный материал. Также буду рад советам, какие еще задачи стоит включить в данный раздел.

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

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

Такие задачи решают методом динамического программирования, а под самим динамическим программированием понимают сведение задачи к подзадачам.
Читать дальше →
Total votes 105: ↑97 and ↓8 +89
Comments 72

Сопроцессы: -что, -как, -зачем?

Reading time 5 min
Views 20K
Многие пользователи Bash знают о существании со-процессов, появившихся в 4-й версии Bash'a. Несколько меньшее количество знает о том, что сопроцессы в Bash не какая-то новая фича, а древний функционал KornShell'a появившийся ещё в реализации ksh88 в 1988 году. Ещё меньшее количество пользователей shell'ов умеющих сопроцессить знают синтаксис и помнят как это делать. Вероятно, я отношусь к четвёртой группе — знающих о сопроцессах, периодически умеющих ими пользоваться но так и не понимающих «зачем?». Я говорю «периодически», так как иногда я освежаю в голове их синтаксис, но к тому моменту, когда мне кажется что «вот тот случай когда можно применить co-proc» я уже напрочь забываю о том как это делать.

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

В заголовке статьи у нас 3 вопроса. Пойдём по порядку.

Что?


Что же такое co-process? Со-процессинг — это одновременное выполнение двух процедур, одна из которых считывает вывод другой. Для его реализации необходимо предварительно запустить фоновый процесс выполняющий функционал канала. При запуске фонового процесса его stdin и stdout присваиваются каналам связанными с пользовательскими процессами. Соответственно, один канал для записи, второй для чтения. Пояснять это проще на примерах, поэтому сразу перейдём ко второму вопросу.
Читать дальше →
Total votes 58: ↑57 and ↓1 +56
Comments 36

Никогда не отвлекай программиста

Reading time 2 min
Views 239K
Во многих компаниях программистам запрещают работать в наушниках или отвлекают их по мелким вопросам. Вероятно, причина кроется в плохой информированности менеджеров и других сотрудников, насколько вредно так делать.

Крис Парнин (Chris Parnin) из технологического института Джорджии решил восполнить этот недостаток и опубликовал чрезвычайно насыщенную статью со ссылками на различные исследования по этой теме.

Для начала, несколько фактов, которые относятся ко всем работникам интеллектуального труда. Задача, прерванная по ходу выполнения, занимает в два раза больше времени и содержит вдвое больше ошибок, чем та же задача, которая выполнялась без прерывания (Czerwinski:04). Офисные сотрудники вынуждены отвлекаться при выполнении 57% задач (Mark:05). Опросы говорят о том, что сотруднику требуется в среднем 15 минут, чтобы вернуться в нормальный ритм после того, как его отвлекли (vanSolingen:98).
Читать дальше →
Total votes 263: ↑248 and ↓15 +233
Comments 180

Что делает центральный процессор, когда ему нечего делать

Reading time 10 min
Views 72K

Мужик приходит устраиваться работать на стройку. Его спрашивает мастер:
— Что делать умеешь?
— Могу копать…
— А что еще?
— Могу не копать…

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


Неактивным процессор может быть не только для экономии энергии, но и в результате возникновения особых ситуаций, в процессе выполнения протоколов инициализации или как итог намеренных действий системных программ. Почему это интересно? При написании программных моделей (в том числе виртуальных машин) компьютерных систем, необходимо корректно моделировать переходы между состояниями виртуальных процессоров. В работе системных программ регулярно возникают ситуации, когда по тем или иным причинам ЦПУ должен «притормозить». Умение корректно использовать и моделировать эти ситуации зависит от знания и понимания спецификаций.


В статье фокус делается на программной стороне вопроса состояний процессора. Я не буду концентрироваться на деталях реализации (напряжения, пины, частоты и т.д.), так как 1) они существенно различаются между поколениями и моделями процессоров даже одной архитектуры, тогда как программный интерфейс остаётся обратно совместимым; 2) они не видны напрямую программам и ОС. Это попытка просуммировать информацию, разбросанную по многим страницам справочника Intel IA-32 and Intel 64 Software Developer Manual.


Начнём с простой и всем знакомой ситуации — процессор включён, бодр и весел.

Читать дальше →
Total votes 67: ↑65 and ↓2 +63
Comments 24

C/C++: как измерять процессорное время

Reading time 10 min
Views 79K

image
КДПВ


От переводчика:
Большинство моих знакомых для измерения времени в разного вида бенчмарках в С++ используют chrono или, в особо запущенных случаях, ctime. Но для бенчмаркинга гораздо полезнее замерять процессорное время. Недавно я наткнулся на статью о кроссплатформенном замере процессорного времени и решил поделиться ею тут, возможно несколько увеличив качество местных бенчмарков.


P.S. Когда в статье написано "сегодня" или "сейчас", имеется ввиду "на момент выхода статьи", то есть, если я не ошибаюсь, март 2012. Ни я, ни автор не гарантируем, что это до сих пор так.
P.P.S. На момент публикации оригинал недоступен, но хранится в кэше Яндекса


Функции API, позволяющие получить процессорное время, использованное процессом, отличаются в разных операционных системах: Windows, Linux, OSX, BSD, Solaris, а также прочих UNIX-подобных ОС. Эта статья предоставляет кросс-платформенную функцию, получающую процессорное время процесса и объясняет, какие функции поддерживает каждая ОС.

Читать дальше →
Total votes 32: ↑29 and ↓3 +26
Comments 69

Forensic VS шрёдер: получение доступа к удаленным файлам

Reading time 4 min
Views 12K
Основой одного из заданий online-этапа NeoQUEST-2016 стала форензика, а именно — работа со средствами восстановления предыдущего состояния разделов Windows. Профессионалы знают и часто пользуются при пентестах или расследовании инцидентов информационной безопасности возможностями данной технологии.

Многим известная Volume Shadow Copy – служба теневого копирования томов, впервые появившаяся в ОС Windows Sever 2003. Она позволяет делать и восстанавливать моментальные снимки файловой системы (снепшоты), в том числе и системного раздела. Также прошлые снепшоты раздела могут быть подмонтированы в букву диска или в папку, как и обычный раздел. Таким образом, удается получить доступ к предыдущему состоянию системы вместе со ВСЕМИ файлами, в том числе и к файлам, в настоящий момент удаленным с этого раздела. Все эти свойства Volume Shadow Copy могут быть использованы специалистами по информационной безопасности следующими способами:
  1. Доступ и копирование занятых системой или пользовательскими приложениями файлов (БД паролей приложений, почтовые ящики Outlook, Thunderbird, БД Active Directory).
  2. Доступ и копирование удаленных файлов (в том числе и надежно затертых шредером).
  3. Сокрытие исполняемых файлов и модулей вредоносного бэкдора (делается снимок файловой системы, в котором они присутствуют, после чего они удаляются с текущего раздела, оставаясь в теневой копии).

На использовании возможности из второго пункта и было основано решение задания на форензику NeoQUEST. Подробнее — под катом!
Читать дальше →
Total votes 13: ↑11 and ↓2 +9
Comments 0

10 онлайн-инструментов для проверки SSL, TLS и последних уязвимостей

Reading time 4 min
Views 156K
От переводчика.

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


image
Читать дальше →
Total votes 20: ↑19 and ↓1 +18
Comments 4

Нет ничего проще, чем вызвать функцию, я сам это делал неоднократно

Reading time 12 min
Views 35K

Предшествующая статья про исключения в С++ оставила кучу тёмных мест,
главное, что осталось непонятным — так как же всё-таки осуществляется
передача управления при возбуждении исключения?
С SJLJ всё понятно, но, утверждается, что эта технология практически
вытеснена некоторым без-затратным (при отсутствии исключений) табличным механизмом.
А вот что это за механизм такой и как он устроен, будем разбираться под катом.
Читать дальше →
Total votes 56: ↑55 and ↓1 +54
Comments 7

TOP'ай сюда

Reading time 5 min
Views 176K
Обзор практически всех *top утилит под linux (atop, iotop, htop, foobartop и т.д.).

top

Все мы знаем top — самую простую и самую распространённую утилиту из этого списка. Показывает примерно то же, что утилита vmstat, плюс рейтинг процессов по потреблению памяти или процессора. Совсем ничего не знает про загрузку сети или дисков. Позволяет минимальный набор операций с процессом: renice, kill (в смысле отправки сигнала, убийство — частный случай). По имени top суффикс "-top" получили и все остальные подобные утилиты в этом обзоре.

atop


Atop имеет два режима работы — сбор статистики и наблюдение за системой в реальном времени. В режиме сбора статистики atop запускается как демон и раз в N времени (обычно 10 мин) скидывает состояние в двоичный журнал. Потом по этому журналу atop'ом же (ключ -r и имя лог-файла) можно бегать вперёд-назад кнопками T и t, наблюдая показания atop'а с усреднением за 10 минут в любой интересный момент времени.

В отличие от top отлично знает про существование блочных устройств и сетевых интерфейса, способен показывать их загрузку в процентах (на 10G, правда, процентов не получается, но хотя бы показывается количество мегабит).

Незаменимое средство для поиска источников лагов на сервере, так как сохраняет не только статистику загрузки системы, но и показатели каждого процесса — то есть «долистав» до нужного момента времени можно увидеть, кто этот счастливый момент с LA > 30 создал. И что именно было причиной — IO программ, своп (нехватка памяти), процесор или что-то ещё. Помимо большего количества информации ещё способен двумя цветами подсказывать, какие параметры выходят за разумные пределы.
Читать дальше →
Total votes 401: ↑389 and ↓12 +377
Comments 122

Обезвреживаем бомбу с Radare2

Reading time 12 min
Views 60K

Доброго времени суток, %username%! Сегодня мы отправимся изучать бесчисленные возможности фреймворка для реверсера — radare2. В виде подопытного я взял первую попавшую бомбу, она оказалась с сайта Университета Карнеги Меллон.
Читать дальше →
Total votes 51: ↑50 and ↓1 +49
Comments 28

Значимость SPF

Reading time 4 min
Views 190K
Хочу обратить ваше внимание на важную, на мой взгляд, проблему, которой пренебрегают даже самые крупные и инновационные компании мира. Проблема заключается в отсутствии у большинства доменов SPF-записи, которая защищает домен от его несанкционированного использования в электронной почте.
SPF (Sender Policy Framework) представляет из себя текстовую запись в TXT-записи DNS домена. Запись содержит информацию о списке серверов, которые имеют право отправлять письма от имени этого домена и механизм обработки писем, отправленных от других серверов.
Например, SPF-запись «example.com. TXT «v=spf1 +a +mx -all»» говорит о том, что отправлять письма от имени домена «example.com» могут сервера, указанные в A и MX-записях этого домена, а письма, отправленные от других серверов должны быть удалены (Fail).

Читать дальше →
Total votes 35: ↑32 and ↓3 +29
Comments 34

Знай сложности алгоритмов

Reading time 2 min
Views 977K
Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. В прошлом, когда я готовился к прохождению собеседования я потратил много времени исследуя интернет для поиска информации о лучшем, среднем и худшем случае работы алгоритмов поиска и сортировки, чтобы заданный вопрос на собеседовании не поставил меня в тупик. За последние несколько лет я проходил интервью в нескольких стартапах из Силиконовой долины, а также в некоторых крупных компаниях таких как Yahoo, eBay, LinkedIn и Google и каждый раз, когда я готовился к интервью, я подумал: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? ». Чтобы сохранить ваше время я создал такую шпаргалку. Наслаждайтесь!
Читать дальше →
Total votes 312: ↑296 and ↓16 +280
Comments 99

Непересекающиеся множества и загадочная функция Аккермана

Reading time 14 min
Views 38K
Речь пойдёт о простой структуре данных — системе непересекающихся множеств. Вкратце: даны непересекающиеся множества (например, компоненты связности графа) и по двум элементам x и y можно: 1) узнать, находятся ли x и y в одном множестве; 2) объединить множества, содержащие x и y. Сама структура очень проста в реализации и описывалась много раз в различных местах (например, есть хорошая статья на хабре и ещё кое-где). Но это один из тех удивительных алгоритмов, написать который ничего не стоит, а вот разобраться, почему он работает эффективно совсем нелегко. Я постараюсь изложить относительно простое доказательство точной оценки на время работы этой структуры данных, придуманное Зейделем и Шариром в 2005 (оно отличается от того ужаса, который многие могли видеть в других местах). Конечно, сама структура тоже будет описана, а попутно разберёмся причём здесь обратная функция Аккермана, о которой многие знают только, что она оооочень медленно растёт.
Читать дальше →
Total votes 39: ↑39 and ↓0 +39
Comments 3

Объекты нулевого размера

Reading time 4 min
Views 29K
В чём разница между следующими парами длин и указателей?

size_t len1 = 0;
char *ptr1 = NULL;

size_t len2 = 0;
char *ptr2 = malloc(0);

size_t len3 = 0;
char *ptr3 = (char *)malloc(4096) + 4096;

size_t len4 = 0;
char ptr4[0];

size_t len5 = 0;
char ptr5[];


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

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

malloc(0)


Поведение malloc(0) определено стандартами. Можно вернуть нулевой или уникальный указатель. Второй вариант во многих реализациях выполняется внутренним увеличением длины на единицу (которая затем обычно округляется до 16). По правилам, разыменовать такой указатель нельзя, но обычно несколько байт всё-таки размещаются, и поэтому такая программа не упадёт.

Возврат NULL приводит к возможности возникновения интересного бага. Часто возврат NULL из malloc расценивается как ошибка.
Читать дальше →
Total votes 33: ↑29 and ↓4 +25
Comments 14

Я не знаю Си

Reading time 4 min
Views 50K
Цель этой статьи — заставить всех, особенно программистов на Си, сказать «я не знаю Си».
Хочется показать, что тёмные углы в Си значительно ближе, чем кажется и даже тривиальные строки кода несут в себе undefined behavior.
Читать дальше →
Total votes 285: ↑268 and ↓17 +251
Comments 309

19 советов по повседневной работе с Git

Reading time 14 min
Views 284K


Если вы регулярно используете Git, то вам могут быть полезны практические советы из этой статьи. Если вы в этом пока новичок, то для начала вам лучше ознакомиться с Git Cheat Sheet. Скажем так, данная статья предназначена для тех, у кого есть опыт использования Git от трёх месяцев. Осторожно: траффик, большие картинки!

Содержание:
  1. Параметры для удобного просмотра лога
  2. Вывод актуальных изменений в файл
  3. Просмотр изменений в определённых строках файла
  4. Просмотр ещё не влитых в родительскую ветку изменений
  5. Извлечение файла из другой ветки
  6. Пара слов о ребейзе
  7. Сохранение структуры ветки после локального мержа
  8. Исправление последнего коммита вместо создания нового
  9. Три состояния в Git и переключение между ними
  10. Мягкая отмена коммитов
  11. Просмотр диффов для всего проекта (а не по одному файлу за раз) с помощью сторонних инструментов
  12. Игнорирование пробелов
  13. Добавление определённых изменений из файла
  14. Поиск и удаление старых веток
  15. Откладывание изменений определённых файлов
  16. Хорошие примечания к коммиту
  17. Автодополнения команд Git
  18. Создание алиасов для часто используемых команд
  19. Быстрый поиск плохого коммита

Читать дальше →
Total votes 152: ↑149 and ↓3 +146
Comments 62

Клетка со всеми удобствами

Reading time 4 min
Views 8.9K
Хабр активно реагирует на все инициативы (чего бы они ни касались) по ограничению возможности выбора. И это замечательно. Тот же интернет (в те времена, когда он еще не писался с большой буквы) декларировался как средство свободного общения всех со всеми и свободного поиска информации в целях развития общества. И ключевое слово в предыдущем предложении естественно — «свободного».

Вот только один вопрос. Насколько свободен от ограничений и в итоге насколько адекватен результат нашего выбора?
Читать дальше →
Total votes 22: ↑15 and ↓7 +8
Comments 5

Настройка окружения для тестирования изменений в ядре Linux

Reading time 2 min
Views 12K
image

Иногда (редко, но все-же) возникает потребность что-то дописать или переделать в ядре всеми нами любимого линукса. И тогда возникает вопрос: А как все эти изменения запустить и проверить быстро и без перекуров?

Одно дело, если мы можем организовать нашу новую функциональность в виде модуля, тогда нам довольно просто можно тестировать его без перезагрузки самого ядра, простым включением и выключением через insmod. Но что делать, если концепция модульности неприменима? Например, как в моем случае, когда потребовалось добавить новую подсистему контрольных групп (cgroups) для Jet9 и нужно было перезапускать ядро каждый раз, чтобы проверить внесенные изменения?
Читать дальше →
Total votes 21: ↑19 and ↓2 +17
Comments 1

Типобезопасные идентификаторы и фантомные типы

Reading time 4 min
Views 16K
Довольно часто в программе, работающей с базой данных, в качестве идентификаторов сущностей используются значения целочисленного типа (например, long). Но людям свойственно ошибаться, и программист может по ошибке использовать идентификатор одного типа сущности для адресации другой. Такая проблема может долго оставаться незамеченной, если идентификаторы сущностей пересекаются, а такое бывает довольно часто. К счастью, в языках, позволяющих манипулировать типами, коим является C++, есть довольно простое решение этой проблемы.
Читать дальше →
Total votes 47: ↑46 and ↓1 +45
Comments 20

Information

Rating
Does not participate
Registered
Activity