Зарезервировано - не следует использовать для большинства новых вопросов. Вопросы широкого спектра об общих методах и концепциях, таких как методы доказательства, инструменты для анализа алгоритмов или основы компьютерной архитектуры. Это не для вопросов, требующих ссылок, то есть книг или статей.
Существует множество вопросов о том, как анализировать время выполнения алгоритмов (см., Например, анализ времени выполнения и анализ алгоритма ). Многие из них похожи, например, те, которые запрашивают анализ затрат на вложенные циклы или алгоритмы «разделяй и властвуй», но большинство ответов,...
Преобразование регулярных выражений в (минимальный) NFA, который принимает тот же язык, легко с помощью стандартных алгоритмов, например , алгоритма Томпсона . Другое направление кажется более утомительным, и иногда получающиеся выражения являются грязными. Какие существуют алгоритмы для...
Существует множество попыток доказать либо либо , и, естественно, многие люди задумываются над этим вопросом, имея идеи для доказательства того или иного направления.P ≠ N PP = N Pпзнак равноNп\mathsf{P} = \mathsf{NP} P ≠ N Pп≠Nп\mathsf{P} \neq \mathsf{NP} Я знаю, что есть подходы, которые, как...
В большинстве вводных классов алгоритмов вводятся нотации, такие как (Big O) и , и студент, как правило, учится использовать одну из них для определения сложности времени.ΘОOOΘΘ\Theta Однако есть и другие обозначения, такие как , и . Существуют ли какие-либо конкретные сценарии, в которых одна...
Обычно в алгоритмах мы не заботимся о сравнении, сложении или вычитании чисел - мы предполагаем, что они выполняются за время . Например, мы предполагаем это, когда говорим, что сортировка на основе сравнения - это O ( n log n ) , но когда числа слишком велики, чтобы поместиться в регистры, мы...
Люди часто говорят, что парсеры LR (k) более мощные, чем парсеры LL (k) . Эти заявления в большинстве случаев расплывчаты; в частности, следует ли сравнивать классы для фиксированного или объединения по всем ? Так как на самом деле ситуация? В частности, меня интересует, как вписывается LL...
Есть много способов доказать, что язык не является регулярным , но что мне нужно сделать, чтобы доказать, что какой-то язык является регулярным? Например, если мне дано, что регулярно, как я могу доказать, что следующее регулярно?LLLL'L′L' L': = { w ∈ L : u v = w для u ∈ Σ*∖ L и v ∈...
Предположим, что я программист, и у меня есть NP-полная проблема, которую мне нужно решить. Какие методы доступны для решения проблем с NPC? Есть опрос или что-то похожее на эту...
Я был компьютерным ботаником много-много лет. Я могу программировать на нескольких языках и даже могу их создавать. Я сел с приятелем на днях и спросил, как компьютер на самом деле берет электричество и что-то с ним делает, и мы просто не могли понять это, и Google тоже не сильно помог. Я имею в...
В теории вычислимости и сложности (и, возможно, в других областях) сокращения являются повсеместными. Существует много видов, но принцип остается тем же: показать, что одна проблема L1L1L_1 , по крайней мере, так же трудна, как и другая проблема L2L2L_2 путем сопоставления экземпляров из с...
Похоже, что на этом сайте люди часто исправляют других за запутанные «алгоритмы» и «проблемы». В чем разница между этими? Как я узнаю, когда мне следует рассмотреть алгоритмы и рассмотреть проблемы? И как они связаны с понятием языка в теории формального...
Предположим, у меня есть список функций, например nloglog(n),2n,n!,n3,nlnn,…nloglog(n),2n,n!,n3,nlnn,…\qquad n^{\log \log(n)}, 2^n, n!, n^3, n \ln n, \dots Как мне отсортировать их асимптотически, т.е. после отношения, определенного f≤Og⟺f∈O(g)f≤Og⟺f∈O(g)\qquad f \leq_O g \iff f \in O(g) , при...
Это может звучать как глупый вопрос, но мне действительно интересно узнать, как компьютер знает, что ? Кроме того, как компьютер узнает, что порядок целых чисел равен и алфавит A, B, C, D, ...? Это где-то хранится в оборудовании или операционная система предоставляет такую информацию?1 , 2 , 3 ,...
Есть много способов доказать, что язык не является контекстно-свободным, но как мне доказать, что язык не является контекстно-независимым? Какие методы существуют, чтобы доказать это? Очевидно, один из способов - показать контекстную грамматику для языка. Существуют ли какие-либо систематические...
Задание формальных языков с помощью формальных грамматик является частой задачей: нам нужны грамматики не только для описания языков, но также для их анализа или даже для правильной науки . Во всех случаях важно, чтобы грамматика под рукой была правильной , то есть генерировала именно нужные слова....
В моем курсе теории вычислений многие наши проблемы связаны с использованием индукции по длине входной строки для доказательства утверждений о конечных автоматах. Я понимаю математическую индукцию, однако, когда вступают в игру струны, меня сильно сбивают с толку. Я был бы очень признателен, если...