• Доступное объяснение гипотезы Римана
    +7

    Простые числа и теория чисел нужны в конечных полях, которые применяются, помимо криптографии, в помехоустойчивом кодировании (типа кодов Рида-Соломона из классики).

  • Почему единицу не относят к простым числам, и когда её вообще начали считать числом
    0

    Есть и детерминированный (не вероятностный) тест на простоту.


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

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


    Доказательство есть в английской Википедии: пусть есть многочлен P(x), который принимает только простые значения. Тогда, в частности, P(1) простое, обозначим его p. Тогда P(1) сравнимо с 0 по модулю p. Однако тогда для произвольного целого k P(1+kp) тоже сравнимо с 0 по модулю p, то есть тоже делится на p. Но если P(1+kp) простое, что P(1+k*p)=p. То есть многочлен в бесконечном количестве точек равен p, следовательно, многочлен — константа.

  • Почему единицу не относят к простым числам, и когда её вообще начали считать числом
    0

    Какое отношение свойства физических объектов ("вычислительные возможности компьютеров") имеют отношение к абстрактным объектам из математики (тот самый полином Матиясевича)?

  • Почему единицу не относят к простым числам, и когда её вообще начали считать числом
    0

    Определить "формулу" мы можем либо очень узко (вроде "можно использовать только арифметические операции", тогда там вообще ничего разумного не сделать), либо так, что получается выражать произвольные алгоритмы. А написать программу для вычисления простых чисел, конечно же, можно. Про это есть прекрасный ответ на английском от Alon Amit на Quora.


    Например, вот формула, которая выдаёт 1, если число простое, и 0 иначе (взята из ответа выше):



    Как работает: надо проверить, что для каждого числа от 2 до n-1 выражение n%d не равно нулю. Другими словами, все выражения вида d-(n%d) равны нулю. А деление на d с округлением вниз — это как раз такой "if". То есть внутренняя сумма — это количество делителей числа n от 2 до n-1.


    Если захотим выразить простое число под номером n, это тоже легко делается через P(n):



    Тут мы просто нашли минимальное m такое, что от 2 до m встречается ровно n простых чисел.


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

  • Почему единицу не относят к простым числам, и когда её вообще начали считать числом
    +1

    Какие-то теоремы чуть проще формулировать, если единицу простым числом не считать. Например, основная теорема арифметики, которая упоминается в статье.


    Какие-то теоремы про простые числа тогда также хорошо обобщаются на более общие структуры вроде целых чисел (а не натуральных) и гауссовых целых чисел. Получаем одно общее определение — удобнее работать.

  • Почему единицу не относят к простым числам, и когда её вообще начали считать числом
    +2

    Да, вполне себе практикуется, когда надо перемножить произвольное число членов. С суммой аналогично, например, сумма квадратов чисел от 1 до n:



    Тут вполне разумно считать, что для n=1 эта сумма равна своему единственному члену

  • Почему единицу не относят к простым числам, и когда её вообще начали считать числом
    +1
    Произведение из одного элемента: самого простого числа. Примерно как SUM(1)=1 в SQL.
  • Максимально вырожденная игра на общение
    +7

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


    Скажем, если считать, что "равные треугольники" — это те, которые можно перевести друг в друга движением или изометрией, то тут мы уже явно разрешаем симметрию, потому что она не влияет на расстояния между точками. Если захотеть явно запретить симметрию, то сформулировать это в терминах точек и расстояний/углов между ними не получится, потребуется вводить ещё что-то.

  • Как попасть на стажировку в Google
    –1
    Скорее чуть меньше трёх месяцев (12 недель — нормальная длительность). Университету совершенно необязательно формально «отпускать» студента (если только не в Цюрих, там вроде требуется бумажка сложнее, чем справка об обучении, но я не уверен).

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

    Например, можно сдать всю сессию досрочно и тогда всё лето свободно, больше 12 недель, пропусков нет. Можно нормально сдать сессию в июне, уехать в июле, приехать в конце сентября, тогда пропускается всего один месяц семестра из четырёх. Можно комбинировать: сдать пару экзаменов досрочно, сдвинуть начало стажировки, пропустить всего пару недель в сентябре. Чисто теоретически можно даже домашние задания на стажировке делать, но это нетривиальное совмещение.
  • Как попасть на стажировку в Google
    0
    Вроде бы там не требуется подтверждать, что вы в США.

    > Pittsburgh, PA, USA
    Это формальное местоположение конкретной вакансии, не имеет отношения к местоположению кандидата.

    > Note: By applying to this position your application is automatically submitted to the following locations: Mountain View, CA, USA;…

    Тут пишут, что при подаче на эту вакансию автоматически отправляются заявки на аналогичные вакансии в куче остальных мест, т.е. это заявка сразу на всё США. Впрочем, можно будет отфильтровать на стадии host matching, если очень хочется.

    > Preferred qualifications:
    > Authorization to legally work in the United States.

    Желательные (но не обязательные) требования: разрешение на работу в США. Если его нет — наверняка сделают J-1.
  • Дейкстра за линейное время
    0
    Корректность проверялась путем проверки полного совпадения массива d расстояний.

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


    показавшие полное совпадение длины кратчайшего пути от 1000 рандомных узлов до 1000 других рандомных узлов на графе.
  • Дейкстра за линейное время
    0

    Да, неточно выразился, бинарная куча (binary heap) и подразумевалась. Это получится этакая оптимизация стандартного алгоритма с двоичной кучей, просто в которой куча разделена на несколько корзин. Мне кажется, чем-то напоминает radix sort.


    Не очень понял, что вы подразумеваете под "сравнением без if'ов". Можете пояснить? Я не понимаю, чем ваша реализация принципиально лучше массива boolean, кроме того, что может занимать меньше места. А вообще в Java есть встроенный битовый массив — BitSet.

  • Дейкстра за линейное время
    +1
    Как проверялась корректность реализации? Например, верно ли, что ответы двух реализаций (стандартной и с корзинами) совпали на всех вершинах графа при поиске расстояний от фиксированной вершины `V`?

    Не пробовали ли вы в каждой ячейке воспользоваться обычной кучей (например, для Java это `PriorityQueue`) вместо массива?

    Есть ли какой-то смысл в написании своей реализации `BitArray` и частичной реализации `ArrayList` внутри `NewSortedHashMapEntry`?

    А каковы длины дуг? Например, если длина дуги всегда больше, чем размер корзины, то можно отсортировать каждую корзину перед её первым посещением и появится гарантия, что каждая вершина посещается не больше одного раза. Ну или можно просто отсортировать и посмотреть, что будет. Или сделать `Collections.shuffle` перед первым проходом.
  • Что не так с std::visit в современном C++
    +4
    Мы начали с простой цели: посмотреть на содержимое сигма-типа.

    Есть же способы проще visit, особенно если мы хотим проверить один конкретный случай:


    • std::size_t std::variant::index(), который вернёт номер варианта.
    • bool std::holds_alternative<T>(), который проверит, верно ли, что внутри лежит T.
    • std::get<T>() и std::get<std::size_t>(), которые позволяют получить значение по типу или номеру.
  • Горячие клавиши Android Studio, которые могут увеличить вашу производительность на 100%
    0
    Ctrl+Shift+A — найти команду по имени и выполнить (если не хочется искать в менюшках)
    Ctrl+Shift+N — перейти в файл по имени (мне кажется, работает лучше Shift+Shift)
    Alt+Enter — исправить ошибку под курсором (quick fix)
  • Новый тренд на IT-собеседованиях: целые дни неоплачиваемой домашней работы
    +2
    Если найм международный и требуется оформление рабочей визы и переезд сотрудника, то хорошо бы не тратить тысячи долларов и недели-месяцы на всё это дело.
  • Boston Dynamics научила роботов помогать друг другу
    0
    Во втором варианте включается столько разных неизвестных, что всё равно надо делать что-то весьма нетривиальное. Даже если мы точно знаем, где стоит банка и откуда стартует робот, то простое проскальзывание одной ноги на полсантиметра испортит все расчёты.
  • Как я олимпиаду на Java писал или почему лучше не пользоваться Scanner
    +1
    С такими проблемами я не встречался, их решения наверняка есть в справочниках

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


    В Москве

    А вот это неожиданно. В Москве, мне казалось, с организацией должно быть всё очень на уровне. Про Visual Studio неудобная проблема.

  • Как я олимпиаду на Java писал или почему лучше не пользоваться Scanner
    0
    и код понятный

    Очень легко написать непонятный код. Или, что хуже — код с undefined behavior.


    и заморочек с платформами нет

    Расскажите это вводу-выводу 64-битных целых чисел (вроде long long) и 80-битных вещественных (long double). Не все компиляторы умеют (даже через iostream), те, что умеют — делают это по-разному. А ещё иногда от ключей компиляции могут менять поведение. И предупреждения компилятора, разумеется, тоже не всегда соответствуют действительности.


    (последние два года мне вообще в блокноте приходится писать на C++ вслепую за отсутствием каких бы то ни было IDE

    Это вы про региональный этап всероссийской олимпиады школьников по информатике? А что за регион?

  • Как я олимпиаду на Java писал или почему лучше не пользоваться Scanner
    0
    На простых задачах, где можно сделать действительно линейное решение без структур — может и да. На сложных задачах на структуры данных подгонят под питон смерти подобно — линия на питоне может работать дольше квадрата на C++.
  • Россия заняла первое место на Всемирной олимпиаде роботов
    +5
    А в чём проблема креативить в конструкции робота из LEGO и программе? Там вполне себе неплохой простор для фантазии.
  • Как отлаживать маленькие программы
    0
    В компиляторах обычно есть множество различных предупреждений, которые они умеют выдавать. Некоторые включены по умолчанию, некоторые выключены. Разными флагами можно включать разные поднаборы. Скажем, в GCC даже флаг -Wall включает далеко не всё, но уже больше, чем по умолчанию.
  • Как отлаживать маленькие программы
    0
    О, да вы почти (или не почти) страж ночи.
  • Как отлаживать маленькие программы
    +6
    Есть: «переменная нигде не используется».

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

    20 строк кода разбить код на методы поменьше? Сколько методов м.б. в программе в 20 строк?!

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

    Специально не ищу, но если случайно попалось на глаза и сразу вижу ошибку, то почему не помочь?


    +1

    Поэтому: не бойтесь спрашивать по существу!


    +1, но отлаживать самостоятельно тоже хорошо бы научиться. Мне кажется, если всё сваливать на добрых людей, то непонятно, как они находят самые коварные баги, хотя там всё более-менее алгоритмизированно (по модулю знаний о специфических подставах языка). Так что тут нужна, прошу прощения, «золотая середина».

  • Как отлаживать маленькие программы
    +6
    Зачем писал исходный автор — не знаю. Я решил перевести, потому что тут перечислены практически все стандартные ответы на фразу «оно не работает». Более того — не только перечислены, но и описано, почему то или другое надо попробовать, а также как именно это надо пробовать.
    Скажем, если человек не знает, что полезно делить программу на кусочки в процессе отделки, то ему можно кинуть ссылку на эту статью.
  • Telegram сам добавляет чужие контакты? Это норма
    +1
    Насколько я понимаю, соответствующее API у сервера есть: getContacts, deleteContacts. Правда, не уверен, что эти методы возвращают в том числе и не-пользователей Telegram. Призываю какого-нибудь экспериментатора собрать консольный клиент и ввести команды contact_list и suggested_contacts.
  • Код Прюфера
    0

    Мы знаем количество деревьев на 1, 2, 3, ..., N вершинах. Выберем сначала с соответствующими вероятностями число вершин (т.е. выбираем число K с вероятностью, пропорциональной K^{K-2}), а потом сгенерируем дерево на ровно K вершинах.

  • Код Прюфера
    0

    При этом, стоит заметить, генерация дерева на не более чем N вершинах через генерацию на ровно N вершинах довольно легко выражается

  • Код Прюфера
    0

    Вот есть множество всех деревьев на N вершинах, их конечно, а точнее — N^{N-2} по теореме Кэли. Давайте их как-нибудь занумеруем, потом выберем случайное число от 1 до N^{N-2} равновероятно (т.е. каждое число выбирается с одинаковой вероятностью), возьмём дерево с таким номером.

  • Код Прюфера
    0

    Сгенерировать произвольное дерево на ровно N пронумерованных вершинах.

  • Код Прюфера
    0

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

  • Финал чемпионата мира по спортивному программированию ACM ICPC: прямая трансляция
    +2

    Конкретно на финале — нет, участники обязаны прийти на само соревнование в выданных футболках. Если холодно — под них можно надеть кофту. Случаи ненадевания мне неизвестны.


    Цвет участники выбирают сами из здоровенного списка за некоторое время до финала.

  • Как студенты становятся продвинутыми программистами
    0
    до первого места не хватило всего 6 баллов

    Эх, опять стандартная ошибка незнакомых с олимпиадами: не до "первого места", а до золотой медали (которые вручаются 1/12 всех участников). В том году "золото" получили 24 участника, Геннадий занял 26 место.
  • Вы неправильно пишете животных
    +5
    Нормально смёржили.
  • Go для системных администраторов. Практические примеры. Часть 0
    +4
    Offtopic: побороть cmd.exe вам поможет delayed expansion. Пример:

    setlocal enabledelayedexpansion
    
    echo %time%
    ping 127.0.0.1 -n 1 -w 1000 >nul 2>&1
    echo %time%
    if 1 neq 0 (
      echo %time% !time!
      ping 127.0.0.1 -n 1 -w 1000 >nul 2>&1
      echo %time% !time!
    )
    
  • Об образовательной робототехнике и кружках
    0
    Среда программирования меняется и их очень много. Например, в центре робототехники ФМЛ 239 в Санкт-Петербурге на исходной (NXT-G) вообще никто не программирует — она слишком тормозная, громоздкая и мало чего позволяет (по крайней мере так было лет пять назад и вряд ли что-то поменялось — она не для серьёзных программ создаётся).

    Начинают с ROBOLAB (первый год, это надстройка над LabVIEW, практически блок-схемы), второй год — RobotC (правда, указатели нигде при работе не нужны, так что эта тема не всплывает).

    Еще есть leJos, это просто Java-машина для контроллера. Пишем на Java, загружаем — вуаля.

  • Как распознавать манипуляции и быстро обезвреживать их
    0
    Мне кажется, что такая статья скорее для GeekTimes или мегамозга, чем для хабра.
  • Какие гаджеты используют в школах
    +1
    > позитивно сказывается на посещаемости детей, а впоследствии — и на их успеваемости.
    Серьёзно? Откуда такие выводы?
  • Краткий обзор первых 10 млн. символов числа Пи
    0
    Нормальность (то самое «встретится что угодно рано или поздно») числа пи — это сейчас открытая проблема.
  • Meteor. Разрабатываем TODO List
    0
    Windows поддерживает, но далеко не последнюю версию. Сейчас, кажется, доступна 0.9.0.1