Informatyka

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

1
Wnioskowanie typu na podstawie typów produktów
Pracuję nad kompilatorem dla języka konkatenatywnego i chciałbym dodać obsługę wnioskowania typu. Rozumiem Hindleya-Milnera, ale nauczyłem się teorii typów, więc nie jestem pewien, jak ją dostosować. Czy następujący system jest dźwiękowy i można go w sposób zdecydowanie wywnioskować? Termin jest literałem, kompozycją terminów, cytatem terminu lub prymitywem. e::=x∣∣ee∣∣[e]∣∣…e::=x|ee|[e]|… e ::= …
4
Czy funkcje są zawsze asymptotycznie porównywalne?
Kiedy porównujemy złożoność dwóch algorytmów, zwykle dzieje się tak, że albo albo g ( n ) = O ( f ( n ) ) (ewentualnie oba), gdzie f i g to czasy działania (na przykład) dwóch algorytmów.f(n)=O(g(n))f(n)=O(g(n))f(n) = O(g(n))g(n)=O(f(n))g(n)=O(f(n))g(n) = O(f(n))fffggg Czy tak jest zawsze? Oznacza to, że ma co …
1
Wszyscy żołnierze powinni strzelać w tym samym czasie
Kiedy byłem studentem, widziałem problem w podręczniku do projektowania systemów cyfrowych / logiki, dotyczący N żołnierzy stojących w rzędzie i chcących strzelać w tym samym czasie. Trudniejszą wersją tego problemu było to, że żołnierze stoją w ogólnej sieci zamiast w rzędzie. Jestem pewien, że to klasyczny problem, ale nie pamiętam …
3
Rozwiązywanie równań rekurencyjnych zawierających dwa wezwania rekurencyjne
Próbuję znaleźć granicę ΘΘ\Theta dla następującego równania rekurencyjnego: T(n)=2T(n/2)+T(n/3)+2n2+5n+42T(n)=2T(n/2)+T(n/3)+2n2+5n+42 T(n) = 2 T(n/2) + T(n/3) + 2n^2+ 5n + 42 Uważam, że Twierdzenie Mistrza jest nieodpowiednie ze względu na różną liczbę podproblemów i podziałów. Również drzewa rekurencyjne nie działają, ponieważ nie ma a raczej T ( 0 ) .T(1)T(1)T(1)T(0)T(0)T(0)
5
Czy istnieją nierozstrzygalne właściwości niekompletnych automatów?
Czy istnieją nierozstrzygalne właściwości automatów z ograniczeniami liniowymi (unikanie sztuczki z pustym językiem ustawiania)? A co z deterministycznym automatem skończonym? (odłóż na bok trudność). Chciałbym uzyskać przykład (jeśli to możliwe) niezdecydowanego problemu, który jest zdefiniowany bez jawnego używania maszyn Turinga . Czy kompletność modelu Turinga jest niezbędna do obsługi problemów …
1
Znajdź najdłuższą ścieżkę od korzenia do liścia na drzewie
Mam drzewo (w sensie teorii grafów), takie jak następujący przykład: Jest to ukierunkowane drzewo z jednym węzłem początkowym (korzeń) i wieloma końcowymi węzłami (liście). Każda krawędź ma przypisaną długość. Moje pytanie brzmi: jak znaleźć najdłuższą ścieżkę, zaczynając od korzenia i kończąc na którymś z liści? Podejście brutalnej siły polega na …
2
Przecięcie okręgu z algorytmem linii przeciągnięcia
Niestety nadal nie jestem tak silny w zrozumieniu algorytmu linii przeciągania . Wszystkie artykuły i podręczniki na ten temat są już przeczytane, jednak ich zrozumienie jest wciąż bardzo odległe. Aby to wyjaśnić, próbuję rozwiązać jak najwięcej ćwiczeń. Ale naprawdę interesujące i ważne zadania wciąż stanowią dla mnie wyzwanie. Poniższe ćwiczenie …
4
Czy język programu może być wystarczająco plastyczny, aby umożliwić programom rozszerzenie semantyki języka?
W odniesieniu do funkcji w językach takich jak ruby ​​(i javascript), które pozwalają programiście rozszerzyć / przesłonić klasy w dowolnym momencie po ich zdefiniowaniu (w tym klasy takie jak String), czy teoretycznie wykonalne jest zaprojektowanie języka, który może pozwolić programom na późniejsze rozszerzenie jego semantyka. np .: Ruby nie zezwala …
3
Jak podejść do problemów związanych z dynamicznym wykresem
Zadałem to pytanie przy ogólnym przepełnieniu stosu i skierowano mnie tutaj. Świetnie będzie, jeśli ktoś będzie w stanie wyjaśnić, w jaki sposób ogólnie podejść do częściowych lub w pełni dynamicznych problemów graficznych. Na przykład: Znajdź najkrótszą ścieżkę między dwoma wierzchołkami na niekierowanym wykresie ważonym dla wystąpień, gdy krawędź jest usuwana …
1
Moc obliczeniowa deterministycznych versus niedeterministycznych automatów typu min-heap
To jest kolejne pytanie tego . W poprzednim pytaniu dotyczącym egzotycznych automatów stanowych Alex ten Brink i Raphael odnieśli się do możliwości obliczeniowych szczególnego rodzaju automatu stanowego: automatów typu min-heap. Udało im się wykazać, że zestaw języków akceptowanych przez takie maszyny ( ) nie jest ani podzbiorem, ani nadzbiorem zestawu …
3
Bramy logiczne z codziennych materiałów
Bramki logiczne są abstrakcyjnym urządzeniem, które można zrealizować za pomocą przekaźników elektromagnetycznych, lamp próżniowych lub tranzystorów. Te wcielenia okazały się częściowo skuteczne z uwagi na różne właściwości łańcuchowości, trwałości i wielkości przekraczające ich podstawową stabilność binarną. Działają również dobrze, ponieważ energia elektryczna jest źródłem energii, którą można dość łatwo przesyłać. …
2
Czas poświęcony wymaganiom i jego wpływ na sukces projektu i czas rozwoju
Czy istnieją dowody sugerujące, że czas poświęcony na pisanie lub myślenie o wymaganiach będzie miało jakikolwiek wpływ na czas opracowywania? Badanie przeprowadzone przez Standish (1995) sugeruje, że niekompletne wymagania częściowo (13,1%) przyczyniły się do niepowodzenia projektów. Czy przeprowadzono jakieś badania, które pokazują, że czas poświęcony na analizę wymagań będzie miał …
2
Która metoda jest preferowana do przechowywania dużych obiektów geometrycznych w kwadracie?
Podczas umieszczania obiektów geometrycznych w kwadracie (lub oktawie) możesz umieszczać obiekty większe niż pojedynczy węzeł na kilka sposobów: Umieszczenie odniesienia do obiektu w każdym liściu, dla którego jest zawarty Umieszczenie odniesienia do obiektu w najgłębszym węźle, dla którego jest w pełni zawarty Zarówno # 1, jak i # 2 Na …
2
Liczba słów o określonej długości w zwykłym języku
Czy istnieje algebraiczna charakterystyka liczby słów o danej długości w zwykłym języku? Wikipedia podaje wynik nieco nieprecyzyjnie: Dla każdego języka regularnego istnieje stałych i wielomiany tak, że dla każdego numer z słowa o długości w spełnia równanie .LLLλ1,…,λkλ1,…,λk\lambda_1,\,\ldots,\,\lambda_kp1(x),…,pk(x)p1(x),…,pk(x)p_1(x),\,\ldots,\,p_k(x)nnnsL(n)sL(n)s_L(n)nnnLLLsL(n)=p1(n)λn1+⋯+pk(n)λnksL(n)=p1(n)λ1n+⋯+pk(n)λkns_L(n)=p_1(n)\lambda_1^n+\dotsb+p_k(n)\lambda_k^n Nie jest określone, w jakiej przestrzeni żyje ( , jak przypuszczam) i …
1
Jeśli wirtualna przestrzeń adresowa może być większa niż fizyczna przestrzeń adresowa, w jaki sposób mapowania adresów są przechowywane w pamięci?
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 niż w lokalizacjach w pamięci fizycznej.2)402)402^{40} Ma …
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.