Я думаю, что я довольно озадачен тем, что называется исчислением и тем, что называется языком программирования. Я склонен думать и, возможно, мне сказали, что исчисление - это формальная система рассуждений об эквивалентности программ. Программы имеют операционную семантику, указанную машиной,...
В литературе достаточно ясно, что ОЗУ с удельной стоимостью с примитивным умножением являются необоснованными, поскольку они не может быть смоделировано машинами Тьюринга за полиномиальное время может решить PSPACE-полные задачи за полиномиальное время Тем не менее, все ссылки, которые я могу найти...
Таким образом, сортировка слиянием - это алгоритм «разделяй и властвуй». Пока я смотрел на приведенную выше диаграмму, я думал, можно ли вообще обойти все этапы разделения. Если вы перебираете исходный массив при переходе на два, вы можете получить элементы по индексам i и i + 1 и поместить их в...
Закрыто. Этот вопрос не по теме . В настоящее время он не принимает ответы. Хотите улучшить этот вопрос? Обновите вопрос так это на тему для Computer Science Stack Exchange. Закрыто 2 года назад . Типы AFAIU могут быть Setэлементами, чьи элементы являются программами, или propositionэлементами,...
Я верю, что это правда, но не смог получить формальное доказательство ни того, ни другого. Но правда ли, что любое минимальное остовное дерево достижимо с помощью алгоритма Крускала? Точно так же это верно для алгоритма Прима? РЕДАКТИРОВАТЬ: Чтобы быть более точным, я хочу знать, если дан MST для...
Проблема Нет простого способа получить перестановку с помощью регулярного выражения. Перестановка: Получение слово ( «ААБК») в другом порядке, без изменения числа или рода писем.w=x1…xnw=x1…xnw=x_1…x_n Regex: Регулярное выражение. Для подтверждения: «Перестановки регулярных выражений без...
Я наткнулся на этот рисунок, который показывает, что контекстно-свободные и регулярные языки являются (правильными) подмножествами эффективных задач (предположительно ). Я прекрасно понимаю, что эффективные проблемы являются подмножеством всех разрешимых проблем, потому что мы можем их решить, но...
Windows NT использовала двухточечный протокол, в котором клиент может «безопасно» общаться с сервером, используя потоковый шифр для шифрования массива сообщений с некоторым ключом . Сервер также шифрует свой ответ тем же ключом . Но как он узнает об этом ключе?kkkkkk В более общем плане : если...
Направленный граф называется унипатическим, если для любых двух вершин и в графе существует не более одного простого пути из в .uuuvvvG=(V,E)G=(V,E)G=(V,E)uuuvvv Предположим, мне дан унипатический граф такой, что каждое ребро имеет положительный или отрицательный вес, но не содержит циклов...
Как пароль, который мы вводим (для подключения к беспроводной сети), шифрует данные в беспроводной сети? Из-за моего чтения я не уверен, совпадает ли пароль, который мы вводим, с парольной фразой. Если это правильно, то как парольная фраза может генерировать четыре ключа WEP? Я понимаю, как четыре...
Алгоритм Кодда преобразует выражение в корреляционном исчислении в реляционную алгебру. Есть ли стандартная реализация алгоритма? Этот алгоритм используется где-нибудь? (Похоже, что отрасли нужны только SQL и варианты, я не уверен насчет теоретиков баз данных в академических кругах.) Какова...
Другими словами, какие преимущества имеет гибридная многопоточность по сравнению с 1: 1 (только для ядра) и N: 1 (только для пользователя)? Это продолжение к тому, В чем разница между потоками уровня пользователя и потоками уровня...
Существуют ли неразрешимые языки, так что их язык объединения / пересечения / сцепления является разрешимым? Какова физическая интерпретация такого примера, потому что в целом неразрешимые языки не закрыты под этими операциями? Что мы можем сказать о закрытии клини? У нас тоже есть примеры для...
Что означает класс сложности ? Я знаю , что ⊕ P есть класс сложности , который содержит языки А , для которых существует многочлен времени недетерминирован машина Тьюринга M такая , что х ∈ тогда и только тогда число принимающих состояний машины М на входе х нечетно.⊕ P⊕ P⊕P⊕P\oplus P^{\oplus P}⊕...
Учитывая распределение степеней, как быстро мы можем построить график, который следует заданному распределению степеней? Ссылка или эскиз алгоритма были бы хорошими. Алгоритм должен сообщать «нет», если граф не может быть построен, и любой один пример, если можно построить несколько...
Я хочу преобразовать введенное пользователем регулярное выражение в NFA, чтобы потом можно было запускать NFA для строки для сопоставления. Какой минимальный компьютер можно использовать для разбора регулярных выражений? Я предполагаю, что это должен быть автомат с принудительной передачей, потому...
Следующее сомнение, что я наткнулся при выполнении домашнего задания OS - однако, это кажется более концепция на основе, чем вопрос кодирования простого, поэтому ИМХО я не думаю, что домашние задания теги подходят для этого. В чистых схемах требуют поискового вызова для нескольких процессов,...
Пусть регулярный, регулярный, не регулярный. Покажите, что не является регулярным, или приведите контрпример.L1L1L_1L1∩L2L1∩L2L_1 \cap L_2L2L2L_2L1∪L2L1∪L2L_1 \cup L_2 Я попробовал это: Посмотрите на . Это регулярно. Для этого я могу построить конечный автомат: регулярный, регулярный, поэтому...
Определение: уменьшение Карпа Язык является приводимым по Карпу к языку если существует вычислимая функция за полиномиальное время такая, что для каждого , тогда и только тогда , когда .B f : { 0 , 1 } ∗ → { 0 , 1 } ∗ x x ∈ A f ( x ) ∈...
Вопрос был задан при переполнении стека ( здесь ): Принимая во внимание целое число , распечатать все возможные комбинации целочисленных значений и , которые решают уравнение .NNND A 2 + B 2 + C 2 + D 2 = NA , B , CA,B,CA,B,CDDDA2+ B2+ C2+ D2= NA2+B2+C2+D2=NA^2+B^2+C^2+D^2 = N Этот вопрос, конечно,...