Я читаю о проблеме максимального потока здесь . Я не мог понять интуицию, стоящую за остаточным графиком. Почему мы учитываем задние края при расчете потока? Может ли кто-нибудь помочь мне понять концепцию остаточного графа? Как меняется алгоритм в неориентированных...
Хорошо известно, что 2-SAT находится в P. Тем не менее, представляется довольно интересным, что подсчет количества решений для данной формулы 2-SAT, то есть # 2-SAT, является # P-сложным. То есть у нас есть пример проблемы, решение которой легко, а подсчет сложно. Но рассмотрим произвольную...
Выполняя второе кодовое ката (которое просит вас реализовать алгоритм двоичного поиска пять раз, каждый раз с другим методом), я придумал немного другое решение, которое работает следующим образом: Если у меня есть отсортированный массив длины 100, и я вижу, что его начальное поле содержит число...
Я только что прочитал Можно ли считать этот алгоритм алгоритмом бинарного поиска? и вспомнил, что несколько лет назад я написал индексатор / поиск файлов журнала, чтобы найти записи журнала в больших текстовых файлах по окну даты / времени. Делая это, я решил попробовать поиск по интерполяции (я не...
Я читаю статью, и в своем описании сложности времени говорится, что сложность времени равна .О~( 22 н)O~(22n)\tilde{O}(2^{2n}) Я искал в интернете и википедии, но я не могу найти, что означает эта тильда в нотации big-O / Landau. В самой газете я также не нашел никаких подсказок по этому поводу....
Я знаком с операционной семантикой (как маленькой, так и большой) для определения языков программирования. Я также заинтересован в изучении денотационной семантики, но не уверен, стоит ли это усилий. Буду ли я изучать один и тот же материал с другой точки зрения, или есть понимание, которое я могу...
У меня есть алгоритмическая проблема. Дан массив (или набор) из неотрицательных целых чисел. Найти максимальное множество из , что для всех ,,н STTTnNnSSSTTTa∈Sa∈Sa\in Sa⩾|S|a⩾|S|a\geqslant |S| Например: Если TTT = [1, 3, 4, 1, 3, 6], то SSS может быть [3, 3, 6] или [3, 4, 6] или [4, 3, 6]. В = [7,...
В разделе 15.3 « Элементы динамического программирования» Кормена и др. « Введение в алгоритмы» объясняется запоминание следующим образом: Записанный рекурсивный алгоритм поддерживает запись в таблице для решения каждой подзадачи. Каждая запись таблицы изначально содержит специальное значение,...
Доказано ли, что квантовые вычисления не лучше в решении полных задач NP, чем классические вычисления, или в это просто
Некоторые из работ Конора МакБрайда, Diff , Dissect , связывают производную типов данных с их «типом контекстов с одной дырой». То есть, если вы берете производную от типа, который у вас остался, с типом данных, который показывает вам, как тип данных выглядит изнутри в любой заданной точке. Так,...
Закрыто . Этот вопрос основан на мнении . В настоящее время он не принимает ответы. Хотите улучшить этот вопрос? Обновите вопрос, чтобы ответить на него фактами и цитатами, отредактировав этот пост . Закрыто 2 года назад . Как правило, программисты, которые являются математиками или имеют...
Я имею в виду этот [забавный] вопрос. Почему недетерминированный конечный автомат называется недетерминированным, в то время как мы определяем переходы для входных данных. Что ж, несмотря на то, что существуют множественные и эпсилон- переходы, они определены, что означает, что машина является...
Я читал эту книгу для своего класса рандомизированных алгоритмов. В этой конкретной книге есть целый раздел, посвященный поиску медианы массива с использованием случайного выбора, что приводит к более эффективному алгоритму. Теперь я хотел бы знать, есть ли какие-либо практические применения этого...
Я программист с автоматом, но не с логикой. Я читал в газетах, что они очень тесно связаны. Детерминированные конечные автоматы (DFA), древовидные автоматы и автоматы видимого нажатия - все они связаны с монадической логикой второго порядка (MSO). Хотя, я понимаю, что автоматы и люди (в статьях)...
Я знаком с идеей базового исключения хвостовой рекурсии, когда функции, которые возвращают прямой результат вызова для себя, могут быть переписаны как итерационные циклы. foo(...): # ... return foo(...) Я также понимаю, что в особом случае функция все еще может быть переписана, если рекурсивный...
Существуют ли методы решения функциональных уравнений для неизвестных функций в лямбда-исчислении? Предположим, у меня есть функция тождества, определенная как таковая: Ix=xIx=xI x = x (то есть, записывая уравнение для ожидаемого поведения этой функции) , и теперь я хочу , чтобы решить эту проблему...
Допустим, мы работаем с системой, которая имеет 40 бит физического адреса. Общее физическое адресное пространство (при условии адресной памяти в байтах ) составляет байтов или 1 ТиБ. И если виртуальные адреса имеют длину 48 бит, это означает, что виртуальной памяти доступно больше адресов, чем мест...
Если я правильно понимаю, алгоритм, который вычисляет значение действительной функции имеет вычислительную сложность если выполняется следующее: Когда мы вычисляем с точностью требуется порядка шагов ,fffO(g(n))O(g(n))O(g(n))fffδδ\deltag(n)g(n)g(n) Однако что если у нас есть алгоритм, который...
Я читал о стековых языках программирования, таких как FORTH и Cat , и кажется, что, учитывая их природу, они могут выполнять только одно действие за раз, независимо от их парадигмы (FORTH обязателен, тогда как Cat функционален). Императивный язык изменил бы стек, а чисто функциональный язык, такой...
Могу ли я доказать следующие утверждения, используя доступные автоматические средства проверки теорем? .( а + б )2= а2+ б2+ 2 а б(a+б)2знак равноa2+б2+2aб(a+b)^2=a^2+b^2+2ab Если , а затем 11 | 7 - 5 б .11 ∣ 2 а - 3 б11|2a-3б 11 \mid 2a-3b11 ∣ 7 а - 5 б11|7a-5б 11 \mid 7a-5b Если , то x = - b ±...