Смотрите в конце этого поста некоторые пояснения к определению (ям) автоматов с минимальной кучей. Можно представить себе использование различных структур данных для хранения информации для использования конечными автоматами. Например, автоматы с отложенным запуском хранят информацию в стеке, а...
Это основной вопрос, но я думаю, что совпадает с , поскольку больший член должен доминировать при переходе к бесконечности? Кроме того, это будет отличаться от O (\ min (m, n)) . Это правильно? Я продолжаю видеть это обозначение, особенно при обсуждении алгоритмов графа. Например, вы обычно видите:...
Существует этот стандартный алгоритм поиска самого длинного пути в ненаправленных деревьях с использованием двух поисков в глубину: Запустите DFS из случайной вершины и найдите самую дальнюю из нее; скажи это .vvvv′v′v' Теперь запустите DFS из чтобы найти самую дальнюю вершину. Этот путь является...
На странице Википедии для комбинаторов с фиксированной точкой написан довольно загадочный текст Y комбинатор является примером того, что делает лямбда-исчисление непоследовательным. Поэтому к этому следует относиться с подозрением. Однако комбинатор Y можно считать безопасным, если он определен...
Я сам изучаю Автоматизированное доказательство теорем / SMT-решатели / Помощники по проверке и выкладываю серию вопросов о процессе, начинающемся здесь. Обратите внимание, что эти темы нелегко усваиваются без знания (математической) логики. Если у вас есть проблемы с основными терминами,...
Предположим, что я программист, и у меня есть NP-полная проблема, которую мне нужно решить. Какие методы доступны для решения проблем с NPC? Есть опрос или что-то похожее на эту...
Я столкнулся со странной проблемой при написании интерпретатора, который (должен) подключаться к внешним программам / функциям: функции в «C» и «C ++» не могут перехватывать переменные функции , например, я не могу создать функцию, которая вызывает «printf» с точно такими же аргументами, которые он...
Я видел повсюду переполнение стека, например, здесь , здесь , здесь , здесь , здесь и некоторые другие, которые я не хочу упоминать, что «любая программа, использующая рекурсию, может быть преобразована в программу, использующую только итерацию». Была даже тема с сильным голосованием и ответом с...
В нашей лекции о компьютерных системах мы познакомились с процессором MIPS. Он был (пере) разработан в течение срока действия термина и на самом деле довольно легко понять. Он использует дизайн RISC , то есть его элементарные команды регулярно кодируются, и их всего несколько, чтобы сохранить...
Я видел упомянутое, что системы зависимого типа не являются заразными, но проверяемыми. Мне было интересно, есть ли простое объяснение, почему это так, и есть ли предел «зависимости», где типы могут быть проиндексированы по значениям, ниже какого типа вывод возможен, а выше которого...
Я пытаюсь понять алгоритмы Петерсона и Деккера, которые очень похожи и имеют много симметрий. Я попытался сформулировать алгоритмы на неформальном языке следующим образом: Peterson's: "I want to enter." flag[0]=true; "You can enter next." turn=1; "If you want to enter and...
В этом ответе упоминается Обычный язык может быть распознан конечным автоматом. Для контекстно-свободного языка требуется стек, а для контекстно-зависимого языка требуются два стека (что эквивалентно тому, что для него требуется полная машина Тьюринга) . Я хотел знать относительно правды смелой...
Давайте предположим следующее определение красно-черного дерева: Это двоичное дерево поиска. Каждый узел окрашен в красный или черный цвет. Корень черный. Два узла, соединенные ребром, не могут быть одновременно красными. Здесь должно быть хорошее определение листа NIL, как на вики. Лист NIL...
Я пытаюсь написать проверку орфографии, которая должна работать с довольно большим словарем. Я действительно хочу, чтобы эффективный способ индексирования данных моего словаря использовался с использованием расстояния Дамерау-Левенштейна, чтобы определить, какие слова наиболее близки к слову с...
В «Big O» общие обозначения имеют общие имена (вместо того, чтобы говорить «о некотором постоянном множителе»): O (1) - «Константа» O (log n) является "логарифмическим" O (n) является "линейным" O (n ^ 2) является "квадратичным" O (n * log n) есть ??? Это просто "n log n" или у него есть...
Я был компьютерным ботаником много-много лет. Я могу программировать на нескольких языках и даже могу их создавать. Я сел с приятелем на днях и спросил, как компьютер на самом деле берет электричество и что-то с ним делает, и мы просто не могли понять это, и Google тоже не сильно помог. Я имею в...
В теории вычислимости и сложности (и, возможно, в других областях) сокращения являются повсеместными. Существует много видов, но принцип остается тем же: показать, что одна проблема L1L1L_1 , по крайней мере, так же трудна, как и другая проблема L2L2L_2 путем сопоставления экземпляров из с...
Через несколько недель я собираюсь провести своего рода «день открытых дверей» в моем университете. В течение этого времени мне (вместе с коллегой) дают по два часа целую группу учеников старших классов, а также компьютерную лабораторию, достаточно большую, чтобы вместить их всех, и я должен...
В алгоритмах и сложности мы фокусируемся на асимптотической сложности алгоритмов, то есть количестве ресурсов, которые алгоритм использует, поскольку размер входных данных уходит в бесконечность. На практике необходим алгоритм, который бы работал быстро на конечном (хотя, возможно, очень большом)...
Я пытался объяснить кому-то, что C завершена по Тьюрингу, и понял, что на самом деле не знаю, действительно ли он технически завершен по Тьюрингу. (C как в абстрактной семантике, а не как в реальной реализации.) «Очевидный» ответ (грубо говоря: он может адресовать произвольный объем памяти, поэтому...