Рубрика «Занимательные задачки» - 40

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

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

Почему этот простой с виду алгоритм работает корректно?
Читать полностью »

Пасхалка в Mr Robot S02E01 - 1

В конце первой серии второго сезона Mr Robot есть сцена, где Дарлин генерирует троян-вымогатель с помощью модифицированного фреймворка SET (Social Engineer Toolkit). Мои пальцы просто зудели, чтобы попробовать IP-адрес 192.251.68.254, где вроде как располагается управляющий сервер трояна. Неудивительно, что WHOIS показал на владельца NBC-UNIVERSAL. Посмотрим, насколько глубока кроличья нора.
Читать полностью »

Представляю вашему вниманию перевод своей статьи Amazon software engineer interview, изначально опубликованной на английском на sobit.me.

Amazon - We Pioneer

Не так давно со мной связался технический рекрутер из Amazon. Компания организовывала трехдневное онсайт собеседование по найму программистов в их берлинский офис.

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

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

Читать полностью »

Математические обозначения: Прошлое и будущее - 1

Перевод поста Стивена Вольфрама (Stephen Wolfram) "Mathematical Notation: Past and Future (2000)".
Выражаю огромную благодарность Кириллу Гузенко KirillGuzenko за помощь в переводе и подготовке публикации


Содержание

Резюме
Введение
История
Компьютеры
Будущее
Примечания
Эмпирические законы для математических обозначений
Печатные обозначения против экранных
Письменные обозначения
Шрифты и символы
Поиск математических формул
Невизуальные обозначения
Доказательства
Отбор символов
Частотное распределение символов
Части речи в математической нотации


Стенограмма речи, представленной на секции «MathML и математика в сети» первой Международной Конференции MathML в 2000-м году.


Резюме

Большинство математических обозначений существуют уже более пятисот лет. Я рассмотрю, как они разрабатывались, что было в античные и средневековые времена, какие обозначения вводили Лейбниц, Эйлер, Пеано и другие, как они получили распространение в 19 и 20 веках. Будет рассмотрен вопрос о схожести математических обозначений с тем, что объединяет обычные человеческие языки. Я расскажу об основных принципах, которые были обнаружены для обычных человеческих языков, какие из них применяются в математических обозначениях и какие нет.

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

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

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

Обычный язык состоит их строк текста; математическая нотация часто также содержит двумерные структуры. Будет обсуждён вопрос о применении в математической нотации более общих структур и как они соотносятся с пределом познавательных возможностей людей.

Сфера приложения конкретного естественного языка обычно ограничивает сферу мышления тех, кто его использует. Я рассмотрю то, как традиционная математическая нотация ограничивает возможности математики, а также то, на что могут быть похожи обобщения математики.
Читать полностью »

Пропорции в искусстве. Есть ли что-то лучше золотого сечения? Исследование более 1 000 000 старых и современных картин - 1

Перевод поста Майкла Тротта (Michael Trott) "Aspect Ratios in Art: What Is Better Than Being Golden? Being Plastic, Rooted, or Just Rational? Investigating Aspect Ratios of Old vs. Modern Paintings".
Код, приведенный в статье, можно скачать здесь.
Выражаю огромную благодарность Кириллу Гузенко KirillGuzenko за помощь в переводе и подготовке публикации


Содержание

Предисловие: золотое сечение — красивая математическая концепция
Работа Фехнера 1876 года об эстетичности прямоугольников и соотношениях сторон в картинах
Легкий старт: анализ «Artwork» — области базы знаний Wolfram Knowledgebase
Первая часть: особенности вероятностного распределения соотношений сторон
Соотношения сторон для разных веков, жанров и художников
Анализируя пять старых немецких музейных каталогов
Коллекция Кресса: четыре больших PDF файла
У нас представлены коллекции следующих галерей: Метрополитен (Metropolitan), институт искусств Чикаго, Эрмитаж, Национальная Галерея (National Gallery), Рейксмюзеум (Rijks) и Тейт Британия
Исключение в соотношениях сторон: Национальная портретная галерея
Веб-галерея изящных искусств: удобная база данных, готовая к использованию
Примечание II: важность точности в измерениях
WikiArt: еще один крупный веб-ресурс
Коллекция Французского государственного музея
Картины в итальянских церквях: высота есть всё
Смитсоновская коллекция
Большая коллекция картин в Великобритании
Нынешний рынок изящных искусств: рациональней чем когда-либо
Проданные картины: большинство написаны недавно, а у распределения длинный хвост
Восток: все показатели отличаются
Пропорции пакетов, автомобилей, этикеток, логотипов, эмблем, бумаги, банкнот, почтовых марок и фильмов
Продукты из супермаркета
Винные этикетки
Этикетки немецких сортов пива
Логотипы продуктов питания
Банкноты
Размеры автомобилей
Бумажные листы
Марки
Эмблемы команд NCAA (Национальной ассоциации студенческого спорта)
Эмблемы немецких футбольных клубов
Форматы фильмов
Заключение: так какое соотношение самое «лучшее»?


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

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

