• Интересная задачка на С

    Просматривая протоколы собеседований на позицию разработчика, обнаружил такую задачу: "Предложите код, который бы выводил на печать числа в убывающем порядке от n до 0, не используя (скрыто или явно) операторы сравнения (реализация функции вывода на печать не в счет)". Несмотря на то, что ко мне эта задача не имела отношения, она меня заняла и я решил подумать над способами ее решения (хотя, кому и при решении какой задачи может понадобиться такой метод оптимизации кода, мне осталось неизвестно, но тем не менее ).


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


    template<int n> 
    void print()
    {
        printf("%d\n", n);
        print<n - 1>();
    }
    
    template<>
    void print<0>()
    {
        printf("0\n");
    }
    
    int main(int argc, char* argv[])
    {
        print<N>();
        return 0;
    }

    Проблема в том, что программирование это инженерная дисциплина, а не оккультная, и если "что-то" должно в системе происходить, то "оно" должно быть описано и под это должны быть выделены ресурсы, и в данном случае, поскольку отработка шаблонов происходит на этапе компиляции, есть ограницения на вложенность подобного рода конструкций (и это хорошо и правильно, и Слава Богу, что так есть), и компилятор совершенно справедливо выдал "fatal error C1202: recursive type or function dependency context too complex" при размере N больше 2000.

    Читать дальше →
  • Шпаргалка для программистов или «мы погуглим за вас»

    Введение, которое можно не читать


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

    Читать дальше →
  • С — не низкоуровневый язык

    • Translation


    Ваш компьютер не является быстрой версией PDP-11


    Привет, Хабр!

    Меня зовут Антон Довгаль, я С (и не только) разработчик в Badoo.

    Мне попалась на глаза статья Дэвида Чизнэлла, исследователя Кембриджского университета, в которой он оспаривает общепринятое суждение о том, что С — язык низкого уровня, и его аргументы мне показались достаточно интересными.

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

    Производители процессоров не одиноки в этом. Разработчики компиляторов C/C++ тоже внесли свою лепту.
    Читать дальше →
  • Обзор задач по алгоритмам для собеседований — генерация множеств

    Привет, Хабр!


    Этим постом начинается разбор задачек по алгоритмам, которые крупные IT-компании (Mail.Ru Group, Google и т.п.) так любят давать кандидатам на собеседованиях (если плохо пройти собеседование по алгоритмам, то шансы устроиться на работу в компанию мечты, увы, стремятся к нулю). В первую очередь этот пост полезен для тех, кто не имеет опыта олимпиадного программирования или тяжеловесных курсов по типу ШАДа или ЛКШ, в которых тематика алгоритмов разобрана достаточно серьезно, или же для тех, кто хочет освежить свои знания в какой-то определенной области.


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



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

    Читать дальше →
  • Курс MIT «Безопасность компьютерных систем». Лекция 4: «Разделение привилегий», часть 3

    • Translation
    • Tutorial

    Массачусетский Технологический институт. Курс лекций #6.858. «Безопасность компьютерных систем». Николай Зельдович, Джеймс Микенс. 2014 год


    Computer Systems Security — это курс о разработке и внедрении защищенных компьютерных систем. Лекции охватывают модели угроз, атаки, которые ставят под угрозу безопасность, и методы обеспечения безопасности на основе последних научных работ. Темы включают в себя безопасность операционной системы (ОС), возможности, управление потоками информации, языковую безопасность, сетевые протоколы, аппаратную защиту и безопасность в веб-приложениях.

    Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
    Лекция 2: «Контроль хакерских атак» Часть 1 / Часть 2 / Часть 3
    Лекция 3: «Переполнение буфера: эксплойты и защита» Часть 1 / Часть 2 / Часть 3
    Лекция 4: «Разделение привилегий» Часть 1 / Часть 2 / Часть 3
    Читать дальше →
  • Курс MIT «Безопасность компьютерных систем». Лекция 4: «Разделение привилегий», часть 1

    • Translation
    • Tutorial

    Массачусетский Технологический институт. Курс лекций #6.858. «Безопасность компьютерных систем». Николай Зельдович, Джеймс Микенс. 2014 год


    Computer Systems Security — это курс о разработке и внедрении защищенных компьютерных систем. Лекции охватывают модели угроз, атаки, которые ставят под угрозу безопасность, и методы обеспечения безопасности на основе последних научных работ. Темы включают в себя безопасность операционной системы (ОС), возможности, управление потоками информации, языковую безопасность, сетевые протоколы, аппаратную защиту и безопасность в веб-приложениях.

    Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
    Лекция 2: «Контроль хакерских атак» Часть 1 / Часть 2 / Часть 3
    Лекция 3: «Переполнение буфера: эксплойты и защита» Часть 1 / Часть 2 / Часть 3
    Лекция 4: «Разделение привилегий» Часть 1 / Часть 2 / Часть 3
    Читать дальше →
    • +25
    • 8.9k
    • 1
  • Курс MIT «Безопасность компьютерных систем». Лекция 3: «Переполнение буфера: эксплойты и защита», часть 3

    • Translation
    • Tutorial

    Массачусетский Технологический институт. Курс лекций #6.858. «Безопасность компьютерных систем». Николай Зельдович, Джеймс Микенс. 2014 год


    Computer Systems Security — это курс о разработке и внедрении защищенных компьютерных систем. Лекции охватывают модели угроз, атаки, которые ставят под угрозу безопасность, и методы обеспечения безопасности на основе последних научных работ. Темы включают в себя безопасность операционной системы (ОС), возможности, управление потоками информации, языковую безопасность, сетевые протоколы, аппаратную защиту и безопасность в веб-приложениях.

    Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
    Лекция 2: «Контроль хакерских атак» Часть 1 / Часть 2 / Часть 3
    Лекция 3: «Переполнение буфера: эксплойты и защита» Часть 1 / Часть 2 / Часть 3
    Читать дальше →
  • Курс MIT «Безопасность компьютерных систем». Лекция 3: «Переполнение буфера: эксплойты и защита», часть 2

    • Translation
    • Tutorial

    Массачусетский Технологический институт. Курс лекций #6.858. «Безопасность компьютерных систем». Николай Зельдович, Джеймс Микенс. 2014 год


    Computer Systems Security — это курс о разработке и внедрении защищенных компьютерных систем. Лекции охватывают модели угроз, атаки, которые ставят под угрозу безопасность, и методы обеспечения безопасности на основе последних научных работ. Темы включают в себя безопасность операционной системы (ОС), возможности, управление потоками информации, языковую безопасность, сетевые протоколы, аппаратную защиту и безопасность в веб-приложениях.

    Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
    Лекция 2: «Контроль хакерских атак» Часть 1 / Часть 2 / Часть 3
    Лекция 3: «Переполнение буфера: эксплойты и защита» Часть 1 / Часть 2 / Часть 3
    Читать дальше →
  • Курс MIT «Безопасность компьютерных систем». Лекция 3: «Переполнение буфера: эксплойты и защита», часть 1

    • Translation
    • Tutorial

    Массачусетский Технологический институт. Курс лекций #6.858. «Безопасность компьютерных систем». Николай Зельдович, Джеймс Микенс. 2014 год


    Computer Systems Security — это курс о разработке и внедрении защищенных компьютерных систем. Лекции охватывают модели угроз, атаки, которые ставят под угрозу безопасность, и методы обеспечения безопасности на основе последних научных работ. Темы включают в себя безопасность операционной системы (ОС), возможности, управление потоками информации, языковую безопасность, сетевые протоколы, аппаратную защиту и безопасность в веб-приложениях.

    Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
    Лекция 2: «Контроль хакерских атак» Часть 1 / Часть 2 / Часть 3
    Лекция 3: «Переполнение буфера: эксплойты и защита» Часть 1 / Часть 2 / Часть 3
    Читать дальше →
  • Курс MIT «Безопасность компьютерных систем». Лекция 2: «Контроль хакерских атак», часть 3

    • Translation
    • Tutorial

    Массачусетский Технологический институт. Курс лекций #6.858. «Безопасность компьютерных систем». Николай Зельдович, Джеймс Микенс. 2014 год


    Computer Systems Security — это курс о разработке и внедрении защищенных компьютерных систем. Лекции охватывают модели угроз, атаки, которые ставят под угрозу безопасность, и методы обеспечения безопасности на основе последних научных работ. Темы включают в себя безопасность операционной системы (ОС), возможности, управление потоками информации, языковую безопасность, сетевые протоколы, аппаратную защиту и безопасность в веб-приложениях.

    Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
    Лекция 2: «Контроль хакерских атак» Часть 1 / Часть 2 / Часть 3
    Читать дальше →
  • Курс MIT «Безопасность компьютерных систем». Лекция 2: «Контроль хакерских атак», часть 2

    • Translation
    • Tutorial

    Массачусетский Технологический институт. Курс лекций #6.858. «Безопасность компьютерных систем». Николай Зельдович, Джеймс Микенс. 2014 год


    Computer Systems Security — это курс о разработке и внедрении защищенных компьютерных систем. Лекции охватывают модели угроз, атаки, которые ставят под угрозу безопасность, и методы обеспечения безопасности на основе последних научных работ. Темы включают в себя безопасность операционной системы (ОС), возможности, управление потоками информации, языковую безопасность, сетевые протоколы, аппаратную защиту и безопасность в веб-приложениях.

    Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
    Лекция 2: «Контроль хакерских атак» Часть 1 / Часть 2 / Часть 3
    Читать дальше →
  • Курс MIT «Безопасность компьютерных систем». Лекция 2: «Контроль хакерских атак», часть 1

    • Translation
    • Tutorial

    Массачусетский Технологический институт. Курс лекций #6.858. «Безопасность компьютерных систем». Николай Зельдович, Джеймс Микенс. 2014 год


    Computer Systems Security — это курс о разработке и внедрении защищенных компьютерных систем. Лекции охватывают модели угроз, атаки, которые ставят под угрозу безопасность, и методы обеспечения безопасности на основе последних научных работ. Темы включают в себя безопасность операционной системы (ОС), возможности, управление потоками информации, языковую безопасность, сетевые протоколы, аппаратную защиту и безопасность в веб-приложениях.

    Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
    Лекция 2: «Контроль хакерских атак» Часть 1 / Часть 2 / Часть 3
    Читать дальше →
    • +13
    • 18.3k
    • 1
  • Курс MIT «Безопасность компьютерных систем». Лекция 1: «Вступление: модели угроз», часть 3

    • Translation
    • Tutorial

    Массачусетский Технологический институт. Курс лекций #6.858. «Безопасность компьютерных систем». Николай Зельдович, Джеймс Микенс. 2014 год


    Computer Systems Security — это курс о разработке и внедрении защищенных компьютерных систем. Лекции охватывают модели угроз, атаки, которые ставят под угрозу безопасность, и методы обеспечения безопасности на основе последних научных работ. Темы включают в себя безопасность операционной системы (ОС), возможности, управление потоками информации, языковую безопасность, сетевые протоколы, аппаратную защиту и безопасность в веб-приложениях.

    Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
    Читать дальше →
    • +21
    • 23.6k
    • 2
  • Курс MIT «Безопасность компьютерных систем». Лекция 1: «Вступление: модели угроз», часть 2

    • Translation

    Массачусетский Технологический институт. Курс лекций #6.858. «Безопасность компьютерных систем». Николай Зельдович, Джеймс Микенс. 2014 год


    Computer Systems Security — это курс о разработке и внедрении защищенных компьютерных систем. Лекции охватывают модели угроз, атаки, которые ставят под угрозу безопасность, и методы обеспечения безопасности на основе последних научных работ. Темы включают в себя безопасность операционной системы (ОС), возможности, управление потоками информации, языковую безопасность, сетевые протоколы, аппаратную защиту и безопасность в веб-приложениях.

    Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
    Читать дальше →
  • Курс MIT «Безопасность компьютерных систем». Лекция 1: «Вступление: модели угроз», часть 1

    • Translation

    Массачусетский Технологический институт. Курс лекций #6.858. «Безопасность компьютерных систем». Николай Зельдович, Джеймс Микенс. 2014 год


    Computer Systems Security — это курс о разработке и внедрении защищенных компьютерных систем. Лекции охватывают модели угроз, атаки, которые ставят под угрозу безопасность, и методы обеспечения безопасности на основе последних научных работ. Темы включают в себя безопасность операционной системы (ОС), возможности, управление потоками информации, языковую безопасность, сетевые протоколы, аппаратную защиту и безопасность в веб-приложениях.

    Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
    Читать дальше →
  • Курс MIT «Безопасность компьютерных систем». Лекция 4: «Разделение привилегий», часть 2

    • Translation
    • Tutorial

    Массачусетский Технологический институт. Курс лекций #6.858. «Безопасность компьютерных систем». Николай Зельдович, Джеймс Микенс. 2014 год


    Computer Systems Security — это курс о разработке и внедрении защищенных компьютерных систем. Лекции охватывают модели угроз, атаки, которые ставят под угрозу безопасность, и методы обеспечения безопасности на основе последних научных работ. Темы включают в себя безопасность операционной системы (ОС), возможности, управление потоками информации, языковую безопасность, сетевые протоколы, аппаратную защиту и безопасность в веб-приложениях.

    Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
    Лекция 2: «Контроль хакерских атак» Часть 1 / Часть 2 / Часть 3
    Лекция 3: «Переполнение буфера: эксплойты и защита» Часть 1 / Часть 2 / Часть 3
    Лекция 4: «Разделение привилегий» Часть 1 / Часть 2 / Часть 3
    Читать дальше →
  • Взломать шифр Хилла? Легко

    Цель: взломать шифр Хилла


    Доброго времени суток, уважаемые читатели! Сегодня я хотел поделиться способом, который помог мне вскрыть текст, зашифрованный методом Хилла. Что такое метод Хилла описывать не буду: до меня уже постарались опытные умельцы донести особенности данного способа. Ссылка на пост.

    Что имеем?


    Скажу сразу, что на руках не имелось ни открытого текста, ни ключа. Было известно, что текст длинной 6286 символов был зашифрован матрицей 7 х 7. Поэтому для нашего же удобства, мы разобьем текст на 898 строчек по 7 символов. В тексте не содержатся буквы 'ё' и 'ъ'. В целях благоразумства, я не буду приводить весь зашифрованный текст, а лишь его часть:

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

    На вид бессмысленная ерунда, пока что…

    Как будем ломать?


    Рассмотрим атаку «грубой силой». Выше было оговорено, что из алфавита исключены две буквы, поэтому все линейные комбинации при шифровании (как и при дешифровке) берутся по mod 31 (учитывая, что это простое число, текст становится чуть более безопасным).
    Если рассматривать перебор обратных матриц-ключей, то всего нам придется перебрать $31^{49} $ комбинаций (это число примерно умещается в 75 знаков). Поэтому такой способ исключается моментально, хотя! Если из этого множества можно было бы каким-нибудь более-менее быстрым способом перебрать подмножество невырожденных матриц, то возможно задача облегчилась бы. К сожалению я такого способа не знаю и не уверен, что такой вообще существует!
    Читать дальше →
  • Новинки С++17, которые необходимо использовать каждому

    • Translation
    Дамы и господа, здравствуйте.

    Мы как раз закончили перевод интересной книги Яцека Галовица о STL С++ 17, которую надеемся выпустить чем раньше, тем лучше.


    Сегодня же мы хотим предложить вашему вниманию перевод статьи Джулиана Темплмана с сайта «O'Reilly» с небольшим анонсом возможностей стандартной библиотеки нового стандарта С++.

    Всех — с наступающим новым годом!
    Читать дальше →
  • Rust vs. C++ на алгоритмических задачах

    Не так давно я стал присматриваться к языку программирования Rust. Прочитав Rustbook, изучив код некоторых популярных проектов, я решил своими руками попробовать этот язык программирования и своими глазами оценить его преимущества и недостатки, его производительность и эко-систему.

    Язык Rust позиционирует себя, как язык системного программирования, поэтому основным его vis-à-vis следует называть C/C++. Сравнивать же молодой и мультипарадигмальный Rust, который поддерживает множество современных конструкций программирования (таких, как итераторы, RAII и др.) с «голым» C я считаю не правильно. Поэтому в данной статье речь пойдет об сравнении с C++.

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

    Статья построена следующим образом: в первой части я опишу основные плюсы и минусы, на которые я обратил внимание, работая с Rust. Во второй части я приведу краткое описание алгоритмических задач, которые были решены в Rust и C++, прокомментирую основные моменты реализации программ. В третьей части будет приведена таблица замера производительности программ на Rust и C++.
    Читать дальше →
  • Двоичный поиск в графах

    • Translation

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

    При каждом сравнении алгоритм двоичного поиска разбиваем пространство поиска пополам. Благодаря этому всегда будет не более $\log(n)$ сравнений со временем выполнения $O(\log n)$. Красиво, эффективно, полезно.

    Но всегда можно посмотреть под другим углом.

    Что, если попробовать выполнить двоичный поиск по графу? Большинство алгоритмов поиска по графам, такие как поиск в ширину или поиск в глубину, требуют линейного времени и были придуманы довольно умными людьми. Поэтому если двоичный поиск по графу будет иметь какой-то смысл, то он должен использовать больше информации, чем та, к которой имеют доступ обычные алгоритмы поиска.
    Читать дальше →