Как стать автором
Обновить
  • по релевантности
  • по времени
  • по рейтингу

Примитивная логика и кодирование информации

Чулан
Итак, довольно давно я столкнулся с довольно интересной задачкой:
Подлые оккупанты захватили деревню мегамозгов, выстроили их друг за другом в колонну так, что каждый предыдущий видит всех последующих. На каждого мегамозга надели колпак черного или белого цвета так, что ни один мегамозг не видит свой колпак. Начиная с самого последнего (того, который видит всех кроме себя) у каждого мегамозга по очереди спрашивают цвет его шляпы, если он ошибается, его убивают. Но как раз на этот случай мегамозги заранее договорились, как минимизировать число убитых. О чем договорились мегамозги?
(все ссылаются на braingames.ru, но на самом деле этот сайт — подлый плагиатор, задачка древняя, они переделали ее под свою специфику, — добавили везде мегамозгов, — и выдали за собственную)
Вначале казалось что половина убитых — радость для этой деревни. Но, немного подумав, я натолкнулся (одна девушка меня натолкнула) на довольно простое решение: мозги заранее договариваются и если цвет впереди стоящего белый, то произносится свой цвет (извини, первый мегамозг, ты в 50% случаев умрешь...) громко, иначе — тихо. Но это — примитив, хотя уже дает результат вдвое лучший — 99 мегамозгов останутся живы.
Теперь мой окончательный вариант: последний, который видит всех, считает парность, например, чёрных. Если получилось парное, говорит, что он чёрный. Он, к сожалению единственный, кто рискует погибнуть. Следующий считает парность чёрных, если парно — он белый (количество чёрных не изменилось), иначе — чёрный, следующий аналогично.

Поразило меня в решении этой задачи то, что достигнут поистине поражающий результат — вначале казалось, что спасти хотя бы больше 50% — отличный результат, однако, пожертвовав жизнью всего лишь одного из мегамозгов (в 50% случаев) можно гарантированно спасти всех остальных!
Всего голосов 14: ↑7 и ↓7 0
Просмотры517
Комментарии 28

Продолжаем решать «простые» задачи

Чулан
Вчера, в комментариях к моему вчерашнему топику кое-кто сказал о том, что решение задачи о двух цветах кепок можно обобщить.

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


Пожалуйста, опишите подробно то, о чем должны договориться пленные, чтобы гарантированно остались жить все, кроме одного.
Всего голосов 10: ↑5 и ↓5 0
Просмотры484
Комментарии 25

Соглашаемся на некачественный код?

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

Читать дальше →
Всего голосов 18: ↑13 и ↓5 +8
Просмотры260
Комментарии 6

Кодирование цифрового идентификатора

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

Однако, со временем меня перестал устраивать подобный алгоритм, а количество контейнеров в cookies захотелось сократить до минимума.
Не взыщите, если уже было (искал — на хабре не нашёл), а также если кому не понравится, да не гордости ради, а пользы для:
Алгоритм шифрования цифрового идентификатора
Всего голосов 14: ↑6 и ↓8 -2
Просмотры1.8K
Комментарии 31

Задачка с башорга

Занимательные задачки
Накопал на баше задачку, и решил ее с небольшими изменениями предложить вам:

Штирлиц должен отправить важное сообщение по в Центр.
Сообщение состоит из 4 бит информации, а общий размер передачи в центр составляет 7 бит.
Противник не дремлет, и при отправке возможны диверсии.
Любой бит информации (но только один) может быть испорчен.
Как должен Штирлиц закодировать информацию, чтобы в Центре гарантированно смогли прочитать сообщение при возможном искажении любого одного бита?

upd: И подскажите возможно ли это в принципе.

upd2: Вроде с тем что это возможно мы определились (вот, вот, вот и вот), теперь кто-нибудь может рассказать как это реализуется без высшей математики? Неохота учебник доставать, а основы немного подзабыл за ненадобностью в повседневной жизни.
Всего голосов 45: ↑31 и ↓14 +17
Просмотры744
Комментарии 41

Введение в DSL. Часть 1 — Проблематика проектирования и кодирования

Разработка веб-сайтов
На протяжении нескольких десятилетий стоит задача поиска повторяемого, предсказуемого процесса или методологии, которая бы улучшила продуктивность, качество и надежность разработки. Одни пытались систематизировать и формализовать этот, по-видимому, непредсказуемый процесс. Другие применяли к нему методы управления проектами и методы программной инженерии. Третьи считали, что без постоянного контроля со стороны заказчика разработка ПО выходит из-под контроля, что влечет за собой увеличение временных и финансовых затрат.
Информатика как научная дисциплина предлагает и использует на базе методов структурного программирования технологию надежной разработки программного обеспечения, используя тестирование программ и их верификацию на основе методов доказательного программирования для систематического анализа правильности алгоритмов и разработки программ без алгоритмических ошибок.
Данная методология направлена на решение задач на ЭВМ, аналогичной технологии разработки алгоритмов и программ, используемой на олимпиадах по программированию отечественными студентами и программистами с использованием тестирования и структурного псевдокода для документирования программ в корпорации IBM с 70-х годов.
Методология структурного проектирования программного обеспечения может использоваться с применением различных языков и средств программирования для разработки надежных программ любого назначения.
Однако при использовании классического подхода к разработке возникают проблемы, описанные под хабракатом:
Читать, какие
Всего голосов 34: ↑25 и ↓9 +16
Просмотры17.3K
Комментарии 27

