Informatyka

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

4
Złożoność dowodu dowodu lub dowodu P = NP
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 kroków?
1
Pokrycie siatki prostokątami
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: Collection prostokątów na siatce (rozmiar wejściowy: ) iN 1 N …
9
Jak znaleźć 5 powtarzanych wartości w czasie O (n)?
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 ? Następnie przejście przez tablicę byłoby , …
5
Co sprawia, że ​​język jest „zoptymalizowany” do określonego zadania?
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 specjalizują się w określonych zadaniach. Niektóre języki programowania doskonale sprawdzają się w arytmetyce tablic (takie …
1
Klasy złożoności związane z listowaniem wszystkich rozwiązań?
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ń wszystkie rozwiązania tego problemu”. Klasa NP w …
6
Co dokładnie odróżnia informatykę od matematyki w kontekście teoretycznym?
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 na matematykę. Proszę, popraw mnie jeśli się mylę. Szczerze mówiąc, uważam, że …
2
Skuteczne wstawianie do listy przy minimalnej liczbie inwersji
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 kolejność pierwszej listy. Przykład: u = [4,6,2,9,7] …
3
Znalezienie przykładów języków „antypalindromicznych”
Niech Σ={0,1}Σ={0,1}\Sigma = \{ 0, 1 \} . Język mówi się, że „anty-palindrom” własność jeśli każdy ciąg że jest palindrom, . Ponadto dla każdego łańcucha który nie jest palindromem, lub , ale nie oba (!) (Wyłączne lub).L⊆Σ∗L⊆Σ∗L \subseteq \Sigma^* wwww∉Lw∉Lw\notin Luuuu∈Lu∈Lu\in LReverse(u)∈LReverse(u)∈L\mathrm{Reverse}(u) \in L Rozumiem właściwość anty-palindromową, ale nie mogłem …
4
Algorytm Dijkstry na wielkich wykresach
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ą biblioteki do obliczania najkrótszych ścieżek na takich …
1
Po co rozdzielać leksowanie i parsowanie?
Możliwe jest parsowanie dokumentu za pomocą pojedynczego przejścia z automatu stanów. Jaka jest korzyść z dwóch przejść, tj. posiadanie leksera do konwersji tekstu na tokeny i parsera do testowania reguł produkcyjnych dla tych tokenów? Dlaczego nie mieć pojedynczego przejścia, które stosuje reguły produkcji bezpośrednio do tekstu?
2
Operacja gwiazdy Kleene na pustym języku
W moim podręczniku wspomniano, że: gdzie to pusty język.∅∅∗={ϵ}∅∗={ϵ}\emptyset^*=\{\epsilon\}∅∅\emptyset Wiemy jednak, że , gdzie to dowolny język.L⋅∅=∅L⋅∅=∅L \cdot \emptyset = \emptysetLLL Nie jestem w stanie intuicyjnie zrozumieć tej koncepcji, ponieważ operacja gwiazdy Kleene wskazuje na fakt, że .∅∗=∅0∪∅1∪∅2∪⋯∅∗=∅0∪∅1∪∅2∪⋯\emptyset^*=\emptyset^0 \cup \emptyset^1 \cup \emptyset^2 \cup \cdots Dlaczego więc nie jest równe ?∅∗∅∗\emptyset^*∅∅\emptyset
4
Co oznacza
Co oznacza ?logO(1)nlogO(1)⁡n\log^{O(1)}n Jestem świadomy notacji wielkiej-O, ale ta notacja nie ma dla mnie sensu. Nie mogę też nic na ten temat znaleźć, ponieważ wyszukiwarka nie ma możliwości prawidłowej interpretacji tego. W pewnym kontekście zdanie, w którym znalazłem, brzmi „[...] nazywamy funkcję [wydajną], jeśli używa ona spacji i co najwyżej …
2
przeznaczenie superkomputerów
Ostatniej jesieni wybrałem się na wycieczkę po superkomputerze Blue Waters na University of Illinois. Zapytałem, czy ktoś kiedykolwiek korzystał z całego komputera. Powiedziano mi, że zawsze pracował nad wieloma projektami. To sprawiło, że zastanawiałem się nad przydatnością superkomputerów. Być może Blue Waters jest niezwykły, ponieważ musi się nim dzielić przemysł …
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.