Informatyka

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

1
Ważona suma ostatnich N liczb
Załóżmy, że otrzymujemy liczby w strumieniu. Po otrzymaniu każdej liczby należy obliczyć ważoną sumę ostatnich liczb, przy czym wagi są zawsze takie same, ale dowolne.NNN Jak skutecznie można to zrobić, jeśli pozwolimy zachować strukturę danych, która pomoże w obliczeniach? Czy możemy zrobić coś lepszego niż , tj. Przeliczać sumę za …
4
Dlaczego ważne jest, aby funkcje były anonimowe w rachunku lambda?
Oglądałem wykład Jima Weiricha zatytułowany „ Przygody w programowaniu funkcjonalnym ”. W tym wykładzie wprowadza pojęcie kombinatorów Y, które zasadniczo znajduje punkt stały dla funkcji wyższego rzędu. Jedną z motywów, jak wspomina, jest możliwość wyrażenia funkcji rekurencyjnych za pomocą rachunku lambda, tak aby teoria Kościoła (wszystko, co można skutecznie obliczyć, …
2
Skonstruuj dwie funkcje
Skonstruuj dwie funkcje spełniające:f,g:R+→R+f,g:R+→R+ f,g: R^+ → R^+ f,gf,gf, g są ciągłe; f,gf,gf, g wzrastają monotonicznie; f≠O(g)f≠O(g)f \ne O(g) i .g≠O(f)g≠O(f)g \ne O(f)
1
Jak przekonwertować maszynę Turinga rozpoznającą język na nieograniczoną gramatykę?
Zgodnie z tym artykułem Wikipedii , nieograniczone gramatyki są równoważne maszynom Turinga. Artykuł zauważa, że ​​mogę przekonwertować dowolną maszynę Turinga na nieograniczoną gramatykę, ale pokazuje ona tylko, jak przekonwertować gramatykę na maszynę Turinga. Jak rzeczywiście to zrobić i przekonwertować maszynę Turinga rozpoznającą język na nieograniczoną gramatykę? Próbowałem zastąpić reguły przejścia …
3
Dlaczego warto używać porównań zamiast środowiska wykonawczego do porównywania dwóch algorytmów?
Zauważam, że w kilku artykułach z badań CS, w celu porównania wydajności dwóch algorytmów, zamiast samych rzeczywistych czasów obliczeniowych użyto całkowitej liczby kluczowych porównań w algorytmach. Dlaczego nie możemy porównać, który z nich jest lepszy, uruchamiając oba programy i licząc całkowity czas potrzebny do uruchomienia algorytmów?
1
Generujesz dane wejściowe dla algorytmów graficznych do testowania losowego?
Podczas testowania algorytmów powszechnym podejściem jest testowanie losowe: generuj znaczną liczbę danych wejściowych zgodnie z pewnym rozkładem (zwykle jednolitym), uruchom na nich algorytm i sprawdź poprawność. Nowoczesne ramy testowania mogą generować dane wejściowe automatycznie na podstawie podpisu algorytmów, z pewnymi ograniczeniami. Jeśli dane wejściowe są liczbami, listami lub łańcuchami, generowanie …
3
Linia oddziela dwa zestawy punktów
Czy istnieje sposób na stwierdzenie, czy dwa zestawy punktów można oddzielić linią? Mamy dwa zestawy punktów i jeśli istnieje linia, która oddziela i tak że wszystkie punkty i tylko po jednej stronie linii oraz wszystkie punkty i tylko po drugiej stronie.B A B A A B BAAABBBAAABBBAAAAAABBBBBB Najbardziej naiwnym algorytmem, …
5
Maksymalny niezależny zestaw wykresu dwudzielnego
Próbuję znaleźć maksymalny niezależny zestaw wykresu biparytu. W niektórych notatkach „13 maja 1998 r. - University of Washington - CSE 521 - Zastosowania przepływu sieci” znalazłem : Problem: Biorąc pod uwagę dwudzielny wykres , znalezienie niezależnego zestawu , który jest tak duży, jak to tylko możliwe, w którym i . …
3
Czy dla każdej funkcji obliczalnej
Czy dla każdej funkcji obliczalnej fff istnieje problem, który można najlepiej rozwiązać w czasie Θ(f(n))Θ(f(n))\Theta(f(n)) czy też istnieje funkcja obliczalna fff tak że każdy problem, który można rozwiązać w O(f(n))O(f(n))O(f(n)) może również być rozwiązany w czasie o(f(n))o(f(n))o(f(n)) ? To pytanie wpadło mi do głowy wczoraj. Zastanawiam się przez chwilę, ale …
1
rozproszone przycinanie alfa beta
Szukam wydajnego algorytmu, który pozwala mi przetwarzać drzewo wyszukiwania minimax dla szachów z przycinaniem alfa-beta w architekturze rozproszonej. Algorytmy, które znalazłem (PVS, YBWC, DTS, patrz poniżej) są dość stare (najpóźniej 1990). Zakładam, że od tego czasu nastąpiło wiele istotnych postępów. Jaki jest obecny standard w tej dziedzinie? Proszę również wskazać …
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.