Informatyka

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

1
Złożoność znalezienia współczynnika dwumianowego równego liczbie
Załóżmy, że otrzymujesz liczbę mmm (używając O(logm)O(log⁡m)O(\log m) bitów w kodowaniu binarnym). Jak szybko można znaleźć (lub stwierdzić, że takie nie istnieje) ?n,k∈N,1&lt;k≤n2:(nk)=mn,k∈N,1&lt;k≤n2:(nk)=mn,k\in \mathbb N, 1<k\leq\frac{n}{2}:{n \choose k}=m Na przykład, biorąc pod uwagę wejście , można wyprowadzić .m=8436285m=8436285m=8436285n=27,k=10n=27,k=10n=27, k=10 Naiwny algorytm dla problemu przekroczyłby wszystkie możliwe wartości dla i szukałby …
3
Deterministyczny algorytm czasu liniowego do sprawdzania, czy jedna tablica jest posortowaną wersją drugiej
Rozważ następujący problem: Dane wejściowe: dwie tablice i o długości , gdzie jest posortowane.B n BAAABBBnnnBBB Pytanie: czy i zawierają te same elementy (z ich wielokrotnością)?B.AAABBB Jaki jest najszybszy algorytm deterministyczny dla tego problemu? Czy można to rozwiązać szybciej niż ich sortowanie? Czy ten problem można rozwiązać w deterministycznym czasie …
1
Czy istnieje algorytm O (n log n) dla uproszczenia linii 4D?
Algorytm Ramer Douglasa-Peucker dla linii Uproszczenie najgorszy czasem przebiegu. W przypadku odpowiednio rozmieszczonych losowych danych wejściowych oczekiwał złożoności środowiska wykonawczego O ( n log n ) . W 2D istnieją inne algorytmy o najgorszym przypadku złożoności środowiska wykonawczego O ( n log n ) , które obliczają dokładnie taki sam …
2
Problemy, które prawdopodobnie wymagają czasu kwadratowego
Szukam przykładów problemu, który ma dolną granicę ) dla wejścia .Ω(|x|2Ω(|x|2\Omega(|x|^2xxx Problem musi mieć następujące właściwości: Ω(n2)Ω(n2)\Omega(n^2) Środowisko wykonawcze dla dowolnego algorytmu - priorytetem jest możliwie najprostszy argument dolnej granicy. O(n2)O(n2)O(n^2)Algorytm , jeśli to możliwe, również prosty. Rozmiar wyjściowy (lub mniejszy). Oczywiście każdy problem, który wymaga wydłużonego wyjścia wymagał co …
1
Czy istnieją implementacje blokady sprzętu bez testowania i ustawiania lub wymiany?
Blokady są zwykle wdrażane za pomocą instrukcji testowania i ustawiania oraz wymiany na poziomie maszyny. Czy istnieją inne implementacje, które ich nie wykorzystują? Czy możemy również powiedzieć, że wszystkie rozwiązania problemu krytycznego na poziomie sprzętowym można podzielić na trzy, a mianowicie: wyłączanie przerwań, testowanie i ustawianie oraz zamiana?
6
Jak mogę powiedzieć naukowo, że „jeden komputer jest wolniejszy od drugiego”?
Piszę artykuł badawczy i muszę zasadniczo powiedzieć, że jeden mikrokontroler jest wolniejszy niż inny mikroprocesor. Martwię się jednak, że samo powiedzenie, że jest „wolniejsze”, nie byłoby właściwe w pracy badawczej. Czy mam rację? Czy można powiedzieć, że jeden procesor jest „wolniejszy”, czy muszę powiedzieć coś innego? Co jeszcze mogę powiedzieć? …
1
Jakie klasy struktur danych można utrwalić?
Trwałe struktury danych to niezmienne struktury danych. Operacje na nich zwracają nową „kopię” struktury danych, ale zmienioną przez operację; stara struktura danych pozostaje jednak niezmieniona. Wydajność jest na ogół osiągana przez dzielenie się niektórymi danymi bazowymi i unikanie pełnego kopiowania struktury danych. Pytania: Czy istnieją wyniki dotyczące klas struktur danych, …
2
Czy można wykazać twardość NP poprzez redukcje Turinga?
W artykule Złożoność problemu Frobeniusa autorstwa Ramíreza-Alfonsína okazało się, że problemem jest NP-zupełność za pomocą redukcji Turinga. Czy to jest możliwe? Jak dokładnie? Myślałem, że było to możliwe tylko w przypadku wielomianowego wielokrotnego zmniejszenia. Czy są jakieś odniesienia na ten temat? Czy istnieją dwa różne pojęcia twardości NP, a nawet …
2
Sortuj tablicę 5 liczb całkowitych z maksymalnie 7 porównaniami
Jak mogę posortować listę 5 liczb całkowitych tak, że w najgorszym przypadku potrzeba 7 porównań? Nie obchodzi mnie, ile innych operacji zostanie wykonanych. Nie wiem nic szczególnego o liczbach całkowitych. Wypróbowałem kilka różnych metod dzielenia i podbijania, które obniżają mnie do 8 porównań, takich jak stosowanie podejścia scalesort lub łączenie …
1
Jak czas działania algorytmu Ukkonen zależy od wielkości alfabetu?
Niepokoi mnie kwestia asymptotycznego czasu działania algorytmu Ukkonena , być może najpopularniejszego algorytmu do konstruowania drzewek sufiksów w czasie liniowym (?). Oto cytat z książki „Algorytmy na strunach, drzewach i sekwencjach” Dana Gusfielda (sekcja 6.5.1): „... wszystkie algorytmy Aho-Corasick, Weiner, Ukkonen i McCreight wymagają albo przestrzeni , albo ograniczenie czasowe …
3
Jak korzystać ze sztucznej inteligencji w szachach komputerowych
W niektórych (historycznych) artykułach szachy określane są mianem drozofili sztucznej inteligencji. Chociaż przypuszczam, że w bieżących badaniach zwykłe zastosowanie algorytmu wyszukiwania jest w najlepszym przypadku zaawansowaną informatyką , uważam, że nadal istnieją obszary, w których można zastosować (i ćwiczyć) techniki sztucznej inteligencji. Prostym przykładem może być uczenie się na podstawie …
4
Czy środowisko wykonawcze może wykryć nieskończoną pętlę?
Czy środowisko wykonawcze może wykryć nieskończone pętle, a następnie zatrzymać powiązany proces, czy też wdrożenie takiej logiki byłoby równoznaczne z rozwiązaniem problemu zatrzymania? Na potrzeby tego pytania definiuję „nieskończoną pętlę”, która oznacza serię instrukcji i powiązanych początkowych danych stosu / sterty, które po uruchomieniu zwracają proces do dokładnie tego samego …
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.