Если бы вы могли переименовать динамическое программирование ...
Если бы вы могли переименовать динамическое программирование, как бы вы это
43
вопросы об определениях, терминах и общеупотребительных именах в теоретической информатике.
Если бы вы могли переименовать динамическое программирование, как бы вы это
Спросите даже кого-то, имеющего опыт работы в области компьютерных наук, что такое регулярное выражение, и ответ, вероятно, выйдет за пределы возможности быть в пределах досягаемости конечного автомата. Например, «регулярное выражение» /^1?$|^(11+?)\1+$/ созданная известной личностью Perl Абигейл...
В паре недавних вопросов ( q1, q2 ) обсуждалась «Теория А» и «Теория В», по-видимому, чтобы уловить разрыв между изучением логики и языков программирования и изучением алгоритмов и сложности. Эта терминология была для меня новой, и при быстром поиске в Интернете не было никаких явных ссылок,...
Кто-нибудь осмелится попытаться выяснить, какова связь между этими областями обучения или, возможно, даже дать более конкретный ответ на уровне проблем? Например, включает в себя некоторые общепринятые формулировки. Если я правильно понял, когда вы переходите от SAT к SMT, вы в основном входите в...
Поскольку в Lambda the Ultimate не было ответа, я пробую это снова: системы переписывания терминов используются, например, в автоматизированной теореме, доказывающей символьные вычисления, и, конечно, для определения формальных грамматик. Есть некоторые языки программирования, основанные на...
Существуют ли проблемы в CS, где эффективные алгоритмы не известны, несмотря на теоремы существования, доказывающие, что такие эффективные алгоритмы должны существовать? Как называются эти проблемы? Где я могу узнать...
Одна из удивительных вещей в компьютерной науке заключается в том, что физическая реализация в некотором смысле «неактуальна». Люди успешно создали компьютеры из нескольких различных подложек - реле, вакуумных трубок, дискретных транзисторов и т. Д. Вскоре люди могут преуспеть в создании...
Возьмем ориентированный граф края которого украшены натуральным числом. Нам нужно множество всех путей P между двумя вершинами v 1 и v 2 , чтобы каждое последующее ребро в пути было украшено натуральным числом, которое больше натурального числа, украшающего предыдущее ребро.GGGPPPv1v1v_1v2v2v_2...
Извините, если это наивный вопрос, но я не смог найти оправдания ни в одном из основных учебников, таких как Бонди-Мёрти, Дистел или Уэст. У совершенных графиков есть много прекрасных свойств, но какова единственная причина, по которой их называют идеальными? Или это просто эстетическое...
Этот вопрос касается логики высказываний, и все случаи «разрешения» следует понимать как «предложенные решения». Этот вопрос является чем-то чрезвычайно основным, но это беспокоило меня некоторое время. Я вижу, как люди утверждают, что решение по предложению завершено, но я также вижу, что люди...
Долгое время я думал, что задача была NP-полной, если она (1) NP-сложная и (2) в NP. Однако в известной статье «Метод эллипсоидов и его последствия в комбинаторной оптимизации» авторы утверждают, что проблема дробного хроматического числа принадлежит NP и является NP-сложной, но пока неизвестно,...
Лемма: Предполагая, что эта эквивалентность у нас есть (\x -> ⊥) = ⊥ :: A -> B. Доказательство: ⊥ = (\x -> ⊥ x)по eta-эквивалентности и (\x -> ⊥ x) = (\x -> ⊥)по сокращению под лямбду. В отчете Haskell 2010, раздел 6.2, seqфункция определяется двумя уравнениями: seq :: a -> b...
Мы говорим, что функция f:N→Nf:N→Nf:\mathbb{N}\rightarrow\mathbb{N} является конструируемой во времени , если существует детерминированная многоленточная машина Тьюринга MMM которая на всех входах длины nnn делает не более f(n)f(n)f(n) шагов, и для каждого существует некоторый вход длина на которой...
Этот вопрос не может быть техническим. Как не носитель языка и ТА для класса алгоритма, я всегда задавался вопросом, что означает гаджет в «гаджете-предложении» или «гаджете-переменной». В словаре говорится, что гаджет - это машина или устройство, но я не уверен, какое это имеет разговорное...
Единственное определение «исчисления», которое я знаю, - это изучение пределов, производных, интегралов и т. Д. В анализе. В каком смысле лямбда-исчисление (или такие вещи, как mu calculus) является «исчислением»? Как это связано с исчислением в...
В настоящее время я слушаю выступление Алана Кейса "Это действительно сложно или мы просто усложнили?" ( https://www.youtube.com/watch?v=ubaX1Smg6pY&= ), где он говорит, что «семафоры были плохой идеей и что-то под названием псевдо-время было превосходным» (в 51:40 на связанном видео). Может...
Мне интересно, есть ли у следующей проблемы имя или какие-либо результаты, связанные с ним. Пусть - взвешенный граф, где обозначает вес ребра между и , и для всех , . Задача состоит в том, чтобы найти подмножество вершин, которое максимизирует сумму весов смежных с ними ребер: Обратите внимание,...
Все мы знаем, что минимальная сложность алгоритма сортировки на основе сравнения Ω ( n logн )Ω(NжурналN)\Omega(n \log n)сравнения. Я пытаюсь сделать слепой сортировку, т.е. с учетом числаNNn вывести схему (с логическими, арифметическими и "сравнительными" вентилями), которая сортирует список NNn...
Цветной граф можно описать как кортеж где - граф, а - раскраска. Два цветных графа и называются изоморфными, если существует такой изоморфизм , что выполняется раскраска, т.е. для всех v \ в V (G) .(G,c)(G,c)(G,c)GGGc:V(G)→Nc:V(G)→Nc : V(G) \rightarrow...