Путешествие в Onionland: взлом скрытого сервиса из даркнета в задании NeoQUEST-2016 - 1 Пока продолжается регистрация на питерскую «очную ставку» NeoQUEST-2016, посетить которую может любой желающий, мы продолжаем разбирать задания online-этапа.

И на очереди задание «Эти горькие луковые слёзы», в котором участникам предстояло взломать скрытый сервис, расположенный в даркнете Onionland. Доступ к таким сервисам возможен только через сеть Tor и только по имени, но в остальном они ничем не отличаются от обычных сайтов. Было два принципиально разных способа решения задания:

  • поиск уязвимости «вручную»;
  • настройка сканера веб-уязвимостей для работы с .onion-сайтами.

Разбор обоих способов — под катом!
Читать полностью »

Что такое пространство-время на самом деле? - 1

Перевод поста Стивена Вольфрама "What Is Spacetime, Really?".
Выражаю огромную благодарность Кириллу Гузенко KirillGuzenko за помощь в переводе и подготовке публикации.

Примечание: данный пост Стивена Вольфрама неразрывно связан с теорией клеточных автоматов и других смежных понятий, а также с его книгой A New Kind of Science (Новый вид науки), на которую из этой статьи идёт большое количество ссылок. Пост хорошо иллюстрирует применение программирования в научной сфере, в частности, Стивен показывает (код приводится в книге) множество примеров программирования на языке Wolfram Language в области физики, математики, теории вычислимости, дискретных систем и др.


Содержание

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


Сто лет назад Альберт Эйнштейн опубликовал общую теорию относительности — блестящую, элегантную теорию, которая пережила целый век и открыла единственный успешный путь к описанию пространства-времени (пространственно-временного континуума).

Есть много различных моментов в теории, указывающих, что общая теория относительности — не последняя точка в истории о пространстве-времени. И в самом деле, пускай мне нравится ОТО как абстрактная теория, однако я пришел к мысли, что она, возможно, на целый век увела нас от пути познания истинной природы пространства и времени.

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

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

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

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

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

По случайности, все трое призёров предпочли участвовать под псевдонимами. Мне кажется, с такими результатами им нечего стесняться. Если вы хотите представиться в комментариях, милости просим!

Итак, призовые места заняли:

  1. Antelle — 83.67% правильных ответов. Приз 3000 USD.
  2. SHB — 83.11% правильных ответов. Приз 2000 USD.
  3. chianti — 83.00% правильных ответов. Приз 1000 USD.

Читать полностью »

Это все потому, что у кого-то слишком маленькая экспонента: атака Хастада на RSA в задании NeoQUEST-2016 - 1 Продолжаем разбирать задания online-этапа NeoQUEST-2016 и готовимся к "очной ставке", куда приглашаем всех желающих! Вас ждут интересные доклады, демонстрации атак, конкурсы, призы и многое другое!

Редкий хак-квест обходится без криптографии, ну и NeoQUEST-2016 не стал исключением! В задании online-этапа наш выбор пал на криптосистему RSA, о безопасности которой можно говорить много и долго. В образовательно-познавательных целях, мы взяли не самую популярную атаку на RSA – атаку Хастада.

Кроме этого, мы порядком запутали участников, не предоставив им (на первый взгляд!) никаких исходных данных к заданию. О том, где нужно было искать, что делать с найденным и как реализовать атаку Хастада – читаем под катом!
Читать полностью »

Спасибо за ожидание! Публикуем предварительные результаты конкурса по программированию.

Протестировано 312 решений, из них 50 упало или зависло, ещё 3 оказались слишком медленными, чтобы пройти все тесты. Из оставшихся 259 решений 12 по разным причинам были объявлены «вне конкурса»: решения не работали без поправки типа файла данных (авторы забыли галочку «gzip») или были присланы сотрудниками Hola.

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

Решение победителя конкурса показало результат в 83.67% правильных ответов. Полные списки решений с результатами тестирования находятся в английской версии поста на GitHub.

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


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js