В 1937 году Тьюринг описал машину Тьюринга. С тех пор многие модели вычислений были описаны в попытке найти модель, которая похожа на настоящий компьютер, но все же достаточно проста для разработки и анализа алгоритмов. В результате мы имеем дюжину алгоритмов для, например, SORT-задачи для разных...
Пол Вегнер и Дина Голдин уже более десяти лет публикуют статьи и книги, утверждая, прежде всего, что тезис Черча-Тьюринга часто искажается в сообществе теории КС и в других местах. То есть он представлен как охватывающий все вычисления, когда на самом деле он применяется только к вычислению...
Этот вопрос похож на более общий вопрос о том, какова правильная теоретическая модель компьютера для разработки алгоритма и структур данных. Здесь я задаю конкретный вопрос о современных высокопроизводительных компьютерах (например, тех, которые перечислены в списке 500 лучших ) или даже о...
В недавнем вопросе обсуждался теперь классический алгоритм динамического программирования для TSP, независимо от Беллмана и Хельда-Карпа . Алгоритм повсеместно сообщается работать в O(2nn2)O(2nn2)O(2^n n^2) времени. Однако, как недавно заметил один из моих учеников, это время выполнения может...
Насколько хорошо была исследована следующая проблема в TCS? (Я извиняюсь, если постановка проблемы звучит расплывчато!) При наличии модели вычислений MC (машина Тьюринга, сотовые автоматы, машина Колмогорова-Успенского ... и т. Д.) И модели шума, которая может повлиять на вычисление MC, существует...
Какой класс сложности связан с исчерпывающими алгоритмами поиска? (если есть) Это NP или PSPACE? Существуют ли ограниченные модели вычислений, охватывающие класс алгоритмов исчерпывающего поиска, аналогичных моделям для жадного и динамического...
Можно ли создать единственную (не полную по Тьюрингу) механическую реализацию, скажем, Microsoft Word? Можно ли реализовать такие вещи, как итераторы, функции первого порядка, весь спектр методов программирования? Могут ли шестерни и другие механические части представлять структуры данных или даже...
Название немного вводит в заблуждение, но, надеюсь, вопрос не в следующем: Новый результат Грёнлунда и Петти, показывающий, что 3SUM имеет только сложность дерева решений, заставил меня задуматься:O(n3/2)O(n3/2)O(n^{3/2}) Есть ли простой пример проблемы со сложностью дерева решений но допускающей...
В то время как EE старшекурсник я посетил некоторые лекции, которые представили хорошую характеристику булевых схем с точки зрения, сколько у них вложенных циклов. По своей сложности булевы схемы часто считаются дагами, но в реальных аппаратных циклах это обычное явление. Теперь, по модулю...
Правильно ли называть инфраструктуру mapReduce типом структуры объемного синхронного параллельного программирования без сохранения локальной памяти в процессорах между синхронизациями? Если нет, то какая модель параллельного программирования наиболее точно инкапсулирует каркас...
Этот вопрос касается того, существуют ли какие-либо известные обратимые тарпиты Тьюринга, где «обратимый» означает в смысле Аксельсена и Глюка , а «тарпит» является гораздо более неформальным понятием (и, возможно, не очень удачным выбором слова), но я сделаю все возможное, чтобы объяснить, что я...
Хорошо известными примерами вычислений, вдохновленных природными явлениями, являются квантовые компьютеры и компьютеры с ДНК. Что известно о потенциале и / или ограничениях вычислений по законам Максвелла или гравитации? То есть непосредственное включение природных «быстрых» решений уравнений...
Есть ли структура / формализм, который определяет вычислительные модели, основанные на белках, отличных от модели ДНК Адлемана или этой работы Черри и Цянь...