Pull to refresh
2
0

Software developer, C/C++, *SQL, DWH, ETL

Send message

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

Reading time 2 min
Views 9.4K

Просматривая протоколы собеседований на позицию разработчика, обнаружил такую задачу: "Предложите код, который бы выводил на печать числа в убывающем порядке от 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.

Читать дальше →
Total votes 19: ↑13 and ↓6 +7
Comments 95

С — не низкоуровневый язык

Reading time 11 min
Views 79K


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


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

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

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

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

Производители процессоров не одиноки в этом. Разработчики компиляторов C/C++ тоже внесли свою лепту.
Читать дальше →
Total votes 206: ↑198 and ↓8 +190
Comments 296

Обзор задач по алгоритмам для собеседований — генерация множеств

Reading time 7 min
Views 60K

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


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


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



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

Читать дальше →
Total votes 28: ↑28 and ↓0 +28
Comments 15

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

Reading time 15 min
Views 4.8K

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


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

Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
Лекция 2: «Контроль хакерских атак» Часть 1 / Часть 2 / Часть 3
Лекция 3: «Переполнение буфера: эксплойты и защита» Часть 1 / Часть 2 / Часть 3
Лекция 4: «Разделение привилегий» Часть 1 / Часть 2 / Часть 3
Total votes 16: ↑15 and ↓1 +14
Comments 0

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

Reading time 15 min
Views 9.9K

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


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

Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
Лекция 2: «Контроль хакерских атак» Часть 1 / Часть 2 / Часть 3
Лекция 3: «Переполнение буфера: эксплойты и защита» Часть 1 / Часть 2 / Часть 3
Лекция 4: «Разделение привилегий» Часть 1 / Часть 2 / Часть 3
Total votes 27: ↑26 and ↓1 +25
Comments 1

Курс MIT «Безопасность компьютерных систем». Лекция 3: «Переполнение буфера: эксплойты и защита», часть 3

Reading time 11 min
Views 4.3K

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


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

Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
Лекция 2: «Контроль хакерских атак» Часть 1 / Часть 2 / Часть 3
Лекция 3: «Переполнение буфера: эксплойты и защита» Часть 1 / Часть 2 / Часть 3
Total votes 15: ↑14 and ↓1 +13
Comments 0

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

Reading time 14 min
Views 6.2K

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


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

Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
Лекция 2: «Контроль хакерских атак» Часть 1 / Часть 2 / Часть 3
Лекция 3: «Переполнение буфера: эксплойты и защита» Часть 1 / Часть 2 / Часть 3
Total votes 15: ↑14 and ↓1 +13
Comments 0

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

Reading time 14 min
Views 10K

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


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

Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
Лекция 2: «Контроль хакерских атак» Часть 1 / Часть 2 / Часть 3
Лекция 3: «Переполнение буфера: эксплойты и защита» Часть 1 / Часть 2 / Часть 3
Total votes 16: ↑15 and ↓1 +14
Comments 0

Курс MIT «Безопасность компьютерных систем». Лекция 2: «Контроль хакерских атак», часть 3

Reading time 10 min
Views 7K

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


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

Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
Лекция 2: «Контроль хакерских атак» Часть 1 / Часть 2 / Часть 3
Total votes 15: ↑13 and ↓2 +11
Comments 0

Курс MIT «Безопасность компьютерных систем». Лекция 2: «Контроль хакерских атак», часть 2

Reading time 14 min
Views 8.4K

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


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

Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
Лекция 2: «Контроль хакерских атак» Часть 1 / Часть 2 / Часть 3
Total votes 15: ↑13 and ↓2 +11
Comments 0

Курс MIT «Безопасность компьютерных систем». Лекция 2: «Контроль хакерских атак», часть 1

Reading time 15 min
Views 20K

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


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

Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
Лекция 2: «Контроль хакерских атак» Часть 1 / Часть 2 / Часть 3
Total votes 17: ↑15 and ↓2 +13
Comments 1

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

Reading time 14 min
Views 26K

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


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

Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
Total votes 23: ↑22 and ↓1 +21
Comments 2

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

Reading time 14 min
Views 30K

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


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

Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
Total votes 17: ↑16 and ↓1 +15
Comments 0

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

Reading time 15 min
Views 139K

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


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

Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
Total votes 23: ↑22 and ↓1 +21
Comments 10

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

Reading time 13 min
Views 5.3K

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


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

Лекция 1: «Вступление: модели угроз» Часть 1 / Часть 2 / Часть 3
Лекция 2: «Контроль хакерских атак» Часть 1 / Часть 2 / Часть 3
Лекция 3: «Переполнение буфера: эксплойты и защита» Часть 1 / Часть 2 / Часть 3
Лекция 4: «Разделение привилегий» Часть 1 / Часть 2 / Часть 3
Total votes 24: ↑23 and ↓1 +22
Comments 0

Взломать шифр Хилла? Легко

Reading time 5 min
Views 17K

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


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

Что имеем?


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

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

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

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


Рассмотрим атаку «грубой силой». Выше было оговорено, что из алфавита исключены две буквы, поэтому все линейные комбинации при шифровании (как и при дешифровке) берутся по mod 31 (учитывая, что это простое число, текст становится чуть более безопасным).
Если рассматривать перебор обратных матриц-ключей, то всего нам придется перебрать $31^{49} $ комбинаций (это число примерно умещается в 75 знаков). Поэтому такой способ исключается моментально, хотя! Если из этого множества можно было бы каким-нибудь более-менее быстрым способом перебрать подмножество невырожденных матриц, то возможно задача облегчилась бы. К сожалению я такого способа не знаю и не уверен, что такой вообще существует!
Читать дальше →
Total votes 22: ↑20 and ↓2 +18
Comments 11

Новинки С++17, которые необходимо использовать каждому

Reading time 7 min
Views 37K
Дамы и господа, здравствуйте.

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


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

Всех — с наступающим новым годом!
Читать дальше →
Total votes 23: ↑22 and ↓1 +21
Comments 38

Rust vs. C++ на алгоритмических задачах

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

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

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

Статья построена следующим образом: в первой части я опишу основные плюсы и минусы, на которые я обратил внимание, работая с Rust. Во второй части я приведу краткое описание алгоритмических задач, которые были решены в Rust и C++, прокомментирую основные моменты реализации программ. В третьей части будет приведена таблица замера производительности программ на Rust и C++.
Читать дальше →
Total votes 79: ↑72 and ↓7 +65
Comments 216

Двоичный поиск в графах

Reading time 10 min
Views 17K

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

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

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

Что, если попробовать выполнить двоичный поиск по графу? Большинство алгоритмов поиска по графам, такие как поиск в ширину или поиск в глубину, требуют линейного времени и были придуманы довольно умными людьми. Поэтому если двоичный поиск по графу будет иметь какой-то смысл, то он должен использовать больше информации, чем та, к которой имеют доступ обычные алгоритмы поиска.
Читать дальше →
Total votes 28: ↑28 and ↓0 +28
Comments 12

Постигаем Си глубже, используя ассемблер

Reading time 8 min
Views 53K
Вдохновением послужила эта статья: Разбираемся в С, изучая ассемблер. Продолжение так и не вышло, хотя тема интересная. Многие бы хотели писать код и понимать, как он работает. Поэтому я запущу цикл статей о том, как выглядит Си-код после декомпиляции, попутно разбирая основные структуры кода.
Читать дальше →
Total votes 54: ↑50 and ↓4 +46
Comments 31

Information

Rating
Does not participate
Location
Bayern, Германия
Registered
Activity