Informatyka

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

3
Jaka jest ta gramatyka LL (1)?
To pytanie z Dragon Book. Oto gramatyka: S→AaAb∣BbBaS→AaAb∣BbBaS \to AaAb \mid BbBa A→εA→εA \to \varepsilon B→εB→εB \to \varepsilon Pytanie dotyczy tego, jak pokazać, że jest to LL (1), ale nie SLR (1). Aby udowodnić, że jest to LL (1), próbowałem zbudować jego tabelę analizującą, ale otrzymuję wiele produkcji w komórce, …
3
Jakie jest znaczenie „szerokość” przy pierwszym wyszukiwaniu?
Uczyłem się o pierwszym wyszukiwaniu szerokości i przyszło mi do głowy pytanie, dlaczego tak nazywa się BFS. W książce Wprowadzenie do algorytmów CLRS przeczytałem następujący powód: Poszukiwanie szerokości jest tak nazwane, ponieważ równomiernie rozszerza granicę między odkrytymi i nieodkrytymi wierzchołkami na całej szerokości granicy. Nie jestem jednak w stanie zrozumieć …
2
Dlaczego maszyny Turinga liniowo ograniczone są bardziej wydajne niż automaty o stanie skończonym?
Miałem wrażenie, że nasze komputery, będąc skończone, ostatecznie nie są potężniejsze niż (wyjątkowo duże) skończone maszyny stanowe. Jednak maszyny Turinga liniowo ograniczone są również skończone, ale wydaje się, że zwykłe języki są ściśle niewłaściwym podzbiorem języków wrażliwych na kontekst. Oczywiście czegoś tu brakuje. Co się dzieje?
2
Zredukowanie produktów w HoTT do kodowania kościoła / Scotta
Więc idę z książką HoTT z niektórymi ludźmi. Stwierdziłem, że większość typów indukcyjnych, które zobaczymy, można zredukować do typów zawierających tylko zależne typy funkcji i wszechświaty, przyjmując typ rekurencji za inspirację dla typu równoważnego. Zacząłem szkicować, jak sądzę, że to zadziała i po pewnym potknięciu doszedłem do tego, co uważałem …
2
Znalezienie k-tego najmniejszego elementu z danej sekwencji tylko z czasem O (k) pamięci O (k)
Załóżmy, że odczytujemy ciąg nnn liczb, jeden po drugim. Jak znaleźć kkk najmniejszy element za pomocą pamięci komórkowej O(k)O(k)O(k) oraz w czasie liniowym ( O(n)O(n)O(n) ). Myślę, że powinniśmy zapisać pierwsze kkk wyrażeń w sekwencji, a kiedy otrzymamy k+1k+1k+1 -ty termin, usuń go, który z pewnością nie może być kkk …
3
Reprezentuj układ 5 kart
Talia kart to 52. Ręka to 5 kart z 52 (nie może mieć duplikatu). Jaka jest najmniejsza liczba bitów reprezentująca układ 5 kart i jak? Ręka NIE jest zależna od kolejności (KQ = QK). 64329 = 96432 Tak, można użyć 52 bitów. Może to stanowić układ dowolnej liczby kart. Biorąc …
3
Złożoność czasowa dodawania
Wikipedia wymienia złożoność czasową dodawania jako , gdzie jest liczbą bitów.nnnnnnn Czy to sztywna teoretyczna dolna granica? Czy to tylko złożoność obecnie najszybszego znanego algorytmu. Chcę wiedzieć, ponieważ złożoność dodawania podkreśla wszystkie inne operacje arytmetyczne i wszystkie algorytmy, które ich używają. Czy teoretycznie niemożliwe jest uzyskanie algorytmu dodawania działającego w …
5
Nauka danych a badania operacyjne
Ogólne pytanie, jak sugeruje tytuł, brzmi: Jaka jest różnica między DS a optymalizacją / optymalizacją. Na poziomie koncepcyjnym rozumiem, że DS próbuje wydobywać wiedzę z dostępnych danych i wykorzystuje głównie techniki statystyczne, uczenie maszynowe. Z drugiej strony OR wykorzystuje dane do podejmowania decyzji na podstawie danych, na przykład poprzez optymalizację …
1
Czy właściwości, takie jak wykorzystanie pamięci przez funkcję, można wyrazić w języku zależnym od typu?
Załóżmy, że ktoś chce argumentować o właściwościach kodu wykraczających poza takie rzeczy, jak totalność i czystość funkcjonalna - dba się również o zużycie pamięci lub złożoność algorytmiczną funkcji. Czy można tego dokonać za pomocą zależnych systemów pisania i efektów?
2
Przypuszczenia matematyczne równoważne zatrzymaniu maszyny Turinga
To pytanie dotyczy tego, czy każde twierdzenie matematyczne można sprowadzić do pytania, czy zatrzyma się pojedyncza maszyna Turinga. W szczególności interesują mnie przypuszczenia, które są obecnie niesprawdzone. Na przykład: Wikipedia mówi , że obecnie nie wiadomo, czy są jakieś nieparzyste liczby idealne. Ponieważ można rozstrzygnąć, czy dana liczba jest idealna, …
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.