• Спросите нас: ДИТ ответит на вопросы
    +3

    Поводом для внедрения программы "Социальный мониторинг" послужила пандемия COVID-19.
    Какими научными исследованиями, показывающими потенциальную эффективность этой меры, руководствовались люди, принимавшие решение об использовании этого приложения?
    Какова ожидаемая эффективность этой меры и какова фактическая эффективность? Каковы негативные последствия (ожидаемые и фактические) от внедрения этой меры?

  • Спросите нас: ДИТ ответит на вопросы
    +11

    Приложение "Социальный мониторинг", по-видимому, предназначено для сбора информации для вынесения массовых штрафов москвичам. Для вынесения штрафов необходимо событие правонарушения и некоторые доказательства. Приложение СМ, насколько я понимаю, как раз и занимается сбором доказательств. Любопытно, какие это доказательства.


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

    В свете вышесказанного, вопросы:


    1. Подскажите пожалуйста, какие именно данные (геолокация, отсутствие фотографии, ...) используются в качестве доказательств при вынесении решений о штрафах?
    2. Каким образом автоматическое вынесение штрафов соотносится с презумпцией невиновности (ст.49 Конституции предусмотрено, что граждане не обязаны доказывать свою невиновность)?
  • n-Queens Completion Problem — линейный алгоритм решения
    0

    Под линейной зависимостью обычно понимают t=k*n + b. В данном случае зависимость — нелинейная t=c*n^d, причём d < 1.
    Здесь, на мой взгляд — две ошибки. Во-первых, в терминологии, чёрное называется белым (нелинейная зависимость — линейной), и, во-вторых, в фактуре, т.к. тем самым Вы утверждаете, что алгоритм имеет сложность O(n^0.781568), что, на мой взгляд, невозможно даже в той задаче, которую Вы решаете. По-видимому, при построении графика производился отбор данных. Например, отбрасывались тупиковые случаи, когда алгоритм был выполнен, но получен отрицательный ответ.

  • n-Queens Completion Problem — линейный алгоритм решения
    0
    1. Коллеги не обидятся. Однако хотелось бы отметить, что, по-видимому, Вы используете демагогический приём — strawman.
      Оба наших комментария относятся к корректному использованию терминологии. А именно, слово "детерминированный" имеет вполне определённый смысл, отличающийся от того, который Вы в него вкладываете.
      В настоящем же комментарии Вы сообщаете, что Ваш алгоритм является недетерминированным. Это мы уже поняли, как только Вы написали, что используете генератор случайных чисел. Тем самым, вы подменяете тезис и спорите уже с другим тезисом.


    2. Вообще же, Back tracking никоим образом не требует использования ГСЧ. Вы могли бы в упомянутых Вами случаях заменить вызовы ГСЧ на детерминированные алгоритмы перебора всех возможных продолжений. Тогда получился бы обычный детерминированный алгоритм.


  • n-Queens Completion Problem — линейный алгоритм решения
    0

    К рис.7.


    log(1000*t) = — 0.628927 + 0.781568*log(n)

    имеется комментарий


    Видно, что время комплектации растет линейно, с увеличением значения n.

    Если я правильно понимаю Ваше уравнение, его можно немного преобразовать:


    3 + log(t) = — 0.628927 + 0.781568*log(n)
    log(t) = — 3.628927 + 0.781568*log(n)
    log(t) = — 3.628927 + log(n^0.781568)
    log(t) = log(n^0.781568*10^(-3.628927))
    t = n^0.781568*10^(-3.628927)

    1. Где здесь "время комплектации растет линейно, с увеличением значения n"?
    2. Время работы алгоритма, если верить этой формуле, растёт медленнее, чем n. По-видимому, здесь какая-то ошибка, вы так не считаете? Возможно, на графике отражены не все значения?
  • n-Queens Completion Problem — линейный алгоритм решения
    +1

    Ваше понимание "строгих математических методов", на мой взгляд, узко. Обычные алгоритмы являются вполне себе строгими и математическими. Можно даже доказать, что алгоритм решает задачу. Например, алгоритм Евклида для поиска НОД. Или http://toccata.lri.fr/gallery/why3.en.html — целый ряд алгоритмов, доказанных математически.


    Back Tracking является неотъемлемым компонентом прямого перебора

    Боюсь, не могу с Вами согласиться. Back tracking — это лишь один из способов обхода решений. Простейший перебор всех вариантов:


    for k = 0..n^n-1
      for i = 0..n-1
        q[i] = k / n^i % n

    С проверкой каждого варианта (O(n)) сложность получается O(n^n*n^2) — экспоненциальная. Такой алгоритм, очевидно, не содержит backtracking'а.

  • n-Queens Completion Problem — линейный алгоритм решения
    +1

    Ваше понимание "детерминированности" очевидно отличается от канонического. Backtracking — обычный элемент алгоритма, ничуть не хуже других. Использование Backtracking'а не добавляет неопределённости. Обычный алгоритм расстановки ферзей с backtracking'м — http://rosettacode.org/wiki/N-queens_problem вполне себе детерминированный. Всегда даёт одинаковый результат при одинаковых входных значениях.

  • n-Queens Completion Problem — линейный алгоритм решения
    0
    Скорость выполнения алгоритма на конкретном компьютере

    Зависит от целей статьи. Если Вы хотите продемонстрировать, что алгоритм имеет сложность O(n), то сведения о времени работы алгоритма на конкретном компьютере не сильно помогают. Обычно сложность можно оценить путём анализа кода алгоритма.


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

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


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

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


    False Negative решения… Это не связано с формулировкой задачи, это свойство алгоритма ошибаться.

    По-моему, это как раз и говорит о том, что предложенный алгоритм исходную задачу не решает. Разве нет?


    я не знаю детерминированных алгоритмов решения NP-полных задач

    Что Вы имеете в виду? В свете https://ru.wikipedia.org/wiki/NP-полная_задача, насколько я понимаю, для всех NP-полных задач существуют детерминированные алгоритмы решения. Другое дело, что они могут быть непрактичны для больших n.

  • n-Queens Completion Problem — линейный алгоритм решения
    +4
    временная сложность алгоритма линейная

    т.е. O(n).


    Может и так. Просто тот алгоритм, который Вы предлагаете, не решает поставленную задачу. Заголовок сформулирован "n-Queens Completion Problem — линейный алгоритм решения", то есть предполагается, что алгоритм, который Вы предлагаете в статье, даёт решение задачи "n-Queens Completion Problem". Если бы это было так, то это была бы революция.
    Как оказалось, исходная задача заменена на другую, и поэтому революции не случилось.


    С помощью строгих математических методов, задачу n-Queens Completion и другие задачи подобного рода решить невозможно

    Не то, чтобы совсем невозможно. Невозможно за полиномиальное время. В чём, собственно и состоит проблема NP-полных задач. А решить при любых конкретных значениях параметров — возможно. За какое-то длительное время. Например, прямым перебором или обычным backtracking'ом.


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

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


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

  • n-Queens Completion Problem — линейный алгоритм решения
    +11

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


    Немного критики


    desktop-13

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


    Очевидно, что данный алгоритм по времени счета является линейным относительно n.

    Краеугольным камнем P≠NP является оценка сложности. Хотелось бы, конечно же, видеть алгоритм на каком-нибудь псевдо-коде, и видеть оценку в стандартной О-нотации.


    n-Queens Completion problem является классической не детерминированной задачей.

    это утверждение противоречит формулировке задачи, данной в разделе "1. Введение". Там задача сформулирована детерминировано, как и положено задачам класса NP.
    Таким образом, автор подменяет одну задачу другой.


    False Negative решения

    В детерминированном алгоритме решения NP-полных задач таких решений быть не может. Таким образом, предложенное автором решение не является решением задачи n-Queens Completion problem

  • 9 советов по использованию библиотеки Cats в Scala
    +1

    Разные цели/задачи — разные языки.


    Бизнес-логику вполне можно писать на Scala с помощью подходящего DSL. В том числе, и не столь прямолинейную.
    "Премудрости" дают инструменты для хороших библиотек и DSL. На прикладном уровне хорошие библиотеки использовать достаточно легко, и можно в большинстве случаев обходиться поверхностными знаниями, не вникая в детали.
    Для некоторых задач отсутствие адекватных по сложности инструментов приводит к тому, что программы получаются не очень хорошими (многословными, с повторами похожего кода, с необходимостью заново тестировать похожую функциональность).

  • 9 советов по использованию библиотеки Cats в Scala
    +1

    Есть хорошие книги и курсы, с помощью которых можно освоить абстракции, используемые в функциональном программировании. Например, FP in Scala (либо аналогичная книжка на Haskell'e — haskellbook.com). На coursera есть специализация "Functional Programming in Scala".


    Ну а собственно lift из обычной функции делает функцию, работающую с какой-то структурой. Например,


    val inc: Int => Int = _ + 1
    val linc: List[Int] => List[Int] = Functor[List].lift(inc)
    
    val List(11,12,13) = linc(List(10,11,12))

    а универсальность позволяет писать код, который не зависит от конкретной структуры:


    def algorithm[F[_]: Functor, A: Numeric](fa: F[A]): F[A] = {
      val N = Numeric[A]
      val F = Functor[F]
      val inc = N.plus(_, N.one)
      val finc = F.lift(inc)
      finc(fa)
    }

    такой алгоритм будет работать с любыми структурами данных (для которых есть Functor) и любыми числовыми типами (для которых есть Numeric).

  • 9 советов по использованию библиотеки Cats в Scala
    0

    COBOL не работает на таком уровне абстракций. lift — мощный универсальный инструмент, который затруднительно даже представить в слабо-абстрактных языках.

  • 9 советов по использованию библиотеки Cats в Scala
    +1

    То же самое на Haskell:


    lift :: (A -> B) -> F A -> F B
    lift f = flip map f

    не то, чтобы стало сильно легче...


    Видимая сложность функции lift связана с её универсальностью. При использовании, вообще говоря, всё довольно удобно и не выглядит сложным:


    val inc: Int => Int = _ + 1
    val oinc: Option[Int] => Option[Int] = Option.lift(inc)
    
    val Option(11) = oinc(10.some)
  • Компилируемая конфигурация распределённой системы
    0
    1. По поводу разрешения IP — есть в статье. Удобный вариант — прописать новый IP в /etc/hosts для предопределённого имени.
      По поводу паролей — (1) разбить конфигурацию на 2 части — общая и секретная; (2) предусмотреть макрос или скрипт сборки, который будет забирать пароли из хранилища и запекать в конфигурацию; (3) по-старинке, предусмотреть runtime-загрузку паролей при старте приложения.
    2. jar-конфигурации будет зависеть от корректных версий составных частей приложения. То есть, всё приложение можно "вытянуть" за один jar-файл. Совместимость проверяется на этапе сборки — после успешной компиляции можно запустить интеграционные тесты.
    3. Отдельный jar для конфигурации будет, вероятно, не очень-то повторно используем. Сам микросервис, без конкретной конфигурации, — вполне себе повторно-используемый компонент. А конфигурация обычно — небольшой файлик. Просто компилируется отдельно.
  • SNA Hackathon 2019
    0

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

  • Списки в Kotlin. Haskell подход
    +1

    Как мне кажется, статья не отражает "Haskell подход". В Haskell — простая структура данных (cons-list) + рекурсия позволяют эффективно решать перечисленные задачи. Предлагаемые в статье алгоритмы выглядят неэффективно.


    Например, size использует метод tail типа List, что, в случае array-list'а будет копировать почти весь лист (O(N) по времени и по памяти), а затем не использует хвостовую рекурсию (O(N) по памяти), чтобы прибавить 1. Тем самым общая вычислительная сложность оказывается O(N^2), что отличается от обычной сложности O(N) по времени и O(1) по памяти.


    В примере с хвостовой рекурсией автор также использует when(xs.size) внутри функции. В случае, если List — односвязный список, опять окажется, что каждый вызов O(N). В итоге хвостовая рекурсия не спасает, получаем O(N^2). (Можно было бы использовать when(xs.isEmpty) с O(1).)

  • Maven. Собираем только измененное
    0

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

  • Tessel – микроконтроллер, программируемый на JavaScript
    0

    Вроде, теперь у espruino лицензия Mozilla MPLv2 и Creative Commons

  • Про ScalaCheck
    +1

    Насколько я понимаю, в ScalaCheck ключевым является понятие "свойства". А генераторы используются постольку поскольку, как средство, позволяющее убедиться, что свойство выполняется в широком диапазоне значений.
    ScalaCheck не подходит для замены Unit-тестов во всех случаях. Этот подход прекрасно работает тогда, когда удаётся найти те самые свойства, справедливые для многих случаев. Если программа представляет собой много отдельных несвязанных случаев — switch/case/if, то маловероятно, что такие обобщённые свойства будет легко обнаружить. А вот если тестируется универсальный алгоритм, то мы можем ожидать определённой стабильности его результатов.
    Если термин "свойство-ориентированное тестирование" не нравится, то можно поискать альтернативы для слова "свойство". Например, "инвариант" — тестирование на основе инвариантов. Или "предикат" — тестирование на основе валидации предикатов. Или "ограничение" — проверка ограничений, тестирование ограничений.

  • Классы типов в Scala (с небольшим обзором библиотеки cats)
    0

    Насколько я понимаю, в данном случае функтор, который конструируется из монады — единственный. Морфизм f: A=>B конвертируется в M[A] => M[B] путём использования двух операций, предоставляемых монадой. Вначале функцию f превращаем в вычисление, применяя нулевое вычисление η к результату функции: φ = λa.ηfa, а затем конструируем результирующую функцию в lifted-категории с использованием моноидного умножения μ: λma.μma φ.
    В Scala это выглядит, как привычный способ выразить map через flatMap и pure:


    def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
    def pure[A](x: A): F[A]
    def map[A, B](fa: F[A])(f: A => B): F[B] = flatMap(fa)(a => pure(f(a)))

    Эндофункторов, над которыми строится моноид, действительно много, но ни один из них, насколько я могу судить, не имеет такой формы, как этот — (A=>B) => (M[A] => M[B]).

  • Классы типов в Scala (с небольшим обзором библиотеки cats)
    0

    Я рассматриваю монаду с точки зрения программирования. В статье Monads for functional programming (Philip Wadler) монада определяется как тройка, состоящая из конструктора типа, отображения, превращающего обычное значение в этот тип ("нулевое" вычисление), и отображения, связывающего два вычисления в одно.
    То, что монада также является функтором, следует из того, что монада (как и функтор) позволяет преобразовать простые функции над базовыми типами в lifted-функции над сконструированным типом, то есть позволяет выполнить отображение категории обычных функции в категорию lifted-функций.
    Несмотря на это, монада — более универсальная конструкция, чем функтор. Монада не только отображает обычные функции в lifted, но и предоставляет дополнительные возможности работы с функциями типа A => M[B], которые включают конструируемый тип — "вычислениями". При этом, сам конструируемый тип M[B] оказывается включен в класс объектов категории (поэтому, по-видимому, категория эндофункторов; при этом конструктор типа M[?] не включен в объекты категории). И вместо двух изолированных категорий, связанных функтором, мы оперируем одной категорией, в структуре которой выделены функции особого вида — вычисления, — и объекты — M[B], инкапсулирующие (потенциальный) результат вычисления. Для этих функций/вычислений монада предоставляет базовый набор действий, соответствующий моноиду, — нулевое действие (без вычислений), и комбинирование двух вычислений.

  • Классы типов в Scala (с небольшим обзором библиотеки cats)
    0

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


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

  • Классы типов в Scala (с небольшим обзором библиотеки cats)
    0

    Похоже на то. В cats:


    trait Monad[F[_]] extends Applicative[F]
    trait Applicative[F[_]] extends Apply[F]
    trait Apply[F[_]] extends Functor[F]

    В scalaz похожая ситуация.

  • Строго типизированное представление неполных данных
    +1
    Добрый день.
    Конечно, можно. Лицензия — BSD-like.
    Мы сейчас этот подход используем и развиваем. В целом — достаточно удобно. При наличии неполных данных в БД (nullable колонок) — очень удобно.
  • Строго типизированные комбинаторы для построения парсера и синтезатора естественного языка
    +1
    Нельзя сказать, что этот подход прямо-таки сильно лучше, чем томита-парсер. Я думаю, что для своих целей томита-парсер вполне подходит. Однако есть несколько отличий, которые могут сделать предлагаемый подход предпочтительнее в некоторых прикладных задачах:
    1. Порождающая и разбирающая грамматики описываются общими средствами. В частности, для числительных обе грамматики записываются в единственном экземпляре. Это упрощает разработку и поддержку, т.к. надо писать вдвое меньше грамматических правил. Например, для модульного тестировани можно проводить преобразование вначале в одну сторону, а затем в другую и сравнивать результаты.
    2. Встроенность в язык программирования: (1) использование родных структур данных языка, (2) проверка типов на этапе компиляции, (3) доступность средств языка для любых целей, например, (а) можно написать свой конвертер в любой точке, (б) можно алгоритмически порождать грамматические выражения, (в) можно использовать средства модуляризации, встроенные в язык — trait'ы, (г) можно использовать удобный DSL для представления словарей.
    3. Из исходной грамматики можно получить грамматику для произвольного парсера, обладающего требуемыми свойствами. (По-видимому, можно сгенерировать грамматику и для томита-парсера.)
    4. Концепция уровня абстракции, лежащая в основе грамматических выражений. Преобразование между уровнями абстракции производится алгоритмически, что позволяет при разборе получать полное значение всей фразы в виде программных объектов, готовых к дальнейшей обработке, а при синтезе начинать генерацию непосредственно от семантических объектов, используемых в программе.
    5. Разделение правил формальной грамматики и правил выбора формы слова. Правила двух видов имеют несколько различную природу, поэтому и представлять в программе их удобно разными способами.
  • Конструирование типов в Scala
    0
    P.S. Вышеприведённый вариант — для общего случая, для Int, Double, BigNumber… и других T, для которых есть Numeric[T]. Если delta имеет известный тип, то можно и проще:
      case class SlotDelta[S <: SlotId[Int]](slotId:S, delta: Int) {
        def +:(oldValue:SlotValue[Int, S]) =
          SlotValue(slotId, oldValue.value+ delta)
      }
    

  • Конструирование типов в Scala
    +1
    1. UnionType (by Miles Sabin) используется для того, чтобы сформировать объединённый тип всех свойств, которые уже использовались в текущем объекте

      type SlotsUnion = head.type with tail.SlotsUnion
    

    (Здесь мы используем оператор with, который соответствует конъюнкции. Для проверки принадлежности мы инвертируем условие с помощью оператора <:<

    def get[SlotType<:SlotId[_](slotId:SlotType)(implicit ev: SlotSeq1#SlotUnion <:< SlotType) = ???
    


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

    3. Пример с delta. Пусть класс Person содержит 100 полей. И пусть среди этих полей есть свойство типа T: Numeric (например, Int, Double и т.п.). Тогда мы можем объявить специальный класс PropertyDelta, который несёт изменение этого свойства

      case class SlotDelta[T:Numeric, S <: SlotId[T]](slotId:S, delta:T)
    


    Это может быть экономнее, чем копировать оставшиеся 99 полей (при сохранении в БД, при передаче по сети и т.п.). Кроме того, здесь мы явно видим, что именно изменилось, можем проверить допустимость изменения этого свойства согласно каким-либо правилам.

    Теперь мы можем этот объект использовать для того, чтобы увеличить значение свойства на указанную величину:

      case class SlotDelta[T:Numeric, S <: SlotId[T]](slotId:S, delta: T) {
        def addTo(oldValue:SlotValue[T, S]) =
          SlotValue(slotId, implicitly[Numeric[T]].plus(oldValue.value, delta))
      }
    


    Или немного поинтереснее:

      implicit class SlotValueEx[T:Numeric, S <: SlotId[T]] (slotValue:SlotValue[T, S]) {
        def +(delta:T) =
          SlotValue(slotValue.slotId, implicitly[Numeric[T]].plus(slotValue.value, delta))
      }
    

  • Конструирование типов в Scala
    0
    Здесь мы сохраняем возможность рефакторинга. Все свойства представлены объектами, хранятся в именованных константах (val'ах). С точки зрения объявления «класса» получается не сильно больше, чем объявление обычного case class'а.
    case class Person(
        name: String, 
        address: Address
    )
    

    vs.
    object Person{
        val name = slot[String]("name")
        val address = slot[Address]("address")
    }
    

  • Обработка событий в реальном масштабе времени с помощью SynapseGrid
    0
    Это я немного погорячился. Граф допускает циклы без проблем. Исправил по тексту.