0
голосов
0
ответов
41 показ
КМП автоматы, суффиксные автоматы
Задача 1:С помощью алгоритма минимизации ДКА докажите, что ДКА КМП A_{w} для любого слова w ∈ T^{∗} является минимальным полным ДКА для языка Suff(w) ...
1
голос
1
ответ
106 показов
Классы L-эквивалентности Майхилла-Нероуда
Опишите классы Майхилла-Нероуда для языка L={w|w=w^R} над алфавитом T={a,b}.Примечание: необходимо указать множества, на которые разбивается T^*, пока ...
0
голосов
0
ответов
147 показов
Однопроходный алгоритм одной задачи
Как решить данную задачу за один проход или не более чем за O(n)? Может быть с созданием предварительно какой-то структуры? Задача. Дана последователь ...
0
голосов
0
ответов
77 показов
Докажите рекурсивную перечислимость множества
Докажите рекурсивную перечислимость следующего множества:$$A = \{x |\ \varphi_x\ \text{принимает хотя бы одно значение, являющееся степенью числа 2}\} ...
0
голосов
0
ответов
86 показов
Доказать рекурсивность множества
Пусть B ⊆ N × N есть рекурсивное множество пар натуральных чисел. Докажите, что мно-жество A, состоящее из всех таких z ∈ N, что точка (z, z) лежит в ...
0
голосов
0
ответов
62 показа
Проверить множество на рекурсивность
Пусть множество A ⊆ N рекурсивно, а f : N → N тотальная строго возрастающая вычислимаяфункция, т. е. f(x) < f(y) для всех x < y. Верно ли, что м ...
0
голосов
0
ответов
99 показов
Доказать, что множество не является рекурсивно перечислимым
Докажите, что множество$$A = \{ x \mid W_{x} \text{ либо пусто, либо одноэлементно}\},$$не является рекурсивно перечислимым. Здесь$$W_{x} = \{y \mid \ ...
0
голосов
0
ответов
61 показ
Доказать рекурсивную перечислимость множества
Докажите рекурсивную перечислимость следующего множества$$A = \{ x \mid \varphi_x \text{ принимает значение 2021 хотя бы в двух различных точках. } \} ...
0
голосов
0
ответов
86 показов
Является ли множество рекурсивно перечислимым
Пусть f : N → \N тотальная вычислимая функция. Верно ли, что множество всех натуральныхчисел x таких, что f(y) < f(x) для некоторого y > x, явля ...
0
голосов
0
ответов
89 показов
Доказать, что функция вычислима [закрыт]
Пусть всюду определенная функция f : N → N строго возрастает, т. е. f(x) < f(y) для всех x < y,а множество N \ rng(f) конечно (здесь rng(f) есть ...
0
голосов
0
ответов
145 показов
Теория алгоритмов _ Примитивная рекурсивность
Задача такая: Доказать, что функция f(x)=[log2(x)] примитивно рекурсивная ([ ] - целая часть). Важно доказать это БЕЗ использования ограниченного "мю" ...
-1
голосов
1
ответ
210 показов
Доказать рекурсивно-примитивную рекурсию
Задача доказать, что функция рекурсивно-примитивная [log2(x)] - целая часть от логарифмапо условию сначала доопределяем f(0) = [log2(x)]=0далее f(x+1) ...
0
голосов
0
ответов
90 показов
Загадано k-элементное подмножество n-элементного множества
Загадано k-элементное подмножество K n-элементного множества N.За один шаг можно спросить, лежит ли некоторое подмножество G множества N полностью вну ...
0
голосов
0
ответов
80 показов
Оцените трудоемкость рекурсивного алгоритма
Оцените трудоемкость рекурсивного алгоритма, разбивающего исходную задачу размераn на n задач размеров n/2 каждая, используя для этого n операций.1. М ...
0
голосов
0
ответов
75 показов
Любую программу можно реализовать на ограниченном компьютере
Докажите, что любую программу, которая использует неограниченную оперативную память, можно реализовать на ограниченном компьютере,который использует к ...
194 вопроса
Связанные метки
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.