Bardzo dobrze znam Dijkstrę i mam konkretne pytanie dotyczące algorytmu. Jeśli mam ogromny wykres, na przykład 3,5 miliarda węzłów (wszystkie dane OpenStreetMap), to oczywiście nie byłbym w stanie mieć wykresu w pamięci, więc wykres jest przechowywany na dysku w bazie danych. Dostępne są...
Załóżmy dwie listy porównywalnych pozycji: u i s. Niech INV (u) będzie liczbą inwersji wu. Szukam wydajnego algorytmu do wstawiania elementów s do u przy minimalnym wzroście INV (u). Zasadniczo chciałbym wstawić obiekty do listy, zachowując ją „tak posortowaną, jak to możliwe”, zachowując...
Czytałem pytanie na Stack Overflow, pytając, czy to NP- twarde, aby wymienić wszystkie proste cykle na wykresie zawierającym określony węzeł i przyszło mi do głowy, że nie mogę wymyślić żadnej istniejącej klasy złożoności, która byłaby odpowiednia dla mówiąc o problemach z formularzem „wymień...
Jestem studentem informatyki na poziomie uniwersyteckim, który ma wielką pasję do studiowania matematyki. Jestem głęboko przekonany, że informatyka lub teoretyczna informatyka jest bezpośrednią gałęzią matematyki i logiki, a także jestem zdania, że stopień informatyki zawsze musi być zorientowany...
Przynajmniej w Javie, jeśli napiszę ten kod: float a = 1000.0F; float b = 0.00004F; float c = a + b + b; float d = b + b + a; boolean e = c == d; wartość byłaby f a l s e . Uważam, że jest to spowodowane faktem, że liczby zmiennoprzecinkowe są bardzo ograniczone w zakresie dokładnego...
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. Często istnieją języki programowania, które...
Czy przeprowadzono badania nad złożonością dowodu rozwiązania problemu P = NP? Jeśli nie, biorąc pod uwagę brak postępów w rozwiązywaniu problemu, czy nie byłoby rozsądne przypuszczać, że jakikolwiek dowód rozwiązujący problem P = NP będzie wymagał wielomianowej liczby...
Mamy siatkę . Mamy zbiór prostokątów na tej siatki, każdy prostokąta może być przedstawiony jako -by- binarna matryca . Chcemy pokryć siatkę tymi prostokątami.N 1 N 2 RN1×N2N1×N2N_1 \times N_2N1N1N_1N2N2N_2RRR Czy wersja decyzyjna tego zestawu obejmuje problem NP-zupełny? Dane wejściowe:...
Powiedziano mi, że użyjemy listy, jeśli wykres jest rzadki, a macierzy, jeśli wykres jest gęsty . Dla mnie to tylko surowa definicja. Nie widzę wiele poza tym. Czy możesz wyjaśnić, kiedy byłby to naturalny wybór? Z góry
Zbiór jest policzalny, jeśli ma bijectję z liczbami naturalnymi, i jest obliczalny (ce), jeśli istnieje algorytm, który wylicza jego elementy. Każdy nieskończony obliczalny zestaw wyliczalny musi być policzalny, ponieważ możemy zbudować bijection z wyliczenia. Czy są jakieś przykłady zbiorów...
Załóżmy, że masz tablicę o rozmiarze zawierającą liczby całkowite od do włącznie, z dokładnie pięcioma powtórzeniami. Muszę zaproponować algorytm, który może znaleźć powtarzające się liczby w czasie . Przez całe życie nie mogę myśleć o niczym. Myślę, że sortowanie w najlepszym razie byłoby ?...
Powiedzmy, że pracujemy z systemem, który ma 40 bitów adresu fizycznego. Całkowita fizyczna przestrzeń adresowa (przy założeniu, że bajtowo-adresowalna pamięć) wynosi bajtów lub 1 TiB. A jeśli adresy wirtualne mają długość 48 bitów, oznacza to, że w pamięci wirtualnej dostępnych jest więcej adresów...
Istnieją relatywistyczne czasoprzestrzenie (np. Czasoprzestrzenie MH; patrz Hogarth 1994), w których linia świata o nieskończonym czasie trwania może być zawarta w przeszłości skończonego obserwatora. Oznacza to, że normalny obserwator może mieć dostęp do nieskończonej liczby kroków...
Mam wrażenie, że dla każdego problemu NP-zupełnego, dla nieskończenie wielu rozmiarów wejściowych , liczba wystąpień tak we wszystkich możliwych wejściach wielkości jest (przynajmniej) wykładnicza w n .nnnnnnnnn Czy to prawda? Czy można to udowodnić (prawdopodobnie tylko przy założeniu, że P.≠...
Ktoś w dyskusji przywołał, że (uważa) może istnieć co najmniej ciągła liczba strategii podejścia do określonego problemu. Specyficznym problemem były strategie handlowe (nie algorytmy, ale strategie), ale myślę, że to nie ma znaczenia dla mojego pytania. To sprawiło, że pomyślałem o liczności...
Zetknąłem się z algorytmem rozwiązywania rzeczywistego problemu i pamiętam klasę, w której wziąłem udział, gdzie zrobiłem coś bardzo podobnego dla niektórych na zadanie domowe. Zasadniczo jest to wykres punktów, a linie są rysowane tak, aby były w równej odległości między dwoma punktami. Tworzy...
napisałem ∑i=1n1i=∑i=1nO(1)=O(n)∑i=1n1i=∑i=1nO(1)=O(n)\qquad \displaystyle \sum\limits_{i=1}^n \frac{1}{i} = \sum\limits_{i=1}^n \cal{O}(1) = \cal{O}(n) ale mój przyjaciel mówi, że to źle. Z ściągawki TCS wiem, że suma nazywa się również HnHnH_n która ma logarytmiczny wzrost w nnn . Więc moja...
Problem z minimalną przepustowością polega na znalezieniu kolejności węzłów wykresu na linii całkowitej, która minimalizuje największą odległość między dowolnymi dwoma sąsiadującymi węzłami. Problem decyzyjny jest NP-zupełny nawet dla drzew binarnych. Wyniki złożoności dla minimalizacji...
Szukałem interesujących i łatwych do stwierdzenia otwartych problemów w zakresie obliczalności (zrozumiałych dla studentów pierwszego roku z zakresu obliczeń), aby podać przykłady otwartych problemów (i oczywiście chcę, aby uczniowie byli w stanie zrozumieć problem bez potrzeby zbyt dużej ilości...
Algorytmy i struktury danych ignorowane przez pamięć podręczną są raczej nową rzeczą, wprowadzoną przez Frigo i in. w algorytmach niepamięci Cache, 1999 . Teza Prokopa z tego samego roku wprowadza także wczesne pomysły. Artykuł Frigo i in. przedstawić niektóre wyniki eksperymentalne pokazujące...