Informatyka

Pytania i odpowiedzi dla studentów, naukowców i praktyków informatyki

2
Uczciwe cięcie ciasta, gdy gracze dołączają późno
Zwykłe stwierdzenie o uczciwym problemie cięcia ciasta zakłada, że ​​wszyscy gracze otrzymują swój udział w tym samym czasie. Jednak w wielu przypadkach gracze przybywają stopniowo. Na przykład, możemy podzielić ciasto na n graczy, ale wtedy pojawia się nowy gracz i chce się podzielić.nnnnnn Zazwyczaj podział sprawiedliwego ciasta wymaga dużego wysiłku …
6
Czy maszyna Turinga zdecydować języka
Niech Czy istnieje maszyna Turinga R, która decyduje (nie mam na myśli rozpoznać) język L ∅ ?L∅={⟨M⟩ ∣ M. jest maszyną Turinga i L ( M) = ∅ } .L∅={⟨M⟩∣M is a Turing Machine and L(M)=∅}.L_\emptyset = \{\langle M\rangle \mid M \text{ is a Turing Machine and }L(M)=\emptyset\}.L.∅L∅L_\emptyset Wydaje się, …
1
Podejście „CPS” wyrządziło wielką szkodę wydajności w SML / NJ; uzasadnienie pożądane
W komentarzu do Nauka F #: Jakie książki w innych językach programowania można przetłumaczyć na F #, aby nauczyć się funkcjonalnych koncepcji? Makarius stwierdził: Zauważ, że podejście „CPS” wyrządziło wielką szkodę wydajności w SML / NJ. Jego model oceny fizycznej narusza zbyt wiele założeń wbudowanych w sprzęt. Jeśli weźmiesz duże …
1
Jaki algorytm obliczy maksymalne wybory z dwóch zestawów?
Biorąc pod uwagę dwa wektory liczb całkowitych o możliwie nierównych długościach, jak mogę określić maksymalny możliwy wynik z akumulacji wybierając maksimum między odpowiadającymi parami liczb między dwoma wektorami z dodatkowymi zerami wstawionymi do krótszego wektora, aby zrekompensować różnicę wielkości? Na przykład rozważ następujące dwa wektory jako dane wejściowe: [8 1 …
1
Nie można przekonwertować z NFA na DFA
Mam prosty problem z utworzeniem DFA, który akceptuje wszystkie dane wejściowe zaczynające się od podwójnych liter (aa, bb) lub kończące się na podwójnych literach (aa, bb), biorąc pod uwagę, że jest zestawem alfabetu dany język.Σ={a,b}Σ={a,b}\Sigma =\{a, b\} Próbowałem rozwiązać to w sposób okrężny: Generowanie wyrażenia regularnego Tworzenie odpowiedniego NFA Wykorzystanie …
1
Niezależny zestaw na sześciennych grafach bez trójkątów
Wiem, że maksymalny niezależny zestaw na sześciennych grafach bez trójkątów jest NP-zupełny. Czy nadal jest NP-kompletny, jeśli potrzebujemy, aby niezależny zestaw miał dokładnie taką samą wielkość ?| V.| / 2|V.|/2)|V|/2 Zasadniczo YES wystąpienie problemu z niezależnym zestawem na szesnastkowym grafie bez trójkątów musi mieć dokładnie węzły. ŻADNA instancja nie ma …
1
Analiza asymptotyczna dla dwóch zmiennych?
Jak definiuje się analizę asymptotyczną (duża o, mała o, duża theta, duża theta itp.) Dla funkcji z wieloma zmiennymi? Wiem, że artykuł w Wikipedii zawiera sekcję, ale wykorzystuje wiele notacji matematycznych, których nie znam. Znalazłem również następujący artykuł: http://people.cis.ksu.edu/~rhowell/asymptotic.pdf Jednak artykuł jest bardzo długi i zawiera pełną analizę analizy asymptotycznej, …
1
Ukierunkowane znalezienie związku
Rozważ skierowany wykres na którym można dynamicznie dodawać krawędzie i tworzyć określone zapytania.GGG Przykład: las rozłączny Rozważ następujący zestaw zapytań: arrow(u, v) equiv(u, v) find(u) pierwszy dodaje strzałkę do wykresu, drugi decyduje, czy u ↔ ∗ v , ostatni znajduje kanoniczny reprezentant klasy równoważności ↔ ∗ , tj. r ( …
3
Książki z algorytmami na różne tematy
Chcesz poprawić ten post? Podaj szczegółowe odpowiedzi na to pytanie, w tym cytaty i wyjaśnienie, dlaczego Twoja odpowiedź jest poprawna. Odpowiedzi bez wystarczającej ilości szczegółów mogą być edytowane lub usuwane. Zadanie polegało na zbudowaniu biblioteki książek na temat algorytmów dla naszej małej firmy (około 15 osób). Budżet wynosi ponad 5 …
2
Uprość złożoność n multichoose k
Mam algorytm rekurencyjny o złożoności czasowej równoważnej do wybierania elementów k z powtórzeniem i zastanawiałem się, czy mogę uzyskać bardziej uproszczone wyrażenie big-O. W moim przypadku może być większe niż i rosną one niezależnie.kkknnn W szczególności oczekiwałbym wyraźnego wyrażenia wykładniczego. Najlepsze, jakie do tej pory mogłem znaleźć, to oparte na …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.