Вопросы с тегом «machine-models»

41
Какая модель вычислений является «лучшей»?

В 1937 году Тьюринг описал машину Тьюринга. С тех пор многие модели вычислений были описаны в попытке найти модель, которая похожа на настоящий компьютер, но все же достаточно проста для разработки и анализа алгоритмов. В результате мы имеем дюжину алгоритмов для, например, SORT-задачи для разных...

38
Применимость тезиса Черча-Тьюринга к интерактивным моделям вычислений

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

20
Какова правильная теоретическая модель для разработки алгоритмов для современных и будущих высокопроизводительных компьютеров

Этот вопрос похож на более общий вопрос о том, какова правильная теоретическая модель компьютера для разработки алгоритма и структур данных. Здесь я задаю конкретный вопрос о современных высокопроизводительных компьютерах (например, тех, которые перечислены в списке 500 лучших ) или даже о...

16
Временная сложность алгоритма Беллмана-Хелда-Карпа для ТСП, дубль 2

В недавнем вопросе обсуждался теперь классический алгоритм динамического программирования для TSP, независимо от Беллмана и Хельда-Карпа . Алгоритм повсеместно сообщается работать в O(2nn2)O(2nn2)O(2^n n^2) времени. Однако, как недавно заметил один из моих учеников, это время выполнения может...

14
Что известно об эффективности надежных вычислений?

Насколько хорошо была исследована следующая проблема в TCS? (Я извиняюсь, если постановка проблемы звучит расплывчато!) При наличии модели вычислений MC (машина Тьюринга, сотовые автоматы, машина Колмогорова-Успенского ... и т. Д.) И модели шума, которая может повлиять на вычисление MC, существует...

14
Класс сложности, связанный с исчерпывающим поиском

Какой класс сложности связан с исчерпывающими алгоритмами поиска? (если есть) Это NP или PSPACE? Существуют ли ограниченные модели вычислений, охватывающие класс алгоритмов исчерпывающего поиска, аналогичных моделям для жадного и динамического...

13
Может ли какая-либо программа быть реализована механически?

Можно ли создать единственную (не полную по Тьюрингу) механическую реализацию, скажем, Microsoft Word? Можно ли реализовать такие вещи, как итераторы, функции первого порядка, весь спектр методов программирования? Могут ли шестерни и другие механические части представлять структуры данных или даже...

13
Обеспечиваемые разрывы между сложностью дерева решений и «истинной» сложностью

Название немного вводит в заблуждение, но, надеюсь, вопрос не в следующем: Новый результат Грёнлунда и Петти, показывающий, что 3SUM имеет только сложность дерева решений, заставил меня задуматься:O(n3/2)O(n3/2)O(n^{3/2}) Есть ли простой пример проблемы со сложностью дерева решений но допускающей...

11
Люди смотрят на циклическое гнездо в логических цепях?

В то время как EE старшекурсник я посетил некоторые лекции, которые представили хорошую характеристику булевых схем с точки зрения, сколько у них вложенных циклов. По своей сложности булевы схемы часто считаются дагами, но в реальных аппаратных циклах это обычное явление. Теперь, по модулю...

11
Является ли инфраструктура MapReduce типом BSP?

Правильно ли называть инфраструктуру mapReduce типом структуры объемного синхронного параллельного программирования без сохранения локальной памяти в процессорах между синхронизациями? Если нет, то какая модель параллельного программирования наиболее точно инкапсулирует каркас...

10
Обратимые брезенты Тьюринга?

Этот вопрос касается того, существуют ли какие-либо известные обратимые тарпиты Тьюринга, где «обратимый» означает в смысле Аксельсена и Глюка , а «тарпит» является гораздо более неформальным понятием (и, возможно, не очень удачным выбором слова), но я сделаю все возможное, чтобы объяснить, что я...

9
Естественное вычисление, основанное на фундаментальных силах

Хорошо известными примерами вычислений, вдохновленных природными явлениями, являются квантовые компьютеры и компьютеры с ДНК. Что известно о потенциале и / или ограничениях вычислений по законам Максвелла или гравитации? То есть непосредственное включение природных «быстрых» решений уравнений...