0
голосов
0
ответов
32 показа
Язвк над алфавитом {0;1}
Рассмотрим язык {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 показов
ММО 2017 второй день алгоритмы
Детектив Ниро Вульф расследует преступление. В делезамешаны 80 человек, среди которых один — преступник, еще один —свидетель преступления (но неизвест ...
0
голосов
0
ответов
117 показов
Домино - максимальное количество "концов"
Имеется набор стандартного домино: 28 костяшек с двумя значениями от 0 до 6. Из этого набора наугад выбирается N костяшек. Нужно рассчитать максимальн ...
124 вопроса
Связанные метки
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.