Informatyka

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

2
Jak praktycznie konstruować zwykłe wykresy ekspanderów?
Muszę skonstruować wykres ekspandera regularnego d dla niektórych małych stałych d (jak 3 lub 4) n wierzchołków. Jaka jest najłatwiejsza metoda na zrobienie tego w praktyce? Konstruujesz losowy wykres d-regularny, który okazał się być ekspanderem? Czytałem także o konstrukcjach Margulis i grafach Ramanujana, które są ekspanderami i konstrukcją wykorzystującą produkt …
1
Algorytm
Załóżmy, że podano różnych liczb całkowitych , takich, że dla pewnej stałej i dla wszystkich .nnna1,a2,…,ana1,a2,…,ana_1, a_2, \dots, a_n0≤ai≤kn0≤ai≤kn0 \le a_i \le knk>0k>0k \gt 0iii Interesuje nas znalezienie zliczeń wszystkich możliwych sum . ( jest dozwolone).Sij=ai+ajSij=ai+ajS_{ij} = a_i + a_ji=ji=ji = j Jednym z algorytmów jest skonstruowanie wielomianu stopnia , …
2
„Kolejność aplikacji” i „Normalna kolejność” w rachunku lambda
Kolejność aplikacji: Zawsze w pełni oceniaj argumenty funkcji przed oceną samej funkcji, na przykład - (λx.x2(λx.(x+1) 2)))→(λx.x2(2+1))→ (λx.x2(3))→ 32 → 9(λx.x2(λx.(x+1) 2)))→(λx.x2(2+1))→ (λx.x2(3))→ 32 → 9(\lambda x. x^2(\lambda x.(x+1) \ \ 2))) \rightarrow (\lambda x. x^2(2+1))\rightarrow \ (\lambda x. x^2(3)) \rightarrow \ 3^2 \ \rightarrow \ 9 Normalna kolejność: wyrażenie …
1
Ciekawy problem z sortowaniem
Biorąc pod uwagę tubę z ponumerowanymi kulkami (losowa). Rurka ma otwory do usuwania kulki. Rozważ następujące kroki dla jednej operacji: Możesz wybrać jedną lub więcej piłek z dołków i zapamiętać kolejność, w jakiej je wybrałeś. Musisz przechylić rurę w lewą stronę, aby pozostałe kulki w rurze przesunęły się w lewo …
1
Wydajny algorytm odzyskiwania przejściowego zamknięcia ukierunkowanego wykresu acyklicznego
Próbuję rozwiązać problem z grafem (nie jest to praca domowa, tylko po to, aby ćwiczyć swoje umiejętności). Podaje się DAG , gdzie jest zbiorem wierzchołków, a krawędziami. Wykres jest reprezentowany jako lista przylegania, więc jest zbiorem zawierającym wszystkie połączenia . Moim zadaniem jest znalezienie których wierzchołki są osiągalne z każdego …
3
Teoretyczna CS i matematyka - rekomendacje do samodzielnej nauki
Jestem absolwentem CS, a mój kierunek studiów nie jest związany z CS. Jednak w ramach większego planu zostania informatykiem chcę uzyskać solidne podstawy teoretycznej informatyki i matematyki w zakresie CS. Przeprowadziłem wiele badań i wybrałem następujące najlepsze / naprawdę dobre książki na temat CS i matematyki i chciałbym zapytać o …
14 books 
2
Algorytm Bellmana-Forda - Dlaczego krawędzie mogą być aktualizowane poza kolejnością?
Algorytm Bellmana-Ford, określa najkrótszą ścieżkę ze źródła, do pozostałych wierzchołków. Początkowo odległość między a wszystkimi innymi wierzchołkami jest ustawiona na . Następnie obliczana jest najkrótsza ścieżka od do każdego wierzchołka; dzieje się tak w przypadku iteracji . Moje pytania to:ssssss∞∞\inftysss|V|−1|V|−1|V|-1 Dlaczego potrzebne są iteracje ?|V|−1|V|−1|V|-1 Czy miałoby to znaczenie, jeśli …
2
Funkcja, która rozprowadza dane wejściowe
Chciałbym wiedzieć, czy istnieje funkcja od liczb n-bitowych do liczb n-bitowych, która ma następujące cechy:ffaf ffaf powinien być bijectywny Zarówno i powinny być obliczalne dość szybkoffaff−1f−1f^{-1} fff powinien zwrócić liczbę, która nie ma znaczącej korelacji z wprowadzonymi danymi. Uzasadnienie jest następujące: Chcę napisać program działający na danych. Niektóre informacje o …
1
Warunki płaskości dla Planar 1-in-3 SAT
Planar 3SAT jest kompletny z NP. Płaska instancja 3SAT jest instancją 3SAT, dla której wykres zbudowany przy użyciu następujących reguł jest płaski: dodaj wierzchołek dla każdegoxixix_i i xi¯xi¯\bar{x_i} dodać wierzchołek dla każdej klauzuli CjCjC_j dodaj krawędź dla każdej pary (xi,xi¯)(xi,xi¯)(x_i,\bar{x_i}) dodaj krawędź z wierzchołka (lub ¯ x i ) do …
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.