Informatyka

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

7
Czy można używać PRNG do magicznej kompresji?
Pomysł ten przyszedł mi do głowy jako dziecko uczące się programowania i przy pierwszym spotkaniu z PRNG. Nadal nie wiem, jak realistyczne jest, ale teraz jest wymiana stosów. Oto 14-letni schemat niesamowitego algorytmu kompresji: Weź PRNG i zaszczep go ziarnem, saby uzyskać długą sekwencję pseudolosowych bajtów. Aby przekazać tę sekwencję …
6
Jakie są zastosowania grup, monoidów i pierścieni w obliczeniach baz danych?
Dlaczego firma taka jak Twitter byłaby zainteresowana koncepcjami algebraicznymi, takimi jak grupy, monoidy i pierścienie? Zobacz ich repozytorium na github: twitter / algebird . Mogłem tylko znaleźć: Implementacje Monoidów dla interesujących algorytmów aproksymacyjnych, takich jak filtr Bloom , HyperLogLog i CountMinSketch . Pozwalają ci myśleć o tych wyrafinowanych operacjach, takich …
2
Czy generatory śmieci są z natury przyjazne dla pamięci podręcznej?
Typowy generacyjny moduł wyrzucający elementy bezużyteczne przechowuje ostatnio przydzielone dane w osobnym regionie pamięci. W typowych programach wiele danych jest krótkotrwałych, więc częste zbieranie śmieci (niewielki cykl GC) i rzadkie zbieranie starych śmieci jest dobrym kompromisem między narzutem pamięci a czasem spędzonym na GC. Intuicyjnie korzyść generatora śmieciowego generatora w …
3
Jak modeluje się złożoność algorytmu dla języków funkcjonalnych?
Złożoność algorytmu została zaprojektowana w taki sposób, aby była niezależna od szczegółów niższego poziomu, ale opiera się na modelu imperatywnym, np. Dostęp do tablicy i modyfikowanie węzła w drzewie zajmuje O (1). Nie dotyczy to wyłącznie języków funkcjonalnych. Dostęp do listy Haskell zajmuje liniowy czas. Modyfikowanie węzła w drzewie wymaga …
8
Co decyduje o „szybkości” języka programowania?
Załóżmy, że program został napisany w dwóch różnych językach, niech to będą język X i język Y, jeśli ich kompilatory generują ten sam kod bajtowy, dlaczego powinienem używać języka X zamiast języka Y? Co określa, że ​​jeden język jest szybszy od drugiego? Pytam o to, ponieważ często zdarza się, że …
3
Algorytm czynnikowy jest bardziej wydajny niż naiwne mnożenie
Wiem, jak kodować silnie przy użyciu iteracji i rekurencji (np. n * factorial(n-1)Na przykład). Przeczytałem w podręczniku (bez dalszych wyjaśnień), że istnieje jeszcze bardziej wydajny sposób kodowania silni poprzez dzielenie ich na pół rekurencyjnie. Rozumiem, dlaczego tak może być. Chciałem jednak spróbować napisać go samodzielnie i nie sądzę, że wiem …
2
Zakłopotany twierdzeniem Rice'a
Podsumowanie: Zgodnie z twierdzeniem Rice'a wszystko jest niemożliwe. A jednak cały czas robię to , jak się wydaje, rzeczy niemożliwe ! Oczywiście twierdzenie Rice'a nie mówi po prostu „wszystko jest niemożliwe”. Mówi coś bardziej szczegółowego: „Każda właściwość programu komputerowego jest niepoliczalna”. (Jeśli chcesz podzielić włosy, każdą właściwość „nietrywialną”. To znaczy …
6
Dlaczego i jak komputer kwantowy jest szybszy niż zwykły komputer?
Obecnie czytam książkę (i wiele Wikipedii) na temat fizyki kwantowej i jeszcze nie zrozumiałem, w jaki sposób komputer kwantowy może być szybszy niż komputery, które mamy dzisiaj. W jaki sposób komputer kwantowy może rozwiązać problem w czasie wykładniczym, który klasyczny komputer może rozwiązać tylko w czasie wykładniczym?
2
Czy istnieją z natury niejednoznaczne i deterministyczne języki bezkontekstowe?
Nazwijmy bezkontekstowy język deterministyczny wtedy i tylko wtedy, gdy może on zostać zaakceptowany przez deterministyczny automat odpychający, a niedeterministyczny inaczej. Nazwijmy język bezkontekstowy z natury dwuznacznym wtedy i tylko wtedy, gdy wszystkie bezkontekstowe gramatyki, które generują ten język, są dwuznaczne, a jednoznaczne inaczej. Przykładem deterministycznego, jednoznacznego języka jest język: Przykładem …
3
Problemy decyzyjne a „rzeczywiste” problemy, które nie są „tak lub nie”
Czytałem w wielu miejscach, że niektóre problemy są trudne do przybliżenia ( NP jest trudne do przybliżenia ). Ale przybliżenie nie jest problemem decyzyjnym: odpowiedź jest liczbą rzeczywistą, a nie Tak lub Nie. Również dla każdego pożądanego współczynnika przybliżenia istnieje wiele odpowiedzi, które są poprawne, a wiele błędnych, a to …
3
Czym dokładnie jest logika?
Być może należałoby przeprosić za zadanie kolejnego pytania na temat warunków wstępnych, ale byłem zdezorientowany co do punktów wyjścia. Spotkałem różne terminy, takie jak „logika modalna”, „logika czasowa”, „logika pierwszego rzędu”, „logika drugiego rzędu” i „logika wyższego rzędu”. Co dokładnie oznacza „logika” w tym kontekście? Jak rygorystycznie definiujemy słowo „logika”? …
3
Wprowadzenie do teorii typów Martina-Löfa
Jakie byłoby najlepsze wprowadzenie do pomysłów Per Martina-Löfsa na temat teorii typów? Obejrzałem niektóre wykłady ze szkoły letniej w Oregon PL, ale nadal jestem zdziwiony następującym pytaniem: Jaki jest typ Wiem, co to jest zestaw, ponieważ można je zdefiniować za pomocą zwykłych aksjomatów ZF i mają one bardzo intuicyjny konkretny …
6
Matematyka związana z konwersją z dowolnej bazy na dowolną bazę bez przechodzenia przez bazę 10?
Patrzyłem na matematykę dotyczącą konwersji z dowolnej bazy na dowolną bazę. Chodzi bardziej o potwierdzenie moich wyników niż cokolwiek innego. Znalazłem moją odpowiedź na mathforum.org, ale nadal nie jestem pewien, czy mam rację. Mam konwersję z większej bazy na mniejszą bazę w porządku, ponieważ jest to po prostu pierwsza cyfra …
11
Dlaczego dane w informatyce są uważane za dyskretne?
Rozumiem, że „struktura” danych jest całkowicie zależna od Algebry Boolean, ale: Dlaczego dane są uważane za dyskretny byt matematyczny, a nie ciągły? Powiązane z tym: Jakie wady lub niezmienniki są naruszane w strukturze danych jako ciągłej jednostki w wymiarach ?rrr Nie jestem ekspertem w tej dziedzinie, ponieważ jestem studentem matematyki …
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.