Informatyka

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

4
Najbardziej wydajny algorytm do drukowania 1-100 przy użyciu danego generatora liczb losowych
Dostajemy generator liczb losowych, RandNum50który generuje losową liczbę całkowitą równomiernie w zakresie 1–50. Możemy używać tylko tego generatora liczb losowych do generowania i drukowania wszystkich liczb całkowitych od 1 do 100 w losowej kolejności. Każda liczba musi przyjść dokładnie raz, a prawdopodobieństwo wystąpienia dowolnej liczby w dowolnym miejscu musi być …
2
-algebrze na wejściu algorytmu
Chcę sprecyzować, co to znaczy podać algebrę jako dane wejściowe do algorytmu i nie znalazłem zbyt wiele literatury na ten temat. Najpierw chciałbym zapytać, czy możesz polecić książkę lub artykuł, który porusza temat analizy złożoności algebr nad polami i jasno określa problem decyzyjny . Po kilku kopaniach znalazłem coś i …
1
Przetwarzaj wstępnie tablicę do zliczania elementu w wycinku (redukcja do RMQ?)
Biorąc pod uwagę tablicę liczb naturalnych , gdzie jest stałą, chcę odpowiedzieć na zapytania o formie: „ile razy pojawia się w tablicy między indeksami i ”?a1,…,ana1,…,ana_1,\ldots,a_n≤k≤k\leq kkkkO(1)O(1)O(1)mmmiiijjj Tablica powinna być wstępnie przetworzona w czasie liniowym. W szczególności chciałbym wiedzieć, czy nastąpiło ograniczenie zapytania minimalnego zakresu. Jest to równoważne z RMQ …
2
Twierdzenie główne nie dotyczy?
Biorąc pod uwagę następujące równanie rekurencyjne T.( n ) = 2 T.( n2)) +nlognT(n)=2T(n2)+nlog⁡n T(n) = 2T\left(\frac{n}{2}\right)+n\log nchcemy zastosować twierdzenie Master i zauważyć, że nlog2)( 2 )= n .nlog2⁡(2)=n. n^{\log_2(2)} = n. Teraz sprawdzamy dwa pierwsze przypadki dla ε > 0ε>0\varepsilon > 0 , czyli czy n logn ∈ O …
1
Przykład poprawności i kompletności wnioskowania
Czy następujący przykład jest prawidłowy, czy algorytm wnioskowania jest prawidłowy i kompletny ? Załóżmy, że mamy igły a, b, c w stogu siana, a także algorytm wnioskowania zaprojektowany do wyszukiwania igieł. dźwięk - uzyskiwane są tylko igły a, b i c. kompletna - otrzymano igły a, b i c. Można …
11 logic 
1
podzbiory nieskończonych zbiorów rekurencyjnych
Ostatnie pytanie egzaminacyjne brzmiało następująco: jest nieskończonym zestawem rekurencyjnie wyliczalnym. Wykazać, że A ma nieskończony rekurencyjny podzbiór.ZAAAZAAA Niech jest nieskończony rekurencyjne podzbiór A . Czy C musi mieć podzbiór, którego nie można wyliczyć rekurencyjnie?doCCZAAAdoCC Odpowiedziałem już 1.. W odniesieniu do 2. odpowiedziałem twierdząco i twierdziłem, co następuje. Załóżmy, że wszystkie …
2
Mieszanie za pomocą drzew wyszukiwania zamiast list
Walczę z haszowaniem i materiałem do wyszukiwania binarnego. Przeczytałem, że zamiast używać list do przechowywania wpisów z tymi samymi wartościami skrótu, możliwe jest również użycie drzew wyszukiwania binarnego. I staram się zrozumieć, jaki jest najgorszy i średni przypadek wykonania operacji insert, find i delete jest wart. średni przypadek. Czy poprawiają …
1
Wnioskowanie typu na podstawie ograniczeń z danymi algebraicznymi
Pracuję nad językiem genealogicznym ML opartym na wyrażeniach, więc oczywiście wymaga wnioskowania typu> :) Teraz próbuję rozszerzyć oparte na ograniczeniach rozwiązanie problemu wnioskowania typów, oparte na prostej implementacji w EOPL (Friedman i Wand), ale są to eleganckie algebraiczne typy danych. To, co mam do tej pory, działa płynnie; Jeśli wyrażenie …
2
Jak radzić sobie z tablicami podczas sprawdzania poprawności w stylu Hoare'a
W dyskusji wokół tego pytania Gilles poprawnie wspomina, że ​​każdy dowód poprawności algorytmu wykorzystującego tablice musi udowodnić, że nie ma dostępu do tablicy poza granicami; w zależności od modelu środowiska wykonawczego spowoduje to błąd środowiska wykonawczego lub dostęp do elementów innych niż macierzowe. Jedną z powszechnych technik przeprowadzania takich dowodów …
1
Kolejka priorytetowa z operacjami zmniejszania i zwiększania
Fibonnaci Heap obsługuje następujące operacje: insert(key, data) : dodaje nowy element do struktury danych find-min() : zwraca wskaźnik do elementu z minimalnym kluczem delete-min() : usuwa element z minimalnym kluczem delete(node) : usuwa element wskazany przez node decrease-key(node) : zmniejsza klucz wskazanego elementu node Wszystkie operacje niezwiązane z usuwaniem mają …
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.