Informatyka

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

3
Maksymalny krąg zamykający danego promienia
Próbuję znaleźć podejście do następującego problemu: Biorąc pod uwagę zestaw punktu i promień , znajdź punkt środkowy okręgu, tak aby okrąg zawierał maksymalną liczbę punktów ze zbioru. Czas działania powinien wynosić .SSSrrrO(n2)O(n2)O(n^2) Na początku wydawało się, że jest to coś podobnego do najmniejszego otaczającego problemu, które można łatwo rozwiązać w …
1
Zapisywanie przy inicjalizacji tablicy
Niedawno przeczytałem, że można mieć tablice, które nie muszą być inicjowane, tzn. Można z nich korzystać bez konieczności poświęcania czasu na ustawianie wartości domyślnej dla każdego elementu. tzn. możesz zacząć używać tablicy tak, jakby została ona zainicjowana wartością domyślną, bez konieczności jej inicjowania. (Przepraszam, nie pamiętam, gdzie to przeczytałem). Na …
1
Problem decyzyjny taki, że dowolny algorytm dopuszcza wykładniczo szybszy algorytm
W Hromkovič's Algorytmics for Hard Problems (2nd edition) znajduje się takie twierdzenie (2.3.3.3, strona 117): Istnieje (rozstrzygalny) problem decyzyjny taki że dla każdego algorytmu A, który rozwiązuje P, istnieje inny algorytm A ', który również rozwiązuje P i dodatkowo spełniaP.PPZAAAP.PPA′A′A'PPP ∀∞n∈N.TimeA′(n)=log2TimeA(n)∀∞n∈N.TimeA′(n)=log2⁡TimeA(n)\qquad \forall^\infty n \in \mathbb{N}. \mathrm{Time}_{A'}(n) = \log_2 \mathrm{Time}_A(n) jest …
3
Ray Tracing a renderowanie obiektowe?
Kursy grafiki wstępnej zwykle mają projekt, w którym prosi się o zbudowanie ray tracera do renderowania sceny. Wielu studentów grafiki rozpoczynających naukę w grad grad mówi, że chcą pracować nad ray tracingiem. A jednak wydaje się, że ray tracing jest martwym polem w miejscach takich jak SIGGRAPH itp. Czy ray …
19 graphics 
2
Ile krawędzi może mieć wykres unipatyczny?
Wykres unipatyczny jest wykresem ukierunkowanym, tak że istnieje co najwyżej jedna prosta ścieżka z jednego wierzchołka do dowolnego innego wierzchołka. Wykresy unipatyczne mogą mieć cykle. Na przykład podwójnie połączona lista (nie okrągła!) Jest grafem unipatycznym; jeśli lista zawiera elementów, wykres ma cykli o długości 2, w sumie .n - 1 …
1
Łatwa redukcja z 3SAT do problemu ścieżki Hamiltonian
W książce Sipsera „Wprowadzenie do teorii obliczeń” na stronie 286 zmniejszono z 3SAT do problemu ścieżki Hamiltona. Czy istnieje prostsza redukcja? Mówiąc prościej, mam na myśli redukcję, która byłaby łatwiejsza do zrozumienia (dla studentów). Czy istnieje redukcja wykorzystująca liniową liczbę zmiennych? Redukcja w Sipserze wykorzystuje zmienne , gdzie jest liczbą …
3
Czy ten język jest zdefiniowany przy użyciu podwójnych liczb pierwszych regularnych?
Pozwolić L={an∣∃p≥n p, p+2 are prime}.L={an∣∃p≥n p, p+2 are prime}.\qquad L = \{a^n \mid \exists_{p \geq n}\ p\,,\ p+2 \text{ are prime}\}. Czy regularny?LLL To pytanie wyglądało podejrzanie na pierwszy rzut oka i zdałem sobie sprawę, że jest związane z hipotezą o podwójnej liczbie pierwszych . Mój problem polega na …
3
Funkcja ML typu „a ->” b
Nasz profesor poprosił nas o przemyślenie funkcji w OCaml, która ma ten typ 'a -> 'b tj. funkcja jednego argumentu, który może być czymkolwiek, i który może zwrócić coś innego. Myślałem o użyciu raisefunkcji, która ignoruje jej argument: let f x = raise Exit Ale profesor powiedział, że istnieje rozwiązanie, …
4
Czy harmonogramowanie kooperacyjne zawiesza procesy podczas wykonywania operacji we / wy?
Wiele odniesień do systemów operacyjnych mówi, że w przypadku wielozadaniowości kooperacyjnej (w przeciwieństwie do zapobiegawczej) proces utrzymuje procesor do momentu, aż jawnie się dobrowolnie zawiesi. Jeśli uruchomiony proces wykonuje żądanie we / wy, którego nie można natychmiast zaspokoić (np. Żąda naciśnięcia klawisza, który nie jest jeszcze dostępny), to czy program …
4
Strategie utknięcia w zrozumieniu TCS
Jestem studentem kończącym kurs teorii teorii i mam poważne problemy z tworzeniem treści, gdy tylko o to poproszę. Potrafię śledzić podręcznik (Wstęp do teorii obliczeń Michaela Sipsera) i wykłady; jednak kiedy poproszono mnie o udowodnienie czegoś lub sformułowanie formalnego opisu konkretnej bazy TM, po prostu dusiłem się. Co mogę zrobić …
2
Algorytmy sprawdzania typu
Zaczynam osobiste badanie bibliograficzne algorytmów sprawdzania typu i chcę uzyskać wskazówki. Jakie są najczęściej stosowane algorytmy sprawdzania typu, strategie i techniki ogólne? Szczególnie interesują mnie złożone algorytmy sprawdzania typu, które zostały zaimplementowane w powszechnie znanych, silnie statycznych językach, takich jak na przykład C ++, Java 5+, Scala lub inne. IE, …
2
Czy operacja „różnica” dodaje wyrazistości do języka zapytań, który już zawiera „dołącz”?
Operator różnicy zbiorów (np. EXCEPTW niektórych wariantach SQL) jest jednym z wielu podstawowych operatorów algebry relacyjnej. Istnieją jednak bazy danych, które nie obsługują bezpośrednio operatora różnicy setów, ale które obsługują LEFT JOIN(rodzaj połączenia zewnętrznego), aw praktyce można tego użyć zamiast operacji ustawiania różnicy, aby osiągnąć ten sam efekt. Czy to …
5
Rozróżnienie przypadków w programowaniu dynamicznym: potrzebny przykład!
Od jakiegoś czasu pracuję nad programowaniem dynamicznym. Kanonicznym sposobem oceny dynamicznej rekurencji programowania jest utworzenie tabeli wszystkich niezbędnych wartości i wypełnienie jej wiersz po wierszu. Zobacz na przykład Cormen, Leiserson i in .: „Wprowadzenie do algorytmów” . Skupiam się na opartym na tabeli schemacie obliczeń w dwóch wymiarach (wypełnianie wiersz …
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.