Pull to refresh
139
Karma
0
Rating
Ярослав Сергиенко @pallada92

Визуализация данных и frontend в ИСИЭЗ НИУ ВШЭ

Стучимся в дверь к Тьюрингу: квантовые компьютеры и машинное обучение

Я не на 100% ориентируюсь в теме, но при помощи стандартных операций можно получить в принципе любой вещественный поворот. Только нужно проводить много промежуточных измерений и повторных операций.

iopscience.iop.org/article/10.1088/1367-2630/15/9/093041/meta

В этой работе самый мозговзрывательный момент, когда они из поворота на угол phi делают поворот на угол phi / 2 с вероятностью 1/2. До сих пор до конца не разобрал, как это работает.

Стучимся в дверь к Тьюрингу: квантовые компьютеры и машинное обучение

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

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

Есть алгоритмы в духе Quantum eigenvalue estimation и упомянутый в статье Variational Quantum Eigensolver, но они позволяют эффективно решать только конкретные задачи, которые удалось привести к определенной форме. Например, VQE позволяет найти только собственные числа матрицы, но не собственные вектора.

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

Если тут есть специалисты по квантовым вычислениям, буду рад оказаться неправ: я сам заинтересован в нахождении эффективных алгоритмов для умножения вещественных чисел на кватовых компьютерах)

Как фотка в портфолио влияет на получение работы и заказов. Обзор исследований

Да, я тоже подумал о таком аналоге FaceMash, где твои фотки или резюме оценивают ректутеры)

Исследователи смогли преодолеть барьер в улучшении решения задачи коммивояжера

С учетом того, что похожая формулировка содержится в оригинальной статье в издании Quanta Magazine, и ее автор — Erica Klarreich, доктор математических наук, которая писала статьи в том числе для Nature, я бы не был столь однозначен в отношении того, что линейное программирование не имеет отношения к информатике.

Точнее, в оригинальной статье сказано, что линейное программирование является одним из инструментов, которые позволили продвинуться в фундаментальных задачах компьютерных наук.

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

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

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

Я думал, что шахматы тут как метафора криптографических протоколов)

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

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

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

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

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

Например, играть в шахматы Фишера и seed для выбора расстановки считать на основе хэша от имен игроков.

А при доказательстве личности при покупке задавать вопросы, связанные с покупаемыми товарами, чтобы ответы на вопросы о еде в ресторане нельзя было использовать для покупки алмазов.

Трехмерный движок в коде… ДНК

Спасибо! Наверное, стоило разбить статью на несколько частей.

Фреймворк необычный, но я сходу не понял его принцип. Это что-то вроде один процесс — одна молекула?

Трехмерный движок в коде… ДНК

Не стоит, одного квайна в 2020 году вполне достаточно :)

Трехмерный движок в коде… ДНК

Спасибо! В статье затронуто несколько тем, которые обычно не встречаются вместе, поэтому для каждой придется подбирать отдельную книгу. На русском я ничего даже не пытался найти, на английском читал только статьи. Из английских книг мне показалась хорошей «An Introduction to Systems Biology: Design Principles of Biological Circuits (Chapman & Hall/CRC Mathematical and Computational Biology)», хотя я не читал ее.

Вычисляем последовательность Фибоначчи за логарифмическое время

Примерно с 65 числа Фибоначчи (17 167 680 177 565) погрешность будет около 0.037.
В любом случае это сильно больше, чем может поместится в int, который используется в коде в статье.

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

Вычисляем последовательность Фибоначчи за логарифмическое время

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

Большинство людей найдет в Гугле формулу Бине, которая даст ответ за константное время (или логарифмическое, смотря как считать возведение в степень):

image

И я не понял, с каких пор логарифмическая сложность считается лучше константной?

Или я что-то фундаментальное не понимаю в этой статье? Может, нужна оговорка, что алгоритм не может оперировать нецелыми числами?

Трехмерный движок в коде… ДНК

Я еще не определился)

Трехмерный движок в коде… ДНК

Спасибо! Это делалось в свободное от работы время: примерно два месяца ушло на изучение научных статей и прототипирование, 3 недели на написание симулятора и генерацию анимаций, еще 3 недели на написание и оформление текста статьи. Но из-за перерывов этот процесс в итоге растянулся на полтора года.

В пещерах этого не было

Тоже долго не мог найти нормальное объяснение. Мне больше всего понравилась теория, что белые клавиши были выбраны для полутонов с номерами i, для которых 2^(i/12) хорошо приближается рациональной дробью со знаменателем из степеней 2, 3 (а эти знаменатели пришли из пифагорова строя). Вот картинка, строка 12-TET. Это не объясняет все белые клавиши, но большинство.

Как npm обеспечивает безопасность

Меня всегда волновал вопрос, пытается ли кто-то проверять, соответствует ли минифицированный код npm-пакетов тому коду, что доступен в репозитории.
Это вроде как базовый шаг, который должен предшествовать поиску уязвимостей в исходном коде.
Насколько мне известно, команда npm publish позволяет публиковать произвольный минифицированный код, а инструкции по сборке не стандартизованы в package.json.

Программисты, давайте изучать исходники классических программ

Почему никто не вспомнил исходники ТеХ от Дональда Кнута, канонический пример literate programming?

Это полный код ядра издательской системы TeX, оформленный в виде книги, которая была сверстана при помощи системы, которая она описывает.

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

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

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

Единственное, что меня удивляет, что там обильно используется goto, интересно найти мнение Кнута на этот счет.

Указатели сложны, или Что хранится в байте?

Но никто в здравом уме не будет складывать годы друг с другом (2019+1942=3961 — какой в этом смысл (конечно, если 1942 — это тоже порядковый номер года, а не число лет)?) или умножать их на числа (2019*3=6057 — то же самое, особого смысла нет).

Но если мы хотим найти середину отрезка между 1942 и 2019, то нам придется как складывать порядковые числа, так и умножать их на скаляр: (1942 + 2019) * 0.5, при этом результат будет вполне осмысленным.

Многомерные графики в Python — от трёхмерных и до шестимерных

1) Если данные меняются по годам, можно добавить анимацию.
2) Каждую точку можно рисовать как смайлик, у которого размер каждого глаза, кривизна рта и т.д. кодируют по параметру. Если не задействовать цвета получится 36 измерений. Техника называется лица Чернова, вот реализация на Python

Чётные числа Фибоначчи

Кстати, есть ещё одна прикольная задача про сумму первых n четных чисел Фибоначчи, которая решается за О(1). Сумма чисел Фибоначчи от 1 до 3n равна числу Ф. с номером 3n + 2, с другой стороны это удвоенная сумма первых n четных чисел Ф. т. к. каждое чётное равно сумме двух предыдущих, а они как раз идут группами по три. То есть ответ что-то вроде F(3n+2) / 2, который считается напрямую по формуле Бине.

Information

Rating
Does not participate
Location
Москва, Москва и Московская обл., Россия
Date of birth
Registered
Activity