Informatyka

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

3
Największa suma podzielna przez n
Zadałem to pytanie na StackOverflow , ale myślę, że tutaj jest bardziej odpowiednie miejsce. Jest to problem od kursu Wprowadzenie do algorytmów : Musisz tablicę aaa z liczb całkowitych dodatnich (tablica nie muszą być sortowane lub elementów unikalnych). Zaproponuj algorytm , aby znaleźć największą sumę elementów, która jest podzielna przez …
2
Czy dla każdego wyrażenia „zła” istnieje nie-zła alternatywa, czy też diabeł w gramatyce?
Najwyraźniej ataki ReDos wykorzystują właściwości niektórych (poza tym użytecznych) wyrażeń regularnych ... zasadniczo powodując eksplozję możliwych ścieżek przez wykres zdefiniowany przez NFA. Czy można uniknąć takich problemów, pisząc równoważne wyrażenie „non-evil”? Jeśli nie (w związku z tym gramatyka nie może być obsługiwana przez NFA w praktycznej czasoprzestrzeni), jakie metody analizy …
2
Kiedy połączenie dwóch regularnych języków jest jednoznaczne?
Biorąc pod uwagę języki i , powiedzmy, że ich konkatenacja jest jednoznaczna, jeśli dla wszystkich słów istnieje dokładnie jeden rozkład z i , a niejednoznaczny inaczej. (Nie wiem, czy istnieje ustalony termin dla tej właściwości - trudna rzecz do wyszukania!) Jako trywialny przykład konkatenacja z samym sobą jest niejednoznaczna ( …
1
Czy jest rozstrzygalne, czy automat przesuwający rozpoznaje dany regularny język?
Problem, czy dwa automaty przesuwające rozpoznają ten sam język, jest nierozstrzygalny. Problem, czy automat przesuwający rozpoznaje pusty język, jest rozstrzygalny, a zatem decydujące jest, czy rozpoznaje dany język skończony. Nie można rozstrzygnąć, czy język akceptowany przez automat pushdown jest regularny. Ale ... ... czy można zadecydować, czy automat przesuwający rozpoznaje …
1
Czy nierozwiązywalność problemu N-ciała jest równoważna problemowi zatrzymania
Nie ma ogólnego analitycznego rozwiązania problemu n-ciała, który mógłby wytworzyć funkcję analityczną, która mogłaby zostać użyta do nadania stanu układu n-ciała w dowolnej chwili t z dokładną dokładnością. Istnieją jednak pewne szczególne przypadki układów n-ciała, dla których znana jest funkcja analityczna. W podobny sposób nie ma ogólnego algorytmu, który mógłby …
1
Zagubiony w „jednokierunkowym” koncercie
Ty i przyjaciel zgubiliście się na linii na koncercie, i żaden nie jest pewien, który z was jest dalej. Formalnie każda z nich ma jakąś całkowitą współrzędną i może podążać w kierunku wyższej współrzędnej lub pozostać na miejscu. Zakładając, że ty i twój przyjaciel przestrzegacie dokładnie tego samego algorytmu (i …
3
Czy istnieje pogląd na złożoność twierdzenia Galois?
Twierdzenie Galois skutecznie mówi, że nie można wyrazić pierwiastków wielomianu stopnia> = 5 za pomocą racjonalnych funkcji współczynników i rodników - czy nie można tego odczytać, mówiąc, że biorąc pod uwagę wielomian, nie ma deterministycznego algorytmu znajdowania pierwiastków? Zastanówmy się teraz nad pytaniem o formę: „Biorąc pod uwagę prawdziwy zakorzeniony …
2
Podejście punktowe do komputerowych przeciwników, którzy potrzebują równowagi
To pytanie dotyczy podejścia do przeciwników komputerowych, które stworzyłem i albo są obecnie używane, albo planuje się ich użycie w kilku grach komputerowych. tło W ubiegłym roku, kiedy próbowałem ulepszyć komputerowego przeciwnika w grze o nazwie „Saper Flagi” (krótki opis: Turowa wersja Saper dla wielu graczy, w której musisz wziąć …
2
W jaki sposób dopuszczalna heurystyka zapewnia optymalne rozwiązanie?
Używając A * (lub innego algorytmu znajdowania najlepszej ścieżki), mówimy, że zastosowana heurystyka powinna być dopuszczalna , to znaczy nigdy nie powinna przeceniać faktycznej długości ścieżki rozwiązania (lub ruchów). W jaki sposób dopuszczalna heurystyka zapewnia optymalne rozwiązanie? Najlepiej szukam intuicyjnego wyjaśnienia. Jeśli chcesz, możesz wyjaśnić za pomocą heurystycznej odległości 8-puzzle …
2
Jakie są krytyki dotyczące wydajności HTM?
Niedawno dowiedziałem się o istnieniu tej hierarchicznej pamięci czasowej (HTM) . Przeczytałem już dokument Hierarchical Temporal Memory: Concepts, Theory and Terminology (autorstwa Jeffa Hawkinsa i Dileepa George'a), który wydaje się raczej łatwy do zrozumienia, ale jedną czerwoną flagą jest to, że dokument nie jest recenzowany ani nie próbuje wyjaśnić, dlaczego …
1
Czy perceptron może zapomnieć?
Chciałbym zbudować internetowy system uczenia maszynowego online, w którym użytkownicy mogą stale dodawać sklasyfikowane próbki i aktualizować model online. Chciałbym użyć perceptronu lub podobnego algorytmu uczenia się online. Jednak użytkownicy mogą popełniać błędy i wstawiać nieistotne przykłady. W takim przypadku chciałbym mieć opcję usunięcia określonego przykładu bez ponownego szkolenia perceptronu …
1
Przekształcanie arbitralnej osłony w osłonę wierzchołków
Podano wykres płaski G=(V,E)G=(V,E)G=(V,E) i niech oznacza jego osadzenie w płaszczyźnie st, każda krawędź ma długość . Mam ponadto zestaw punktów, w których każdy punkt jest zawarty w . Ponadto, dla dowolnego punktu w istnieje z odległością geodezyjną do co najwyżej jeden. (Odległość jest mierzona jako najkrótsza odległość w obrębie …
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.