Как доказать, что ожидаемая высота случайно построенного бинарного дерева поиска с узлами составляет ? В CLRS Введение в алгоритмы есть доказательство (глава 12.4), но я его не понимаю.O ( log n )nnnO(logn)O(logn)O(\log...
Я беру курс по вычислительной сложности. Моя проблема в том, что я не понимаю метод релятивизации . К сожалению, во многих учебниках я пытался найти немного интуиции, но пока безуспешно. Буду признателен, если кто-нибудь сможет пролить свет на эту тему, чтобы я смог продолжить сам. Несколько...
Мне очень нужна ваша помощь в доказательстве следующего. Если то . P = N PN T i m e ( n100) ⊆ D Т я м е ( п1000)NTime(n100)⊆DTime(n1000)\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})P = N PP=NP\mathrm{P}=\mathrm{NP} Здесь - это класс всех языков, которые могут быть определены...
Предположим, у меня есть ориентированный граф с весами ребер, взятыми из диапазона где - константа. Если я пытаюсь найти кратчайший путь, используя алгоритм Дейкстры , как я могу изменить алгоритм / структуру данных и повысить сложность времени до ?K O ( | V | + | E | )[1,…,K][1,…,K][1,\dots,...
Существуют ли языки программирования (или логика), которые могут реализовать (или выразить) функцию тогда и только тогда, когда f вычислимые биективные функции?f:N→Nf:N→Nf:\mathbb{N}\to...
Исходя из POV кого-то, кто думает о получении докторской степени в области компьютерных наук. У меня возникают проблемы с выбором того, на чем я буду концентрироваться, когда буду получать докторскую степень. Смотрите также этот вопрос на academia.SE . Поэтому я думаю, что чтение / отслеживание...
Время от времени встречается головокружительный набор символов, используемых в математических и компьютерных работах. Все же многие предполагают базовое знакомство, которое, кажется, редко преподается в одном месте. Я ищу словарь что-то вроде следующего, особенно с точки зрения CS. В нем будут...
максимизировать F( х )при условии A x = bmaximize f(x)subject to Ax=b\text{maximize } f(\mathbf{x}) \quad\text{subject to } \mathbf{Ax} = \mathbf{b} где е( х ) = ∑я = 1N1 + х4я( ∑Nя = 1Икс2я)2-------------⎷,f(x)=∑i=1N1+xi4(∑i=1Nxi2)2,f(\mathbf{x}) =...
Мне нужна помощь в определении потенциальной функции для максимальной кучи, так что извлечение max завершается за время амортизации . Я должен добавить, что у меня нет хорошего понимания потенциального метода.O ( 1 )О(1)O(1) Я знаю, что функция вставки должна «платить» больше, чтобы уменьшить...
В бакалавриате я прошел курс по компиляторам, в котором мы написали компилятор, который компилирует исходные программы на игрушечном Java-подобном языке в игрушечный ассемблер (для которого у нас был переводчик). В проекте мы сделали несколько предположений о целевой машине, тесно связанной с...
Эта страница, посвященная алгоритму Кнута-Мориса-Пратта по сравнению с Бойером-Муром, описывает возможный случай, когда алгоритм Бойера-Мура страдает небольшим пропуском, а KMP может работать лучше. Я ищу хороший пример (текст, шаблон), который может четко продемонстрировать этот...
Что такое анонимные (лямбда) функции? Каково формальное определение анонимной функции в функциональном языке программирования? Проще говоря, когда я программирую на схеме / lisp, я бы сказал, что анонимная (лямбда) функция - это функция, которая не связана с идентификатором. Это все, что вы можете...
Рассмотрим следующую проблему, входной экземпляр которой представляет собой простой граф и натуральное целое число k .гGGКkk Существует ли множество такое, что G - S двудольный и | S | ≤ к ?S⊆ V( G )S⊆V(G)S \subseteq V(G)G - SG−SG - S| S| ≤k|S|≤k|S| \leq k Я хотел бы показать, что эта проблема...
Недавно я наткнулся на статью, описывающую технику синтаксического анализа, упомянутую в заголовке. К сожалению, терминология, использованная в упомянутой статье, немного за пределами моего понимания, поэтому я пытался понять алгоритм построения более интуитивно. Я полагаю, что мне это удалось (...
Машины Тьюринга и неограниченные грамматики - это два разных формализма, которые определяют языки RE. Некоторые языки RE разрешимы, но не все. Мы можем определить разрешимые языки с помощью машин Тьюринга, сказав, что язык разрешимый, если есть язык для языка, который останавливает и принимает все...
Это проблема с практической сессии Польского студенческого соревнования по программированию 2012 года . Хотя я мог найти решения для основного конкурса, я не могу найти решение этой проблемы где-либо. Проблема в том, что: учитывая набор из различных положительных целых чисел, не превышающих ,...
Я изучаю классификацию SVM и сталкиваюсь с проблемой. Я не уверен, что у этой дилеммы есть терминология для этого. Предположим, мы хотели бы классифицировать пациентов по SVM, учитывая образцы здоровых людей (обоих полов) и людей с раком печени (обоих полов). Если мы помечаем выборку здоровых людей...
С точки зрения асимптотического поведения, что считается «эффективным» алгоритмом? Каков стандарт / причина для рисования линии в этой точке? Лично я бы подумал, что все, что я могу наивно назвать «подполиномом», такое, что такое как , будет эффективным, а все, что будет "неэффективным". Однако я...
Я не могу обернуться вокруг того, как работает SR Latch. По-видимому, вы подключаете входную строку от R, а другую от S, и вы должны получить результаты в и .Q ′QQQQ'Q'Q' Однако и R, и S требуют ввода от выхода другого, а выход другого требует ввода от выхода другого. Что первично - курица или...
Я ищу ресурсы для начала работы с анализом программы . Единственная книга, которую я нашел по этой теме, это книга Нильсона и Нильсона . Кроме этого, кажется, что есть только книги по «компиляторам», где «программный анализ» будет главой или чем-то в этом роде. Знают ли люди о каких-либо других...