Русские идентификаторы в коде

.NET
Из песочницы
Речь пойдет об использовании в программном коде названий (классов, переменных, методов) на родном языке (в моем случае — на русском).

Опыт показал, что русские идентификаторы идеально подходят для создания объектной модели и для обсуждения ее с Заказчиком (для отечественных проектов).

Читать дальше →
Всего голосов 46: ↑16 и ↓30 -14
Просмотры9.3K
Комментарии 133

Модульное тестирование — личный опыт

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

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

Читать дальше →
Всего голосов 62: ↑42 и ↓20 +22
Просмотры8.1K
Комментарии 50

Простой пример кодирования текстовой строки по Хаффману

Алгоритмы
Перевод
Вы, наверное, слышали о Дэвиде Хаффмане и его популярном алгоритме сжатия. Если нет, то предлагаю вам самостоятельно поискать в интернете — в этой статье я не буду донимать вас уроками истории или математики. Я попробую показать вам на практике, как применить этот алгоритм к текстовой строке. Наше приложение просто сгенерирует значения кода для символов из введенной строки и наборот — воссоздаст оригинальную строку из представленного кода.
Читать дальше →
Всего голосов 26: ↑17 и ↓9 +8
Просмотры39.2K
Комментарии 3

Голографические свойства бит-реверсивной перестановки

Алгоритмы
Об экспериментах с компьютерной голографией писалось неоднократно. [1, 2, 3] Мне эта тема просто любопытна. Я как-то экспериментировал с бит-реверсивной перестановкой (bit-reversal permutation) изображений и случайно обнаружил голографические свойства. Но обо всем по порядку.
Читать дальше →
Всего голосов 136: ↑131 и ↓5 +126
Просмотры43.2K
Комментарии 30

Схема разделения секретной визуальной информации

Блог компании НордавиндИнформационная безопасностьАлгоритмы
Доброго времени суток, Хабрапользователи!

Визуальная криптография [1] впервые была введена Мони Наором и Ади Шамиром в 1994 году [3]. Она используется для шифрования изображения или текста, представленного в виде изображения. Основная идея модели визуальной криптографии состоит в разбиении исходного изображения на несколько шифрованных («теневых» изображений, shadow images), каждое из которых не дает никакой информации об исходном изображении кроме, может быть, его размера (изображение – а-ля «белый шум»). При наложении шифрованных изображений друг на друга, можно получить исходное изображение. Таким образом, для декодирования не требуется специальных знаний, высокопроизводительных вычислений и даже компьютера (в случае, если распечатать теневые изображения на прозрачных пленках). В случае использования этого алгоритма в компьютерных системах, наложить все части изображения друг на друга можно используя логические операции AND, OR, XOR (или установив более высокую степень прозрачности в графическом редакторе). Данная технология обладает криптоустойчивостью за счет того, что при разделении исходного изображения на множество шифроизображений происходит случайным образом.

Читать дальше →
Всего голосов 52: ↑44 и ↓8 +36
Просмотры23.7K
Комментарии 26

ZBase32, Base32 и Base64 алгоритмы кодирования

Программирование.NETАлгоритмы
Привет!

Многие используют Base64 кодирование, реже Base32 и еще реже ZBase32 (вы знаете о таком?), но не все понимают их алгоритмы. В статье я описываю достоинства, недостатки данных кодировок, а также рассказываю о их реализации.
Читать дальше →
Всего голосов 44: ↑38 и ↓6 +32
Просмотры39.4K
Комментарии 26

Тестирование производительности различных конфигураций Swift OpenStack

Блог компании Mirantis/OpenStackOpen source
Для тех, кто еще не знаком с объектным хранилищем данный Swift OpenStack, общая информация о структуре и алгоритмах уже была приведена в нашем блоге: habrahabr.ru/company/mirantis_openstack/blog/176195, habrahabr.ru/company/mirantis_openstack/blog/176455.
Читать дальше →
Всего голосов 3: ↑2 и ↓1 +1
Просмотры4.4K
Комментарии 0

Кодирование и декодирование PHP кода

Разработка веб-сайтовPHP
Из песочницы
Recovery mode
Я занимаюсь восстановлением исходников PHP из закодированного вида.
В этой статье я расскажу о том, как обстоят дела с кодированием и декодированием PHP в настоящее время.

