0
голосов
0
ответов
32 показа

Рассмотрим язык {1^n| n=k^2, k натуральное} над алфавитом {0;1}Опишите машину тьюринга, которая за полиномиальное время распознает язык.
0
голосов
1
ответ
140 показов

Добрый день!Треугольником в неор.графе называется тройка вершин, попарно соединенных дугами. Склеиванием треуг. называется операция замены вершин треу ...
0
голосов
0
ответов
108 показов

К набору из n различных натуральных чисел применяется такой алгоритм на каждом шаге цикла берутся два числа и если они взаимно просты, то из большого ...
0
голосов
0
ответов
70 показов

Добрый день!Нигде не могу найти информацию об алгоритме построения КС-грамматики по регулярному языку.Не могли бы знающие помочь ссылками или любой др ...
0
голосов
0
ответов
98 показов

Имеется таблица размера $%10^9 \times 10^9$%, в j-м элементе i-й строки которой стоит минимальное натуральное число, такое, что оно не встречается в j ...
0
голосов
0
ответов
72 показа

Рассмотрим следующую задачу:FILLAPIX : Дана таблица размера m × n, в которой каждая клетка либо пуста, либосодержит число от 0 до 9. Выяснить, можно л ...
0
голосов
0
ответов
105 показов

Все слова языка L принимаются машиной Тьюринга M за полиномиальное время, и ни-какие другие слова машиной M не принимаются (но, возможно, и не отверга ...
0
голосов
0
ответов
90 показов

Рассмотрим сложностной класс coNP = {L ∣ L ∈ NP}. Докажите, что если NP ≠ coNP, тоP ≠ NP
0
голосов
0
ответов
92 показа

Существует ли разрешимое множество, не принадлежащее классу P (разрешимых за по-линомиальное время языков)?
0
голосов
1
ответ
114 показов

Необходимо составить программу для машины Тьюринга, вычисляющую функцию $%2^{N} $%, где $%N$% задано в троичной системе счисления.Смущает очень троичн ...
0
голосов
0
ответов
78 показов

Задача: Пусть для положительной функции $%f(n)$% выполнено $%f(n)=(3+o(1))^n+\Theta(n^{100})$%. Верно ли в общем случае, что $%\log{f(n)}=\Theta(n)$%? ...
0
голосов
0
ответов
74 показа

Задался такой задачей:Если есть n чисел и нужно выбрать k, так, чтобы просуммировав k чисел, сумма цифр данного числа была максимальной. Реально ли эт ...
0
голосов
0
ответов
60 показов

Каждый из игроков играет в определённую игру против компьютера. За победу над компьютером игроку начисляет 1 балл. За проигрыш - ничего не начисляется ...
5
голосов
1
ответ
335 показов

Детектив Ниро Вульф расследует преступление. В делезамешаны 80 человек, среди которых один — преступник, еще один —свидетель преступления (но неизвест ...
0
голосов
0
ответов
117 показов

Имеется набор стандартного домино: 28 костяшек с двумя значениями от 0 до 6. Из этого набора наугад выбирается N костяшек. Нужно рассчитать максимальн ...
на странице153050
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru