Информатика

25
Какова связь между языками программирования, регулярными выражениями и формальными языками

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

25
В чем разница между «страницей» памяти и «рамкой» памяти?

В WP адекватное обсуждение пейджинга , которое, я думаю, я понимаю. Однако меня смущают статьи, в которых неоднократно используется термин Page Frame . Я думал, что рамки и страницы - это разные вещи. Может ли кто-нибудь, пожалуйста, уточнить...

25
Если проблема двух генералов неразрешима, как мы, люди, можем договориться о вещах?

Если проблема двух генералов неразрешима, как мы, люди, можем договориться о вещах? Я имею в виду, что мы общаемся каждый день и имеем те же ограничения, что и любая проблема общения, которую решает информатика. Почему это не влияет на...

25
Решаема ли проблема остановки для чистых программ на идеальном компьютере?

Довольно просто понять, почему проблема остановки неразрешима для нечистых программ (т. Е. Программ, в которых ввод / вывод и / или состояния зависят от состояния машины); но интуитивно кажется, что остановка чистой программы на идеальном компьютере может быть решена, например, статическим...

25
Нахождение минимального разреза неориентированного графа

Вот вопрос из прошлого экзамена, который я пытаюсь решить: Для неориентированного графа с положительными весами w ( e ) ≥ 0 я пытаюсь найти минимальный разрез. Я не знаю других способов сделать это, кроме использования теоремы о максимальном потоке. Но график ненаправленный, так как мне его...

25
Доказательство неразрешимости проблемы остановки

У меня возникли проблемы с пониманием доказательства неразрешимости проблемы остановки. Если возвращает то, останавливается ли программа a на входе b , почему мы должны передавать код P для a и b ?H(a,b)H(a,b)H(a,b)aaabbbPPPaaabbb Почему мы не можем подать с помощью P и некоторого произвольного...

25
Есть ли фильтр против Блума?

Bloom фильтр позволяет эффективно отслеживать ли уже встречались различные значения в процессе обработки. Когда имеется много элементов данных, тогда фильтр Блума может привести к значительной экономии памяти по хеш-таблице. Основная особенность фильтра Блума, который он разделяет с хеш-таблицей,...

25
Структура данных с поиском, вставкой и удалением за амортизированное время ?

Существует ли структура данных для ведения упорядоченного списка, которая поддерживает следующие операции за время амортизации ?O ( 1 )O(1)O(1) GetElement (k) : возвращает й элемент списка.Кkk InsertAfter (x, y) : вставить новый элемент y в список сразу после x. Удалить (x) : удалить x из списка....

25
Разве случайность фон Неймана в кавычках больше не применима?

Какой-то парень сказал следующее: Любой, кто пытается генерировать случайные числа детерминистскими средствами, конечно же, живет в состоянии греха. Это всегда означает, что вы не можете генерировать истинные случайные числа только с помощью компьютера. И он сказал, что когда компьютеры были...

25
Существуют ли проблемы, которые легко вычислить, но трудно проверить?

Предполагая, что P NP, NP-полные проблемы «трудно решить, но есть ответы, которые легко проверить». Имеет ли смысл рассматривать противоположные, то есть проблемы, для которых легко вычислить правильный ответ, но трудно проверить произвольное предполагаемое решение?≠≠\neq Я думаю, что такая...

25
Есть ли доказательства того, что использование динамических языков влияет на производительность?

Мне интересно, есть ли какие-либо эксперименты, которые показывают существование или отсутствие корреляции между использованием динамического языка (такого как Python, Ruby, или даже языков, которые работают на платформе Java, таких как Groovy, Clojure) над статический язык (например, C / C ++) и...

25
Алгоритм распределения предметов «равномерно»

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

25
Почему алгоритм вращения Splay Tree учитывает как родительский, так и родительский узел?

Я не совсем понимаю, почему при ротации в структуре данных Splay Tree учитывается не только родительский узел рейтингового узла, но и прародитель (операция zig-zag и zig-zig). Почему следующее не работает: Когда мы вставляем, например, новый узел в дерево, мы проверяем, вставляем ли мы в левое или...

25
Почему не используются реверсивные ворота?

Я читал книгу «Сингулярность близка», написанную Курцвейлом, и он упомянул обратимые ворота, например, ворота Фредкина . Преимущество использования таких элементов состоит в том, что мы можем избавиться от тепловых потерь, связанных с вычислениями, когда биты просто исчезают в тепле, и вычисления...

25
Обучение NP-полноте - сокращения Тьюринга против сокращений Карпа

Меня интересует вопрос о том, как лучше всего преподавать NP-полноту специальностям информатики. В частности, должны ли мы учить этому, используя сокращения Карпа или сокращения Тьюринга? Я чувствую, что концепции NP-полноты и сокращения - это то, что должен изучать каждый специалист по...

25
Эффективная структура картографических данных, поддерживающая приблизительный поиск

Я ищу структуру данных, которая поддерживает эффективный приблизительный поиск ключей (например, расстояние Левенштейна для строк), возвращая максимально возможное совпадение для клавиши ввода. Наилучшей структурой данных, которую я нашел до сих пор, являются деревья Буркхарда-Келлера , но мне было...

25
«Плотные» регулярные выражения порождают

Вот гипотеза для регулярных выражений: Для регулярного выражения пусть длина | R | быть количеством символов в нем, игнорируя скобки и операторы. Например | 0 ∪ 1 | = | ( 0 ∪ 1 ) ∗ | = 2ррR| R ||р||R|| 0∪1 | = | (0∪1 )*| =2|0∪1|знак равно|(0∪1)*|знак равно2|0 \cup 1| = |(0 \cup 1)^*| = 2 Гипотеза:...

25
Почему эта неразрешимая проблема в NP?

Очевидно, что в NP нет неразрешимых проблем. Однако, согласно Википедии : NP - это совокупность всех задач решения, для которых в случаях, когда ответ «да», есть [... доказательства, которые] проверяются за полиномиальное время с помощью детерминированной машины Тьюринга. [...] Говорят, что...

25
Инструменты визуального программирования, почему они не работают с AST напрямую?

Я нашел несколько инструментов визуального программирования с открытым исходным кодом, таких как Blockly и друзья, и другие проекты, размещенные на Github, но не смог найти ни одного, который бы работал непосредственно с абстрактным синтаксическим деревом. Почему это? Я спрашиваю, потому что, как...