Вопросы по теме 'computation-theory'
Как написать перечисление всех вычислимых функций?
Мотивация: я хотел бы иметь возможность использовать функциональное программирование игрушек на языках без функций первого порядка, используя натуральные числа вместо функций.
Универсальная функция - это функция f: N -> (N -> N), эквивалентно f: N...
1434 просмотров
schedule
16.05.2022
Хорошие ресурсы для изучения моделей вычислений?
Из любопытства я пытаюсь определить, какой модели вычислений система, с которой я работаю, функционально эквивалентна, и доказать эквивалентность. Чем дольше я занимаюсь этой проблемой, тем больше подозреваю, что система не эквивалентна Тьюрингу. Я...
691 просмотров
schedule
15.10.2022
Ключевые моменты и важность разрешимости
Язык разрешим, если TM распознает язык и переходит в состояние Accept или Reject. Как разраб. Я думаю, что это важно, поскольку это означало бы, что мы могли бы определить, содержит ли программа переполнение буфера или тупиковые ситуации. Также...
1291 просмотров
schedule
22.08.2022
Колмогоровская сложность
Я буду более чем благодарен, если кто-нибудь сможет объяснить мне, как колмогоровская сложность связана со случайностью и случайными входными данными.
Еще одна вещь, которую я не могу понять, - мы знаем, что вычисление колмогоровской сложности для...
962 просмотров
schedule
13.10.2022
Примеры задач не в P и не в NP-полных, а в NP
В колледже у меня есть курс под названием «Анализ алгоритмов», где мы сейчас изучаем разные классы сложности - P, NP, NP-hard и т. Д.
Мы уже обсуждали NP-полные проблемы как пересечение между NP и NP-трудными и P-проблемами, содержащимися в NP. Мы...
9006 просмотров
schedule
20.01.2023
Подсчитайте все подмножества массива, где наибольшее число является суммой оставшихся чисел
Я боролся с уровнем 3 испытания Греплина. Для тех, кто не в курсе, вот проблема:
вы должны найти все подмножества массива, где наибольшее число равно сумме остальных чисел. Например, для ввода:
(1, 2, 3, 4, 6)
подмножества будут
1 + 2 = 3...
2769 просмотров
schedule
08.12.2023
Написание программы, которая пишет программу
В теоретической информатике хорошо известно, что программа "Hello world tester" - неразрешимая проблема. (Вот ссылка, которую я имею в виду под hello world tester Мой вопрос в том, что, поскольку введена программа в качестве входных данных, мы не...
1544 просмотров
schedule
27.07.2022
Эквивалентность моделей вычислений
Я ищу объяснение того, как можно доказать, что модели вычислений эквивалентны. Я читал книги на эту тему, за исключением того, что доказательства эквивалентности опущены. У меня есть базовое представление о том, что означает эквивалентность двух...
880 просмотров
schedule
16.12.2023
Устранение левой рекурсии
У меня есть эта грамматика
S->S+S|SS|(S)|S*|a
Я хочу знать, как исключить левую рекурсию из этой грамматики, потому что S+S действительно сбивает с толку ...
2494 просмотров
schedule
19.05.2024
Алгоритмический анализ сложности: практическое использование метода обычных операций Кнута (oops) и операций с памятью (mems)
При реализации большинства алгоритмов (сортировки, поиска, обхода графа и т. д.) часто приходится идти на компромисс, сокращая доступ к памяти за счет дополнительных обычных операций.
У Кнута есть полезный метод для сравнения сложности различных...
426 просмотров
schedule
22.02.2022
Самая медленная вычислительная сложность (Big-O)
Я знаю, что из этих алгоритмов Alg1 является самым быстрым, так как это n в квадрате. Следующим будет Alg4, так как он n в кубе, а затем Alg2, вероятно, самый медленный, поскольку он 2^n (который должен иметь очень низкую производительность)....
14942 просмотров
schedule
27.04.2023
Расчет вычислительной сложности (Big-O)
Algorithm 1. QUEUESTUFF(n)
Input: Integer n
1) Let Q = an empty Queue
2) For i = 1 to n
3) Q.Enqueue(i)
4) End For
5) For i = 1 to n-1
6) Let X = Q.Dequeue()
7) End For
8) Let X = Q.Dequeue()
Output: The contents of X
What is the computational...
295 просмотров
schedule
06.09.2022
Устраните эту косвенную левую рекурсию
Следующая грамматика оставила рекурсию.
X - начальный символ.
X -> Xa | Zb
Z -> Zc | d | Xa
Как это убрать? Пожалуйста, объясните это шаг за шагом.
531 просмотров
schedule
17.05.2022
Как разделить состояния DFA, находящиеся в мертвом состоянии, во время минимизации одного и того же
Когда мы хотим минимизировать DFA, сначала мы разделяем конечные и неконечные состояния. Затем мы делим эти состояния еще на несколько разделов, пока все состояния в каждом разделе не будут принадлежать одному и тому же классу эквивалентности. Теперь...
979 просмотров
schedule
12.05.2022
Интересно, следующий язык конечен
Есть вопрос о том, является ли следующий язык конечным или нет в моем классе
{w : w – регулярное выражение для {a m b n :m+n≤k}}, где k – конкретное натуральное число.
Я думаю, что это конечно, потому что в языке может быть не более...
39 просмотров
schedule
02.08.2022
Теория интерпретаторов, частичных вычислителей и компиляторов
Итак, я изучал стековые машины, интерпретаторы, компиляторы и некоторые другие вещи, связанные с языками программирования и их общей теорией. Большинство материалов, которые я нахожу в книгах и в Интернете, очень специализированы и касаются одной...
213 просмотров
schedule
25.03.2023
бикличные реализации покрытия
Известно, что проблема покрытия сложна и для аппроксимации. Кто-нибудь знает какое-либо программное обеспечение, которое реализует какую-то практическую эвристику?
55 просмотров
schedule
02.12.2023
DFA для этого языка
Σ={ a, b, c, d } L={ x ∈ Σ* | x не начинается и не заканчивается на "bab" }
Примеры, которые следует принять:
абаба
аббревиатура
ббабб
ббаба
ab
ba
аааа
ɛ
Примеры, от которых следует отказаться:
баб
баба
бабк...
232 просмотров
schedule
24.06.2023
Справка по регулярному выражению для идентификатора в лексическом анализаторе
Я пытаюсь создать лексер, я не хочу использовать файл lex , потому что хочу учиться, поэтому перейдем к тому, что я хочу создать регулярное выражение для идентификатора со следующими ограничениями:
'__' не может быть идентификатором....
505 просмотров
schedule
12.11.2023
Можно ли уменьшить набор, независимый от K, до 2-SAT
Это вопрос домашнего задания для начала. Перед тем, как я начну, у меня есть несколько вопросов.
Наша проблема:
«Сократите k-независимое множество до 2-SAT следующим образом. Для графа G с n вершинами формируется n предложений, по одному на...
1218 просмотров
schedule
12.05.2022
