Недавно я чрезвычайно заинтересовался пониманием и доказательством аспектов (функциональных) языков программирования. Однако, как я углублюсь в глубину, такие вещи, как исчисление , теория категорий и денотационная семантика, немного трудно найти без надлежащего объяснения.λλ\lambda Я читаю SICP...
Я узнал, что в графическом процессоре есть нечто, называемое объединением памяти. Читая об этом, я не был ясно по теме. Это как-то связано с параллелизмом уровня памяти. Я искал в Google, но не смог получить удовлетворительный ответ. Было бы полезно, если бы кто-то дал более полное и понятное...
Немного подставного лица: я специалист по информатике и работаю программистом. Итак, извините, если эта подсказка кажется несколько за пределами левого поля - я обычно играю с математической симуляцией и открываю задачи, когда мне нечего делать. Играя с гипотезой Римана , я определил, что главный...
Пусть - фиксированная функция, построенная по времени.fff Классический универсальный результат моделирования для ТМ (Hennie and Stearns, 1966) гласит, что существует ТМ с двумя лентами , для которогоUUU описание МТ , и⟨M⟩⟨M⟩\langle M \rangle входная строка ,xxx работает для шагов и возвращает ответ...
Я читал в Stack Overflow вопрос о том, является ли NP- трудным перечисление всех простых циклов в графе, содержащем определенный узел, и мне пришло в голову, что я не могу придумать какой-либо существующий класс сложности, который хорошо подходит для разговор о проблемах в форме «перечислите все...
Я самообучающийся помощник по доказательствам и решил начать с некоторых базовых доказательств и продолжить работу. Поскольку доказательства основаны на других доказательствах и поэтому образуют иерархию, существует ли хранилище иерархии доказательств? Я знаю, что могу выбрать конкретного помощника...
Каковы некоторые примеры сложных проблем решения, которые могут быть решены за полиномиальное время? Я ищу проблемы, для которых оптимальный алгоритм является «медленным», или проблемы, для которых самый быстрый известный алгоритм является «медленным». Вот два примера: Распознавание совершенных...
Я интересно, что это лучший известный алгоритм, в терминах big- нотации, для решения целочисленных линейного программирования?OOO Я знаю, что проблема в полном, поэтому я не ожидаю ничего полиномиального. И я знаю, что есть много эвристик и тому подобного, которые используются в практических...
Может ли кто-нибудь отослать меня к рецензируемым статьям, изучающим преимущества или недостатки написания кода в функциональном стиле? Существуют ли документы, в которых обсуждается применение лямбда-исчисления в таких областях, как машинное обучение, языковой дизайн и т....
Классическое приложение «разделяй и властвуй» заключается в решении следующей проблемы: Учитывая массив различных сопоставимых элементов, подсчитайте количество пар инверсии в массиве: пар ( i , j ), таких что a [ i ] > a [ j ] и i < j .a[1…n]a[1…n]a[1\dots...
Пусть GGG граф, и пусть sss и ttt две вершины GGG . Можем ли мы эффективно выбрать равномерно и независимо случайным образом кратчайший путь sss - ttt из множества всех кратчайших путей между sss и ttt ? Для простоты можно предположить, что GGG простая, ненаправленная и невзвешенная. Даже во многих...
Предположим, нам даны два числа и и мы хотим найти для .lllrrrmax(i⊕j)max(i⊕j)\max{(i\oplus j)}l≤i,j≤rl≤i,j≤rl\le i,\,j\le r Наивный алгоритм просто проверяет все возможные пары; например, в ruby у нас будет: def max_xor(l, r) max = 0 (l..r).each do |i| (i..r).each do |j| if (i ^ j > max) max...
У меня есть ряд связанных вопросов по этим двум темам. Во- первых, большинство текстов сложности только замазывать класс NCNC\mathbb{NC} . Есть ли хороший ресурс, который более подробно освещает исследования? Например, то, что обсуждает все мои вопросы ниже. Кроме того, я предполагаю, что...
Мне 16 лет, и мой друг недавно подарил мне большую энциклопедию по информатике. Я обычно не очень интересуюсь компьютерами и технологиями, но компьютерные науки начали очаровывать меня. Однако я собираюсь изучать физику и / или математику, а не CS, поэтому мой вопрос: было бы полезно провести...
Согласно статье в Википедии , L в означает «сканирование слева направо», а «R» означает «крайний правый вывод». Однако в оригинальной статье Кнута по грамматике L R ( k ) он определяет язык L R ( k ) (на стр. 610) как язык, который «переводим слева направо с ограничением k ».L R (k )Lр(К)LR(k)L R (...
Один студент недавно попросил меня проверить доказательство твердости NP для них. Они выполнили сокращение в соответствии с: Я уменьшаю эту проблему P′п'P' которая, как известно, является NP-полной, к моей проблеме (с многократным уменьшением многократного числа), поэтому является NP-трудной.PпPPпP...
Не обращающие внимания на кэш алгоритмы и структуры данных - довольно новая вещь, представленная Frigo et al. в алгоритмах кеширования, 1999 . Тезис Прокопа того же года знакомит и с ранними идеями. Бумага Frigo et al. представить некоторые экспериментальные результаты, показывающие потенциал...
Проблема минимальной пропускной способности состоит в том, чтобы найти порядок узлов графа на целочисленной линии, который минимизирует наибольшее расстояние между любыми двумя соседними узлами. Решение проблемы является NP-полным даже для бинарных деревьев. Результаты сложности для минимизации...
Страница проблемы изоморфизма графов Википедии, похоже, указывает на то, что нет, она не была решена. Однако мой друг указал на Алгоритм Полиномиального Времени для Изоморфизма Графов . Я недостаточно опытен, чтобы следовать рассуждениям в газете. У меня есть собственная очень грубая попытка...
Проблема почтовой корреспонденции (PCP) неразрешима. Ограниченная версия PCP является -полной и отмеченная версией PCP (слова одного из двух списков, должны отличаться по первой букве) в P S P A C E [1].Н ПNп\mathrm{NP}P S P A C EпSпAСЕ\mathrm{PSPACE} Используются ли эти ограниченные версии, чтобы...