В литературе достаточно ясно, что ОЗУ с удельной стоимостью с примитивным умножением являются необоснованными, поскольку они не может быть смоделировано машинами Тьюринга за полиномиальное время может решить PSPACE-полные задачи за полиномиальное время Тем не менее, все ссылки, которые я могу найти...
Есть ли какой-нибудь естественный или заметный способ связать или связать математические группы и формальные языки CS или какую-то другую основную концепцию CS, например машины Тьюринга? Я ищу ссылки / приложения. Однако обратите внимание, что я знаю о связи между полугруппами и языками CS (а...
Мне было интересно, если кто-то знал происхождение модели клиент-сервер. Откуда этот термин (бумага, программное приложение,
Я продолжаю слышать о том, как нужно изучать теорию категорий, чтобы действительно понять теорию языка программирования. До сих пор я выучил много PL, даже не ступая в царство категорий. Тем не менее, я подумал, что пришло время сделать прыжок, чтобы увидеть, что я пропустил. К сожалению, ни один...
Мне интересно, какова сложность определения пустоты для двусторонних DFA? То есть конечные автоматы, которые могут двигаться назад на своей ленте ввода только для чтения. Согласно Википедии, они эквивалентны DFA, хотя эквивалентный DFA может быть экспоненциально больше. Я обнаружил сложность...
В компьютерной науке существует такая популярная проблема [1] [2], которая заключается в нахождении минимального числа прямых, охватывающих данный набор точек в 2D. Несмотря на то, что я отсканировал много бумаг, ни у одной из них нет четкой мотивации проблемы. Какая польза от решения этой...
С точки зрения асимптотического времени выполнения в наихудшем случае, какая NP-полная задача имеет самый известный (точный) алгоритм и что это за алгоритм? Известно ли что-то, что быстрее, чем...
Я не знаю, было ли это шуткой, но однажды я прочитал то, что упоминалось как формальное определение файла в системе управления версиями, такой как git, hg или svn. Это было что-то вроде математического объекта, такого как гомеоморфизм. Это была шутка или действительно теория информатики о системах...
Я пытаюсь решить проблему SAT переменных 25k пунктов 5k переменных. Так как он работал в течение часа (precosat), и я хотел бы потом решить более крупные, я ищу многоядерный SAT-Solver. Кажется, что есть много SAT-Solvers, я совершенно потерян. Кто-нибудь может указать мне лучший вариант для моего...
Можете ли вы дать мне несколько советов о хорошей вводной (но всеобъемлющей) книге о логике и вычислениях? Некоторые нечеткие темы, которые я имею в виду: Presburger artihm., PA, ZF, ZFC, HOL Теория множеств, Теория типов Моделирование вычислений (машины Тьюринга) в разных теориях Связи с...
Согласно статье в Википедии о схемах аппроксимации за полиномиальное время : Все проблемы в FPTAS доступны для фиксированных параметров. Этот результат меня удивляет - эти занятия, похоже, совершенно не похожи друг на друга. FPTAS характеризует проблемы по тому, насколько легко их аппроксимировать,...
Учитывая заданий , для выполнения каждого задания требуется раз.J 1 , J 2 , . , , , J п Г я > 0 , Т я ∈ NnnnJ1,J2,...,JnJ1,J2,...,JnJ_1,J_2,...,J_nTi>0,Ti∈NTi>0,Ti∈NT_i > 0, T_i \in N Каждое задание должно быть предварительно обработано и постобработано одной машиной M, которая может...
Мой вопрос к тем, кто занимается алгоритмикой вычислительной биологии. Этой осенью я собираюсь пройти курс биоинформатики; проблема, однако, в том, что у меня слишком мало знаний в области биологии и химии, чтобы чувствовать себя подготовленным к этому циклу лекций (я был довольно слаб в этих...
Существует ли какой-либо инструмент для создания прототипа семантики и системы типов языка программирования, который также позволяет выполнять некоторую проверку моделей стандартных свойств, например, правильности типа? Я спрашиваю об этом, потому что я читаю книгу по Alloy, и она предоставляет...
Все знают «Garey & Johnson», и я всегда обращаюсь к ним, когда мне нужно выполнить преобразование для доказательства NP-твердости. Однако недавно я нуждался в доказательстве твердости APX, и мне интересно, есть ли подобный (и более современный ...?) Набор проблем, которые, как было показано,...
Хотите улучшить этот пост? Предоставьте подробные ответы на этот вопрос, включая цитаты и объяснение того, почему ваш ответ правильный. Ответы без достаточной детализации могут быть отредактированы или удалены. Мне было поручено создать библиотеку книг по алгоритмам для нашей небольшой компании...
Закрыто . Этот вопрос основан на мнении . В настоящее время он не принимает ответы. Хотите улучшить этот вопрос? Обновите вопрос, чтобы ответить на него фактами и цитатами, отредактировав этот пост . Закрыто 4 года назад . Я увлекаюсь математической элегантностью и строгостью, и сейчас ищу такую...
На работе мне было поручено вывести некоторую информацию о типах динамического языка. Я переписываю последовательности операторов во вложенные letвыражения, например так: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then {...
Мне интересно, есть ли какие-нибудь -hard проблемы, которые являются «полиномиальными» в среднем случае. Я думаю, что есть два способа интерпретировать это?NпNпNP Если , может ли быть алгоритм, решающий задачу N P -hard, с амортизированным (в среднем случае) временем работы O ( n k ) для константы...
Мне сказали, что квантовые компьютеры не являются вычислительно более мощными, чем машины Тьюринга. Может ли кто-нибудь любезно помочь дать некоторые литературные ссылки, объясняющие этот...