Вопросы, которые помогают развить интуицию в отношении формальных или сложных концепций.
Я считаю, что у меня есть разумное представление о сложностях, таких как , Θ ( n ) и Θ ( n 2 )O(1)O(1)\mathcal{O}(1)Θ(n)Θ(n)\Theta(n)Θ(n2)Θ(n2)\Theta(n^2) . С точки зрения списка, - это постоянный поиск, поэтому он просто получает заголовок списка. Θ ( n ) - это место, где я прошёл бы весь список,...
Я понимаю доказательство неразрешимости проблемы остановки (приведенное, например, в учебнике Пападимитриу), основанное на диагонализации. Хотя доказательство является убедительным (я понимаю каждый его шаг), оно не является для меня интуитивным в том смысле, что я не понимаю, как кто-то может его...
Этот вопрос был вдохновлен комментарием к StackOverflow . Помимо знания NP-полных проблем книги Гэри Джонсона и многих других; Есть ли эмпирическое правило, чтобы узнать, выглядит ли проблема как NP-полная? Я не ищу что-то строгое, но что-то, что работает в большинстве случаев. Конечно, каждый раз,...
Я аспирант, изучающий курс теории вычислений, и у меня возникли серьезные проблемы с созданием контента, как только меня об этом попросят. Я могу следовать учебнику (Введение в теорию вычислений Майкла Сипсера) и лекциям; однако когда меня просят что-то доказать или придумать формальное описание...
Иногда легко определить временную сложность алгоритма, если внимательно его изучить. Алгоритмы с двумя вложенными циклами , очевидно, N 2 . Алгоритмы , которые исследуют все возможные комбинации N групп из двух значений, очевидно , 2 N .NNNN2N2N^2NNN2N2N2^N Однако я не знаю, как «определить»...
Я думал, что правильно понял зависимую типизацию (DT), но ответ на этот вопрос: /cstheory/30651/why-was-there-a-need-for-martin-l%C3% Теория типа «создать творческий интуиционизм» заставила меня думать иначе. После прочтения DT и попыток понять, что они из себя представляют, я пытаюсь задаться...
Ниже предположим, что мы работаем с машиной Тьюринга с бесконечной лентой. Объясняя кому-то понятие временной сложности и почему оно измеряется относительно входного размера экземпляра, я наткнулся на следующее утверждение: [..] Например, естественно, что вам нужно больше шагов для умножения двух...
На работе мне было поручено вывести некоторую информацию о типах динамического языка. Я переписываю последовательности операторов во вложенные letвыражения, например так: return x; Z => x var x; Z => let x = undefined in Z x = y; Z => let x = y in Z if x then T else F; Z => if x then {...
Я получил доказательство перехода от перечислителя к машине Тьюринга (продолжайте запускать перечислитель и посмотрите, соответствует ли он вводу), но я не вижу, как работает другой способ. Согласно моим заметкам и книге (Введение в теорию вычислений - Sipser), чтобы получить перечислитель Тьюринга...
Учитывая язык L={anbncn}L={anbncn} L= \{a^n b^n c^n\} , как я могу прямо сказать, не глядя на правила производства, что этот язык не является регулярным? Я мог бы использовать лемму прокачки, но некоторые парни говорят, просто глядя на грамматику, что это не совсем так. Как это...
Я прочитал много документов о свертке при обработке изображений, и большинство из них говорят о его формуле, некоторых дополнительных параметрах. Никто не объясняет интуицию и реальный смысл создания свертки на изображении. Например, интуиция вывода на графике делает его более линейным, например. Я...