теория-алгоритмов

новыебез ответаценныетекущиеизбранныенепринятые
0
голосов
0
ответов
116 показов

Докажите, что множество A = {x ∣ ωx либо пусто, либо одноэлементно} не является перечислимым.
0
голосов
0
ответов
113 показов

Пусть множество A ⊆ N разрешимо, а тотальная вычислимая функция f∶N → N строго возрастает, т.е. f(x) < f(y) для всех x < y. Верно ли, что множес ...
0
голосов
0
ответов
123 показа

Докажите перечислимость следующего множества:A = {x ∣ φx принимает значение 1111 хотя бы в двух различных точках}
1
голос
2
ответа
272 показа

Задам дилетантский вопрос. Каким образом из теоремы Пенроуза следует невозможность создания ИИ? Пенроуз доказал, что ИИ невозможно реализовать на коне ...
0
голосов
0
ответов
73 показа

Всем привет! Кто может помочь составить нормальный алгоритм Маркова для сравнения двух чисел в унарной системе? Машину Тьюринга я сделал, а понять как ...
0
голосов
1
ответ
193 показа

Рассмотрим частичную функцию $$f(x) = \mu y(1 \dot{-} |g(y) - x| = 0)$$ где $$g(y) = \begin{cases} 3y + 1, \text{если } y \neq 4 \\ \text{не определен ...
0
голосов
0
ответов
147 показов

Помогите пожалуйста с теорией алгоритмов1 . Доказать, что функция φ (x) = n является примитивно рекурсивной,используя определение ПРФ2 . Определить фу ...
0
голосов
0
ответов
158 показов

В одном из алгоритмов сжатия используется следующая процедура разбиения данных на блоки:Первый символ строки образует первый блок.Выбирается наибольши ...
0
голосов
0
ответов
162 показа

Реализовать Машину Тьюринга, сделать проверку работы МТ на примере.УУ (курсор) в начале просматривает пустую ячейку справа от последнего слова. Алфави ...
0
голосов
0
ответов
132 показа

Обосновать принадлежность класса задач проверки на связность графа классу NP. Оценить сложность проверки входного слова в худшем случае.
0
голосов
0
ответов
150 показов

Построить схему Нормального Алгорифма Маркова, применимую ко всем словам tx1...xn (t - разделитель, помечающий начало слова) в алфавите {a, b} и перев ...
0
голосов
0
ответов
170 показов

Задача 1:С помощью алгоритма минимизации ДКА докажите, что ДКА КМП A_{w} для любого слова w ∈ T^{∗} является минимальным полным ДКА для языка Suff(w) ...
1
голос
1
ответ
280 показов

Опишите классы Майхилла-Нероуда для языка L={w|w=w^R} над алфавитом T={a,b}.Примечание: необходимо указать множества, на которые разбивается T^*, пока ...
0
голосов
0
ответов
293 показа

Как решить данную задачу за один проход или не более чем за O(n)? Может быть с созданием предварительно какой-то структуры? Задача. Дана последователь ...
0
голосов
0
ответов
206 показов

Докажите рекурсивную перечислимость следующего множества:$$A = \{x |\ \varphi_x\ \text{принимает хотя бы одно значение, являющееся степенью числа 2}\} ...

12345 ... 14следующий »

на странице153050
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru