Это прекрасно, если у человека такая возможность есть. Вопрос поста заключается в том, как я понимаю, что делать, если у человека есть особенность деятельности мозга. Состояние потока, по-видимому, недостижимо. Приходится предлагать какие-то "костыли"/протезы, позволяющие получать продукт имеющимися ментальными средствами.
Есть процесс думания, позволяющий получить некоторый интеллектуальный продукт. Этот процесс требует 23 минут. В случае отвлечения продукт рассыпается.
Есть объект, который может осуществлять процесс думания непрерывно в течение 5-7 минут, максимум — 15 минут (СДВГ?).
Спрашивается, каким образом объект может создать продукт?
Как мне кажется, задача в такой формулировке не имеет непосредственного решения, удовлетворяющего имеющимся ограничениям. Поэтому надо подойти творчески и немного расширить эти ограничения.
Желательно разбить процесс думания на части меньшей длительности. И при этом избежать рассыпания интеллектуального продукта.
Желательно увеличить длительность концентрации объекта.
Был такой фильм — 50 первых поцелуев. Там предлагалось решение для проблемы сброса суточной памяти — в начале каждого нового периода концентрации проигрывать промежуточные результаты предыдущего периода концентрации.
Для программиста можно предложить что-то аналогичное — систему конспектирования промежуточных результатов — TDD, скелеты классов, названия функций без реализации, формулирование текущих задач, текущего понимания способа решения (например, текстом описывать план действий будущей функции). Можно рисовать диаграммы, отражающие текущую модель интеллектуального продукта. Главное требование к такой системе конспектирования — универсальность, т.к. программистам приходится строить разные конструкты в голове. Возможно, текстовая форма — удобнее всего.
Второй путь — развитие способностей объекта и удлинение периодов концентрации внимания. Например, попробовать медитацию, попробовать читать художественную литературу многократно (чтобы исключить новизну), попробовать монотонную физическую активность — бег/ходьба/плавание...
Третий путь — осознать, что все люди разные, принять такую особенность, и переключиться на такой вид деятельности в IT, для которого такая особенность является преимуществом или не является критическим недостатком. Поддержка коммьюнити, тим-лидерство, тестирование,..
Эксплуатировать свой код должны инженеры
Если проект небольшой — то да, хорошая идея. Если же проект большой, то, к сожалению, это труднореализуемо. Для больших проектов люди придумали разделение труда. Поэтому-то есть product owner'ы, которые выступают теми-самыми-инженерами-которые-эксплутируют-и-хорошо-понимают-всё, и разработчики, QA, DevOps'ы, team lead'ы, PM-ы и т.п., которые по поручению product-owner'а выполняют различные работы. И коммуникации в больших командах можно настроить достаточно неплохо при должном старании.
Покупка почти всегда лучше создания
Пример противоположной ситуации. AWS продаёт сервис NAT gateway (что-то типа роутера). Аналогичный сервис можно реализовать на других сервисах и получится дешевле (в 10-100 раз). Единовременные затраты на разработку довольно быстро окупятся.
Упростите процесс деплоев
Двумя руками за. Как мне кажется, CI/CD как раз об этом. Должна быть одна кнопка, которая отправляет изменения в продакшн.
Доверяйте людям, которые ближе всего к практической работе
Можно и шире сформулировать — "доверяйте профессионалам" :) Если люди непосредственно работают с пользователями, им можно доверять по вопросам UI/UX. Но я бы не стал доверять им архитектуру обработки данных. В этом вопросе лучше доверять другим специалистам.
Меры QA снижают качество
Как мне кажется, здесь какая-то подмена терминов. QA — quality assurance — обеспечение качества. Так что получается оксюморон. Видимо, автор имеет в виду какое-то несовершенство процессов QA в его компании.
Ручному тестированию, конечно, нет места в цепочке CI/CD. Все необходимые тесты должны быть автоматизированы.
Идея "тестирования в продакшене" хорошо известна по соответствующему интернет-мему. Как мне кажется, не для всех проектов такая идея подходит. В случае, если product owner считает возможным пожертвовать частью пользователей, и сэкономить на других мерах QA, то это, наверное, его право. Ему, по-видимому, надо будет обосновать это решение перед заинтересованными лицами (stakeholder'ами).
Скучная технология — это отлично
Идти по проторённой дороге — это отличный способ снижения рисков. Если такая дорога есть — туда, вероятно, и надо идти большинству. Все грабли разложены в известных местах, остаётся только их аккуратно обходить.
Но, как говорится, кто не рискует, тот не пьёт шампанского. Если суть разработки как раз заключается в изменении этой проторённой дороги, поиске новых путей, то такой совет не очень подойдёт. Некоторые стартапы, изобретая свой велосипед, достигли впечатляющих результатов.
Простота всегда выигрывает
Ну, история знает и другие примеры. Например, автомобиль Жигули 2101, по-видимому, проще Tesla Model S. Но, как мне кажется, потребители склонны предпочесть что-то более сложное.
Или пример из области баз данных. DynamoDB — попроще чем Postgres. Там даже толком не поддерживается SQL. Но для многих задач архитекторы предпочитают RDBMS.
Видимо, есть какие-то преимущества в сложных решениях...
Среды вне продакшена имеют убывающие доходы
Здесь трудно даже понять, что имеется в виду.
Доход по определению приносит только конечный продукт. Это же не значит, что надо уволить отдел бэкенд, т.к. там самые высокие расходы?
staging/dev среды, несмотря на отличие от prod, позволяют
проводить отладку в условиях, приближенных к prod,
обнаруживать массу проблем без риска потери пользователей,
свободно экспериментировать с новыми фичами,
…
Если бы они не были нужны, никто бы их не делал.
По поводу трафика. (1) можно делать копию prod-базы на регулярной основе (с обфускацией, если это необходимо); (2) во многих случаях можно направлять копию входящих событий на параллельную систему (staging/dev) в какой-либо пропорции 0-100%. Так что вполне можно получить очень близкую к реальности картину.
Всё всегда ломается
С этим, пожалуй, соглашусь. Несмотря на то, что есть вещи, которые работают очень надёжно, мы всё-таки должны иметь планы и стратегии реакции на всевозможные отказы.
Действительно, можно найти обходной путь. Который, в свою очередь, увеличивает сложность, и на котором тоже сделаны ловушки неожиданных расходов.
Мне всё же кажется, что цена в $36/месяц (=$432/год) несколько неадекватна за такой, в общем-то, несложный сервис как NAT.
Ценовая политика местами выглядит грабительски.
Для справки, небольшой пример неожиданной стоимости.
Если вы хотите использовать VPC (то есть, изолировать свою инфраструктуру от внешнего интернета), и при этом, естественно, захотите получать информацию из внешнего мира, то окажется, что с большой вероятностью вам потребуется NAT. Что же здесь такого, спросит неискушённый читатель? Стоимость сервиса, предлагаемого AWS (NAT Gateway) (в среднем, по регионам отличается):
$0.05 в час
$0.05 за Гб трафика.
То есть, если вы собрали Hello World, в котором используется NAT Gateway, то за месяц, даже если приложение не используется, придётся заплатить $36.
Если захотите использовать нормальную базу данных (в терминологии AWS — RDS), то стоимость — $0,07 в час.
Бесплатный сыр, как известно, в мышеловке, и за Free Tier (уровень бесплатного использования) кто-то всё-таки должен заплатить...
Если я правильно понимаю (раздел "Что мы считаем"), то задача выглядит так:
выполнить вычисления ("расчётное ядро") длительностью 1.5мс 6 раз независимо друг от друга.
Для параллельного вычисления изначально и задействовали akka. Так?
Или есть какие-то другие веские причины, чтобы использовать akka?
Поводом для внедрения программы "Социальный мониторинг" послужила пандемия COVID-19.
Какими научными исследованиями, показывающими потенциальную эффективность этой меры, руководствовались люди, принимавшие решение об использовании этого приложения?
Какова ожидаемая эффективность этой меры и какова фактическая эффективность? Каковы негативные последствия (ожидаемые и фактические) от внедрения этой меры?
Приложение "Социальный мониторинг", по-видимому, предназначено для сбора информации для вынесения массовых штрафов москвичам. Для вынесения штрафов необходимо событие правонарушения и некоторые доказательства. Приложение СМ, насколько я понимаю, как раз и занимается сбором доказательств. Любопытно, какие это доказательства.
Геолокация, по-видимому, не является достаточным доказательством совершения административного правонарушения, т.к. телефон не является сертифицированным устройством, дающим какие-то гарантии в отношении этих данных. В частности, на основании этих данных нельзя достоверно прийти к выводу, что человек находился в каком-то месте, либо за пределами какой-то области.
Если пользователь не делает фотографию, то это является отсутствием данных, и не может использоваться в качестве доказательства, ввиду отсутствия оного. Рассуждения вида "раз нет фотографии, значит, был далеко" несостоятельны с логической точки зрения, т.к. из отсутствия фотографии нельзя сделать вывод о том, что человек был далеко.
В свете вышесказанного, вопросы:
Подскажите пожалуйста, какие именно данные (геолокация, отсутствие фотографии, ...) используются в качестве доказательств при вынесении решений о штрафах?
Каким образом автоматическое вынесение штрафов соотносится с презумпцией невиновности (ст.49 Конституции предусмотрено, что граждане не обязаны доказывать свою невиновность)?
Под линейной зависимостью обычно понимают t=k*n + b. В данном случае зависимость — нелинейная t=c*n^d, причём d < 1.
Здесь, на мой взгляд — две ошибки. Во-первых, в терминологии, чёрное называется белым (нелинейная зависимость — линейной), и, во-вторых, в фактуре, т.к. тем самым Вы утверждаете, что алгоритм имеет сложность O(n^0.781568), что, на мой взгляд, невозможно даже в той задаче, которую Вы решаете. По-видимому, при построении графика производился отбор данных. Например, отбрасывались тупиковые случаи, когда алгоритм был выполнен, но получен отрицательный ответ.
Коллеги не обидятся. Однако хотелось бы отметить, что, по-видимому, Вы используете демагогический приём — strawman.
Оба наших комментария относятся к корректному использованию терминологии. А именно, слово "детерминированный" имеет вполне определённый смысл, отличающийся от того, который Вы в него вкладываете.
В настоящем же комментарии Вы сообщаете, что Ваш алгоритм является недетерминированным. Это мы уже поняли, как только Вы написали, что используете генератор случайных чисел. Тем самым, вы подменяете тезис и спорите уже с другим тезисом.
Вообще же, Back tracking никоим образом не требует использования ГСЧ. Вы могли бы в упомянутых Вами случаях заменить вызовы ГСЧ на детерминированные алгоритмы перебора всех возможных продолжений. Тогда получился бы обычный детерминированный алгоритм.
Где здесь "время комплектации растет линейно, с увеличением значения n"?
Время работы алгоритма, если верить этой формуле, растёт медленнее, чем n. По-видимому, здесь какая-то ошибка, вы так не считаете? Возможно, на графике отражены не все значения?
Ваше понимание "строгих математических методов", на мой взгляд, узко. Обычные алгоритмы являются вполне себе строгими и математическими. Можно даже доказать, что алгоритм решает задачу. Например, алгоритм Евклида для поиска НОД. Или 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'а.
Ваше понимание "детерминированности" очевидно отличается от канонического. Backtracking — обычный элемент алгоритма, ничуть не хуже других. Использование Backtracking'а не добавляет неопределённости. Обычный алгоритм расстановки ферзей с backtracking'м — http://rosettacode.org/wiki/N-queens_problem вполне себе детерминированный. Всегда даёт одинаковый результат при одинаковых входных значениях.
Скорость выполнения алгоритма на конкретном компьютере
Зависит от целей статьи. Если Вы хотите продемонстрировать, что алгоритм имеет сложность O(n), то сведения о времени работы алгоритма на конкретном компьютере не сильно помогают. Обычно сложность можно оценить путём анализа кода алгоритма.
То, что каждый раз необходимо определить статус ячейки (он неопределенный, пока это не установим) делает недетерминированным решение задачи.
Насколько я понимаю, единственный источник недетерминированности — использование генератора случайных чисел. Во всём остальном алгоритм должен быть детерминированным, т.е. давать одинаковый результат при одинаковых входных значениях.
Ведь, даже для n=10 пришлось бы держать массив n=10, и каждый раз проводить диагональные исключения, чтобы по ходу знать статус каждой ячейки.
Как мне кажется, вы используете более подходящую структуру данных для хранения заполненности диагоналей — линейный массив, — так что нет необходимости хранить большой массив. По-видимому, этот аргумент не относится к вопросу детерминированности/недетерминированности.
False Negative решения… Это не связано с формулировкой задачи, это свойство алгоритма ошибаться.
По-моему, это как раз и говорит о том, что предложенный алгоритм исходную задачу не решает. Разве нет?
я не знаю детерминированных алгоритмов решения NP-полных задач
Что Вы имеете в виду? В свете https://ru.wikipedia.org/wiki/NP-полная_задача, насколько я понимаю, для всех NP-полных задач существуют детерминированные алгоритмы решения. Другое дело, что они могут быть непрактичны для больших n.
Может и так. Просто тот алгоритм, который Вы предлагаете, не решает поставленную задачу. Заголовок сформулирован "n-Queens Completion Problem — линейный алгоритм решения", то есть предполагается, что алгоритм, который Вы предлагаете в статье, даёт решение задачи "n-Queens Completion Problem". Если бы это было так, то это была бы революция.
Как оказалось, исходная задача заменена на другую, и поэтому революции не случилось.
С помощью строгих математических методов, задачу n-Queens Completion и другие задачи подобного рода решить невозможно
Не то, чтобы совсем невозможно. Невозможно за полиномиальное время. В чём, собственно и состоит проблема NP-полных задач. А решить при любых конкретных значениях параметров — возможно. За какое-то длительное время. Например, прямым перебором или обычным backtracking'ом.
Если согласитесь с тем, что на основе строгого математического подхода решение задач из множества NP-Complete не будет успешным, то тогда у Вас появится уверенность в том, что такие задачи будут решены на основе алгоритмической математики
Как я понимаю, NP-полные задачи, в силу их специфики, люди решают с помощью перебора с некоторыми эвристиками. Например, задача SAT, несмотря на свою NP-полноту, достаточно успешно решается на практике. Поэтому предлагаемый Вами алгоритм, вероятно, следует отнести к тому же классу.
Строгий математический подход необходим в любом случае. Если мы явно объявим, что решаем другую задачу, тогда можно спокойно применять математический аппарат и приходить к верным результатам.
Выглядит как отличная бизнес-возможность… UpWork добровольно уходит с рынка и даёт возможность всем остальным игрокам занять освободившуюся нишу.
Действительно, опечатался. Спасибо за замечание. (К сожалению, в комментарии уже исправить не получается.)
Деление можно представить как умножение на обратный элемент.
Обратный элемент:
домножим числитель и знаменатель на
a - b \sqrt 5. Получим в знаменателеa^2 - 5b.Т.е. остаёмся в группе.
Люди деляться на две группы — кого эта фраза бесит и кто ничего не замечает.
Это прекрасно, если у человека такая возможность есть. Вопрос поста заключается в том, как я понимаю, что делать, если у человека есть особенность деятельности мозга. Состояние потока, по-видимому, недостижимо. Приходится предлагать какие-то "костыли"/протезы, позволяющие получать продукт имеющимися ментальными средствами.
Задача сформулирована математически:
Как мне кажется, задача в такой формулировке не имеет непосредственного решения, удовлетворяющего имеющимся ограничениям. Поэтому надо подойти творчески и немного расширить эти ограничения.
Был такой фильм — 50 первых поцелуев. Там предлагалось решение для проблемы сброса суточной памяти — в начале каждого нового периода концентрации проигрывать промежуточные результаты предыдущего периода концентрации.
Для программиста можно предложить что-то аналогичное — систему конспектирования промежуточных результатов — TDD, скелеты классов, названия функций без реализации, формулирование текущих задач, текущего понимания способа решения (например, текстом описывать план действий будущей функции). Можно рисовать диаграммы, отражающие текущую модель интеллектуального продукта. Главное требование к такой системе конспектирования — универсальность, т.к. программистам приходится строить разные конструкты в голове. Возможно, текстовая форма — удобнее всего.
Второй путь — развитие способностей объекта и удлинение периодов концентрации внимания. Например, попробовать медитацию, попробовать читать художественную литературу многократно (чтобы исключить новизну), попробовать монотонную физическую активность — бег/ходьба/плавание...
Третий путь — осознать, что все люди разные, принять такую особенность, и переключиться на такой вид деятельности в IT, для которого такая особенность является преимуществом или не является критическим недостатком. Поддержка коммьюнити, тим-лидерство, тестирование,..
Разбор (немного предвзятый) этого же инцидента со стороны:
https://cloudirregular.substack.com/p/the-cold-reality-of-the-kinesis-incident
Довольно спорные утверждения, как мне кажется.
Эксплуатировать свой код должны инженеры
Если проект небольшой — то да, хорошая идея. Если же проект большой, то, к сожалению, это труднореализуемо. Для больших проектов люди придумали разделение труда. Поэтому-то есть product owner'ы, которые выступают теми-самыми-инженерами-которые-эксплутируют-и-хорошо-понимают-всё, и разработчики, QA, DevOps'ы, team lead'ы, PM-ы и т.п., которые по поручению product-owner'а выполняют различные работы. И коммуникации в больших командах можно настроить достаточно неплохо при должном старании.
Покупка почти всегда лучше создания
Пример противоположной ситуации. AWS продаёт сервис NAT gateway (что-то типа роутера). Аналогичный сервис можно реализовать на других сервисах и получится дешевле (в 10-100 раз). Единовременные затраты на разработку довольно быстро окупятся.
Упростите процесс деплоев
Двумя руками за. Как мне кажется, CI/CD как раз об этом. Должна быть одна кнопка, которая отправляет изменения в продакшн.
Доверяйте людям, которые ближе всего к практической работе
Можно и шире сформулировать — "доверяйте профессионалам" :) Если люди непосредственно работают с пользователями, им можно доверять по вопросам UI/UX. Но я бы не стал доверять им архитектуру обработки данных. В этом вопросе лучше доверять другим специалистам.
Меры QA снижают качество
Как мне кажется, здесь какая-то подмена терминов. QA — quality assurance — обеспечение качества. Так что получается оксюморон. Видимо, автор имеет в виду какое-то несовершенство процессов QA в его компании.
Ручному тестированию, конечно, нет места в цепочке CI/CD. Все необходимые тесты должны быть автоматизированы.
Идея "тестирования в продакшене" хорошо известна по соответствующему интернет-мему. Как мне кажется, не для всех проектов такая идея подходит. В случае, если product owner считает возможным пожертвовать частью пользователей, и сэкономить на других мерах QA, то это, наверное, его право. Ему, по-видимому, надо будет обосновать это решение перед заинтересованными лицами (stakeholder'ами).
Скучная технология — это отлично
Идти по проторённой дороге — это отличный способ снижения рисков. Если такая дорога есть — туда, вероятно, и надо идти большинству. Все грабли разложены в известных местах, остаётся только их аккуратно обходить.
Но, как говорится, кто не рискует, тот не пьёт шампанского. Если суть разработки как раз заключается в изменении этой проторённой дороги, поиске новых путей, то такой совет не очень подойдёт. Некоторые стартапы, изобретая свой велосипед, достигли впечатляющих результатов.
Простота всегда выигрывает
Ну, история знает и другие примеры. Например, автомобиль Жигули 2101, по-видимому, проще Tesla Model S. Но, как мне кажется, потребители склонны предпочесть что-то более сложное.
Или пример из области баз данных. DynamoDB — попроще чем Postgres. Там даже толком не поддерживается SQL. Но для многих задач архитекторы предпочитают RDBMS.
Видимо, есть какие-то преимущества в сложных решениях...
Среды вне продакшена имеют убывающие доходы
Здесь трудно даже понять, что имеется в виду.
Доход по определению приносит только конечный продукт. Это же не значит, что надо уволить отдел бэкенд, т.к. там самые высокие расходы?
staging/dev среды, несмотря на отличие от prod, позволяют
Если бы они не были нужны, никто бы их не делал.
По поводу трафика. (1) можно делать копию prod-базы на регулярной основе (с обфускацией, если это необходимо); (2) во многих случаях можно направлять копию входящих событий на параллельную систему (staging/dev) в какой-либо пропорции 0-100%. Так что вполне можно получить очень близкую к реальности картину.
Всё всегда ломается
С этим, пожалуй, соглашусь. Несмотря на то, что есть вещи, которые работают очень надёжно, мы всё-таки должны иметь планы и стратегии реакции на всевозможные отказы.
Действительно, можно найти обходной путь. Который, в свою очередь, увеличивает сложность, и на котором тоже сделаны ловушки неожиданных расходов.
Мне всё же кажется, что цена в $36/месяц (=$432/год) несколько неадекватна за такой, в общем-то, несложный сервис как NAT.
Ценовая политика местами выглядит грабительски.
Для справки, небольшой пример неожиданной стоимости.
Если вы хотите использовать VPC (то есть, изолировать свою инфраструктуру от внешнего интернета), и при этом, естественно, захотите получать информацию из внешнего мира, то окажется, что с большой вероятностью вам потребуется NAT. Что же здесь такого, спросит неискушённый читатель? Стоимость сервиса, предлагаемого AWS (NAT Gateway) (в среднем, по регионам отличается):
То есть, если вы собрали Hello World, в котором используется NAT Gateway, то за месяц, даже если приложение не используется, придётся заплатить $36.
Если захотите использовать нормальную базу данных (в терминологии AWS — RDS), то стоимость — $0,07 в час.
Бесплатный сыр, как известно, в мышеловке, и за Free Tier (уровень бесплатного использования) кто-то всё-таки должен заплатить...
Если я правильно понимаю (раздел "Что мы считаем"), то задача выглядит так:
выполнить вычисления ("расчётное ядро") длительностью 1.5мс 6 раз независимо друг от друга.
Для параллельного вычисления изначально и задействовали akka. Так?
Или есть какие-то другие веские причины, чтобы использовать akka?
Пробовали ForkJoinPool использовать?
Поводом для внедрения программы "Социальный мониторинг" послужила пандемия COVID-19.
Какими научными исследованиями, показывающими потенциальную эффективность этой меры, руководствовались люди, принимавшие решение об использовании этого приложения?
Какова ожидаемая эффективность этой меры и какова фактическая эффективность? Каковы негативные последствия (ожидаемые и фактические) от внедрения этой меры?
Приложение "Социальный мониторинг", по-видимому, предназначено для сбора информации для вынесения массовых штрафов москвичам. Для вынесения штрафов необходимо событие правонарушения и некоторые доказательства. Приложение СМ, насколько я понимаю, как раз и занимается сбором доказательств. Любопытно, какие это доказательства.
В свете вышесказанного, вопросы:
геолокация,отсутствие фотографии, ...) используются в качестве доказательств при вынесении решений о штрафах?Под линейной зависимостью обычно понимают
t=k*n + b. В данном случае зависимость — нелинейнаяt=c*n^d, причёмd < 1.Здесь, на мой взгляд — две ошибки. Во-первых, в терминологии, чёрное называется белым (нелинейная зависимость — линейной), и, во-вторых, в фактуре, т.к. тем самым Вы утверждаете, что алгоритм имеет сложность
O(n^0.781568), что, на мой взгляд, невозможно даже в той задаче, которую Вы решаете. По-видимому, при построении графика производился отбор данных. Например, отбрасывались тупиковые случаи, когда алгоритм был выполнен, но получен отрицательный ответ.Коллеги не обидятся. Однако хотелось бы отметить, что, по-видимому, Вы используете демагогический приём — strawman.
Оба наших комментария относятся к корректному использованию терминологии. А именно, слово "детерминированный" имеет вполне определённый смысл, отличающийся от того, который Вы в него вкладываете.
В настоящем же комментарии Вы сообщаете, что Ваш алгоритм является недетерминированным. Это мы уже поняли, как только Вы написали, что используете генератор случайных чисел. Тем самым, вы подменяете тезис и спорите уже с другим тезисом.
Вообще же, Back tracking никоим образом не требует использования ГСЧ. Вы могли бы в упомянутых Вами случаях заменить вызовы ГСЧ на детерминированные алгоритмы перебора всех возможных продолжений. Тогда получился бы обычный детерминированный алгоритм.
К рис.7.
имеется комментарий
Если я правильно понимаю Ваше уравнение, его можно немного преобразовать:
Ваше понимание "строгих математических методов", на мой взгляд, узко. Обычные алгоритмы являются вполне себе строгими и математическими. Можно даже доказать, что алгоритм решает задачу. Например, алгоритм Евклида для поиска НОД. Или http://toccata.lri.fr/gallery/why3.en.html — целый ряд алгоритмов, доказанных математически.
Боюсь, не могу с Вами согласиться. Back tracking — это лишь один из способов обхода решений. Простейший перебор всех вариантов:
С проверкой каждого варианта (
O(n)) сложность получаетсяO(n^n*n^2)— экспоненциальная. Такой алгоритм, очевидно, не содержит backtracking'а.Ваше понимание "детерминированности" очевидно отличается от канонического. Backtracking — обычный элемент алгоритма, ничуть не хуже других. Использование Backtracking'а не добавляет неопределённости. Обычный алгоритм расстановки ферзей с backtracking'м — http://rosettacode.org/wiki/N-queens_problem вполне себе детерминированный. Всегда даёт одинаковый результат при одинаковых входных значениях.
Зависит от целей статьи. Если Вы хотите продемонстрировать, что алгоритм имеет сложность
O(n), то сведения о времени работы алгоритма на конкретном компьютере не сильно помогают. Обычно сложность можно оценить путём анализа кода алгоритма.Насколько я понимаю, единственный источник недетерминированности — использование генератора случайных чисел. Во всём остальном алгоритм должен быть детерминированным, т.е. давать одинаковый результат при одинаковых входных значениях.
Как мне кажется, вы используете более подходящую структуру данных для хранения заполненности диагоналей — линейный массив, — так что нет необходимости хранить большой массив. По-видимому, этот аргумент не относится к вопросу детерминированности/недетерминированности.
По-моему, это как раз и говорит о том, что предложенный алгоритм исходную задачу не решает. Разве нет?
Что Вы имеете в виду? В свете https://ru.wikipedia.org/wiki/NP-полная_задача, насколько я понимаю, для всех NP-полных задач существуют детерминированные алгоритмы решения. Другое дело, что они могут быть непрактичны для больших n.
т.е.
O(n).Может и так. Просто тот алгоритм, который Вы предлагаете, не решает поставленную задачу. Заголовок сформулирован "n-Queens Completion Problem — линейный алгоритм решения", то есть предполагается, что алгоритм, который Вы предлагаете в статье, даёт решение задачи "n-Queens Completion Problem". Если бы это было так, то это была бы революция.
Как оказалось, исходная задача заменена на другую, и поэтому революции не случилось.
Не то, чтобы совсем невозможно. Невозможно за полиномиальное время. В чём, собственно и состоит проблема NP-полных задач. А решить при любых конкретных значениях параметров — возможно. За какое-то длительное время. Например, прямым перебором или обычным backtracking'ом.
Как я понимаю, NP-полные задачи, в силу их специфики, люди решают с помощью перебора с некоторыми эвристиками. Например, задача SAT, несмотря на свою NP-полноту, достаточно успешно решается на практике. Поэтому предлагаемый Вами алгоритм, вероятно, следует отнести к тому же классу.
Строгий математический подход необходим в любом случае. Если мы явно объявим, что решаем другую задачу, тогда можно спокойно применять математический аппарат и приходить к верным результатам.