Informatyka

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

4
Czy problemy z ograniczeniami można rozwiązać za pomocą Prolog?
Czy problemy typu „obecność na imprezie” można rozwiązać w Prologu? Na przykład: Łopian Muldoon i Carlotta Pinkstone powiedzieli, że przybędą, jeśli przyjdzie Albus Dumbledore. Albus Dumbledore i Daisy Dodderidge powiedzieli, że przybędą, jeśli przyjdzie Carlotta Pinkstone. Albus Dumbledore, Burdock Muldoon i Carlotta Pinkstone powiedzieli, że przyjdą, jeśli przyjdzie Elfrida Clagg. …
4
Pokazuje, że problem w X nie jest X-Complete
Egzystencjalna teoria Real jest w PSPACE , ale nie wiem, czy to jest PSPACE zupełnych . Jeśli uważam, że tak nie jest, jak mogę to udowodnić? Mówiąc bardziej ogólnie, biorąc pod uwagę problem z pewną klasą złożoności X , jak mogę pokazać, że nie jest to X-Complete ? Na przykład …
1
Naturalne występowanie monad, które wykorzystują ramy teoretyczne kategorii
Dzisiaj przemówienie Henninga Kerstana („Trace Semantics for Probabilistic Transition Systems”) po raz pierwszy skonfrontowało mnie z teorią kategorii. Zbudował teoretyczne ramy do opisywania probabilistycznych układów przejściowych i ich zachowania w sposób ogólny, tj. Z nieskończenie nieskończonymi zbiorami stanów i różnymi pojęciami śladów. W tym celu przechodzi przez kilka warstw abstrakcji, …
5
Dla jakiego rodzaju danych są operacje tabeli skrótów O (1)?
Od odpowiedzi do (Kiedy) jest wyszukiwanie tablicy skrótów O (1)? , Rozumiem, że tabele skrótów mają O(1)O(1)O(1)zachowanie w najgorszym przypadku ) , przynajmniej zamortyzowane, gdy dane spełniają określone warunki statystyczne, i istnieją techniki, które pomagają rozszerzyć te warunki. Jednak z perspektywy programisty nie wiem z góry, jakie będą moje dane: …
3
Problemy z wdrażaniem zamknięć w ustawieniach niefunkcjonalnych
W językach programowania zamknięcia są popularną i często pożądaną funkcją. Wikipedia mówi (moje podkreślenie): W informatyce zamknięcie (...) jest funkcją wraz ze środowiskiem odniesienia dla zmiennych nielokalnych tej funkcji. Zamknięcie umożliwia funkcji dostęp do zmiennych poza jej bezpośrednim zakresem leksykalnym. Zatem zamknięcie jest zasadniczo (anonimową?) Wartością funkcji, która może wykorzystywać …
3
Sprytne zarządzanie pamięcią ze stałymi operacjami czasowymi?
Rozważmy segment pamięci (którego rozmiar może się zwiększać lub zmniejszać, jak plik, w razie potrzeby), na którym można wykonać dwie podstawowe operacje alokacji pamięci obejmujące bloki o stałym rozmiarze: przydział jednego bloku uwolnienie wcześniej przydzielonego bloku, który nie jest już używany. Ponadto, jako wymaganie, system zarządzania pamięcią nie może poruszać …
4
Rekurencje i funkcje generujące w algorytmach
Kombinatoryka odgrywa ważną rolę w informatyce. Często stosujemy metody kombinatoryczne zarówno w analizie, jak i projektowaniu w algorytmach. Na przykład jedna metoda znajdowania zestawu okładek kkk -vertex na wykresie może po prostu sprawdzić wszystkie możliwe podzbiory . Podczas gdy funkcje dwumianowe rosną wykładniczo, jeśli jest jakąś stałą stałą, w wyniku …
3
Co konkretnie czyni komputery kwantowe użytecznymi?
Wiem, że komputery kwantowe są w stanie przetwarzać superpozycję wszystkich możliwych stanów za jednym przejściem przez logikę. Wydaje się, że to właśnie ludzie wskazują, że komputery kwantowe są wyjątkowe lub przydatne. Jednak po przetworzeniu danych wejściowych superpozycyjnych otrzymujesz wynik superpozycji, którego możesz zadać tylko jedno pytanie, a ono zapada się …
5
Rozwiązywanie relacji rekurencji z √n jako parametrem
Rozważ powtórzenie T(n)=n−−√⋅T(n−−√)+cnT(n)=n⋅T(n)+cn\qquad\displaystyle T(n) = \sqrt{n} \cdot T\bigl(\sqrt{n}\bigr) + c\,n dla z pewną stałą dodatnią , a .c T ( 2 ) = 1n>2n>2n \gt 2cccT(2)=1T(2)=1T(2) = 1 Znam twierdzenie Master dotyczące rozwiązywania nawrotów, ale nie jestem pewien, w jaki sposób moglibyśmy rozwiązać tę relację za pomocą tego. Jak podchodzisz …
4
Jak sprawdzić, czy dwa algorytmy zwracają ten sam wynik dla dowolnego wejścia?
Jak sprawdzisz, czy dwa algorytmy (powiedzmy: Sortuj i Naiwne) zwracają ten sam wynik dla dowolnego wejścia, gdy zestaw wszystkich danych wejściowych jest nieskończony? Aktualizacja: Dziękuję Ben za opisanie, w jaki sposób niemożliwe jest algorytmiczne wykonanie tego przypadku w ogólnym przypadku. Odpowiedź Dave'a jest doskonałym podsumowaniem metod algorytmicznych i ręcznych (w …
3
Dlaczego pętle są szybsze niż rekurencja?
W praktyce rozumiem, że każdą rekurencję można zapisać jako pętlę (i vice versa (?)) I jeśli mierzymy z rzeczywistymi komputerami, stwierdzimy, że pętle są szybsze niż rekurencja dla tego samego problemu. Ale czy istnieje jakaś teoria, która czyni tę różnicę, czy jest to głównie uzasadnienie?
8
Dlaczego możemy założyć, że algorytm może być reprezentowany jako ciąg bitowy?
Zaczynam czytać książkę o złożoności obliczeniowej i maszynach Turinga. Oto cytat: Algorytm (np. Maszyna) może być reprezentowany jako ciąg bitów, gdy zdecydujemy się na pewne kodowanie kanoniczne. To twierdzenie zostało przedstawione jako prosty fakt, ale nie rozumiem tego. Na przykład, jeśli mam algorytm, który przyjmuje jako dane wejściowe i oblicza …
4
Czy dane można skompresować do rozmiaru mniejszego niż limit kompresji danych Shannona?
Czytałem o algorytmach kompresji danych i teoretycznym limicie kompresji danych. Ostatnio spotkałem metodę kompresji zwaną „kombinatorycznym kodowaniem entropii”, główną ideą tej metody jest kodowanie pliku jako znaków przedstawionych w pliku, ich częstotliwości i indeksu permutacji tych znaków reprezentowanych przez plik. Te dokumenty mogą pomóc w wyjaśnieniu tej metody: https://arxiv.org/pdf/1703.08127 http://www-video.eecs.berkeley.edu/papers/vdai/dcc2003.pdf …
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.