Очень краткий ликбез по внутреннему устройству интерпретатора PHP


При выполнении PHP-скрипта, он парсится и компилируется в опкоды внутренней виртуальной машины PHP.
Из каждого файла PHP получаются:
— массив классов: в каждом классе — информация о классе, свойства класса и массив методов класса
— массив функций
— «тело скрипта» — код вне классов и функций
Читать дальше →
Всего голосов 46: ↑38 и ↓8 +30
Просмотры65.1K
Комментарии 25

Некоторые математические проблемы информационной безопасности

Информационная безопасностьКриптографияМатематика
Recovery mode
     Наряду с политическими, социально-экономическими, организационными, военными, правовыми, специальными и информационными проблемами, решение которых предусматривается на государственном, федеральном уровне, в информационной сфере существуют проблемы математического характера, о которых в работе и пойдет речь. В работе приводятся и конкретизируются некоторые важные понятия и основные положения информационной безопасности и защиты информации. Основными нормативными документами в этой сфере являются Конституция РФ — основной закон, ФЗ О безопасности, Военная доктрина и Доктрина информационной безопасности, а также руководящие документы Федеральной службы по техническому и экспортному контролю (РД ФСТЭК)
Читать дальше →
Всего голосов 37: ↑7 и ↓30 -23
Просмотры8.2K
Комментарии 11

SAP объявляет CodeJam и приглашает покодить вместе

Блог компании SAPРазработка веб-сайтовПрограммирование
SAP входит в 5 крупнейших софтверных компаний мира. Это ко многому обязывает, в частности, к тому, что знаниями надо делиться. Что мы и запланировали сделать в рамках серии московских Кодджемов. Начинаем в 10 утра и на 5-6 часов уходим в кодирование под руководством наших зарубежных экспертов (естественно с перерывами на поесть и пообщаться).

Мы ждем:
  1. студентов — 31 марта и 1 апреля
  2. более опытных представителей мира программирования — 2 апреля

Что попробуем:
  1. Обработку больших данных в режиме реального времени (SAP HANA)
  2. Графический интефейс — модный и удобный (SAP UI5)
  3. Визуализацию данных, чтобы вычленять из них смысл (SAP Lumira)

Рабочий язык: английский
Bring your own device!


Адрес: Москва, м. Павелецкая, Космодамианская набережная, 52/5, этаж 3, из лифта направо

Читать дальше →
Всего голосов 5: ↑4 и ↓1 +3
Просмотры3.4K
Комментарии 0

GIF изнутри

АлгоритмыОбработка изображений
Из песочницы

Вам когда-нибудь было интересно, как устроены gif-ки? В данной статье попробуем разобраться с внутренним строением GIF-формата и методом сжатия LZW.

Структура GIF


Файл в формате GIF состоит из фиксированной области в начале файла, за которой располагается переменное число блоков, и заканчивается файл завершителем изображения.


Читать дальше →
Всего голосов 80: ↑74 и ↓6 +68
Просмотры44.7K
Комментарии 17

Хорошие инстинкты кодировщика в конечном итоге «ударят вас по зубам»

Блог компании TESTutorУправление разработкойGTD
Перевод
Recovery mode
image

Я написал свои первые несколько строчек кода почти 32 года назад, когда мне было 6. Я развил очень сильные инстинкты программирования и мог смотреть на любую проблему, сразу зная, как ее решить — просто интуитивно.

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

Но одной интуиции недостаточно. Я столкнулся со стеной. И никакой инстинкт кодировщика не помогал мне сквозь нее пробиться. Далее Bill Sourour поделится с нами информацией о том, как не останавливаться на достигнутом. Кому-то эти рассуждения, безусловно, покажутся очевидными. Ну, а кому-то — пригодятся.
Читать дальше →
Всего голосов 22: ↑15 и ↓7 +8
Просмотры22.2K
Комментарии 28

Шаг влево, шаг вправо — шкала. Или от абсолюта к простому порядку

Читальный зал
Так уж получилось в нашей Вселенной, что все (или почти все) сигналы природного происхождения – аналоговые. Для большинства задач их обработки, анализа, распознавания и т.п. необходимо, в первую очередь, преобразовать сигнал в цифровые данные (ведь у нас как никак век цифровых технологий, ага). Для этого используют аналого-цифровое преобразование. Тема настолько хорошо всем известная, что не о чем, вроде-бы, и говорить (за исключением конкретной техники преобразования, но статья не об этом). Однако давайте, все-таки, углубимся в эту тему и рассмотрим ее под необычным углом зрения.

image

Для применения классических процедур обработки сигналов требуется выполнение операций сложения и умножения, следовательно, требуется представление отсчетов в абсолютной шкале. А могут ли для обработки сигналов применяться другие шкалы, в каких случаях и что это дает? Об этом рассказывается в данной статье.
Читать дальше →
Всего голосов 18: ↑17 и ↓1 +16
Просмотры6.4K
Комментарии 1