Informatyka

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

2
Dlaczego uważa się, że DFS ma złożoność przestrzeni ?
Według tych notatek , DFS jest uważany za złożoność przestrzeń, gdzie jest współczynnik rozgałęzienia drzewa i jest maksymalna długość każdej ścieżki w przestrzeni stanów.O(bm)O(bm)O(bm)bbbmmm To samo zostało powiedziane na tej stronie Wikibook w Search Uninformed Search . Teraz „infobox” artykułu Wikipedii na temat DFS przedstawia następujące aspekty złożoności algorytmu: O(|V|)O(|V|)O(|V|) …
2
Co to jest najmniej ograniczająca wartość?
W przypadku problemów związanych z satysfakcją z ograniczeń heurystykę można wykorzystać w celu poprawy wydajności solvera z funkcją Bactracking. Trzy najczęściej podawane heurystyki dla prostych solverów do cofania to: Minimalna pozostała wartość (ile wartości jest nadal poprawnych dla tej zmiennej) Stopień heurystyczny (ile innych zmiennych wpływa na tę zmienną) Najmniejsza …
5
Częstotliwość wyrazów z uporządkowaniem w złożoności O (n)
Podczas wywiadu na stanowisko programisty Java zapytano mnie: Napisz funkcję, która przyjmuje dwa parametry: ciąg znaków reprezentujący dokument tekstowy i liczba całkowita podająca liczbę elementów do zwrócenia. Zaimplementuj funkcję tak, aby zwracała listę ciągów uporządkowanych według częstotliwości słów, najczęściej występujących jako pierwsze słowo. Twoje rozwiązanie powinno działać w czasie gdzie …
5
Czy wszystkie problemy z całkowitym programowaniem liniowym są trudne?
Jak rozumiem, problem przypisania występuje w P, ponieważ węgierski algorytm może go rozwiązać w czasie wielomianowym - O (n 3 ). Rozumiem również, że problem z przypisaniem jest całkowitym problemem programowania liniowego , ale strona Wikipedii stwierdza, że ​​jest to NP-Hard. Dla mnie oznacza to, że problem przypisania jest w …
2
Dowód sprzeczności dla nierówności P i NP?
Próbuję argumentować, że N nie jest równe NP przy użyciu twierdzeń hierarchicznych. To mój argument, ale kiedy pokazałem go naszemu nauczycielowi i po dedukcji powiedział, że jest to problematyczne, gdy nie mogę znaleźć ważnego powodu do zaakceptowania. Zaczynamy od założenia, że . Następnie zwraca który następnie następuje po tym . …
2
Czy możesz uniemożliwić środkowemu czytaniu wiadomości?
Słyszałem o wszystkich tych zapobieganiach atakom typu „człowiek w środku” i zastanawiam się, jak to może działać, jeśli mężczyzna w środku tylko słucha twojego strumienia i nie chce zmienić samej wiadomości. Czy środkowy człowiek może nie tylko wziąć klucze zamienione przez przeciwników, zmienić klucze, a następnie ponownie odszyfrować i zaszyfrować …
2
Czy rachunek SK2 jest kompletną podstawą, gdzie K2 jest odwróconym kombinatorem K?
W szczególności, jeśli zdefiniowałem nowy jako zamiast czy -calculus byłby podstawą do konkurowania?K2K2K_2K2=λx.(λy.y)K2=λx.(λy.y)K_2 = \lambda x. (\lambda y. y)K=λx.(λy.x)K=λx.(λy.x)K = \lambda x. (\lambda y. x){S,K2,I}{S,K2,I}\{S, K_2,I\} Domyślam się, że „nie”, tylko dlatego, że nie wydaje mi się, że jestem w stanie zbudować zwykłego kombinatora K z kombinacji SSS , III …
2
Zbieg ekspansji beta
Niech →β→β\to_\beta będzie redukcją ββ\beta w rachunku λλ\lambda . Zdefiniuj ββ\beta rozszerzenie ←β←β\leftarrow_\beta przez t′←βt⟺t→βt′t′←βt⟺t→βt′t'\leftarrow_\beta t \iff t\to_\beta t' . Czy ←β←β\leftarrow_\beta zbieżny? Innymi słowy, nie mamy, że dla każdego l,d,rl,d,rl,d,r , jeżeli l→∗βd←∗βrl→β∗d←β∗rl \to_\beta^* d\leftarrow_\beta^* r , to istnieje uuu taki sposób, że l←∗βu→∗βrl←β∗u→β∗rl\leftarrow_\beta^* u \to_\beta^* r ? Słowa …
2
Język obejmujący liczbę niewymierną nie jest CFL
Pracuję nad ciężkim ćwiczeniem w podręczniku i po prostu nie mogę wymyślić, jak postępować. Oto problem. Załóżmy, że mamy język gdzie jest liczbą nieracjonalną. Jak mam udowodnić, że nie jest językiem bezkontekstowym?L={aibj:i≤jγ,i≥0,j≥1}L={aibj:i≤jγ,i≥0,j≥1}L = \{a^ib^j: i \leq j \gamma, i\geq 0, j\geq 1\}γγ\gammaLLL W przypadku, gdy jest racjonalna, całkiem łatwo jest …
5
Lambda Calculus Generator
Nie wiem, gdzie jeszcze zadać to pytanie, mam nadzieję, że to dobre miejsce. Jestem tylko ciekawy, czy można zrobić generator lambda; zasadniczo pętla, która w nieskończonym czasie wytworzy każdą możliwą funkcję rachunku lambda. (jak w postaci ciągu). Ponieważ rachunek lambda jest tak prosty, mając tylko kilka elementów do jego zapisu, …
2
Jak uzyskać eliminatory o typie zależnym?
W programowaniu zależnym są dwa główne sposoby dekompozycji danych i wykonania rekurencji: Zależne dopasowanie wzorca : definicje funkcji podano w postaci wielu klauzul. Ujednolicenie zapewnia, że ​​wszystkie pominięte przypadki są niemożliwe, a zewnętrzny solver zapewnia, że ​​rekurencja jest uzasadniona. Eliminatory : Każda indukcyjnego typu danych posiada powiązaną stałej E D …
1
Co obliczył tajemniczy mały program Turinga na komputerze w Manchesterze?
Czytam artykuł Turinga „Maszyny obliczeniowe i inteligencja” ( https://www.csee.umbc.edu/courses/471/papers/turing.pdf ) i znalazłem fragment, w którym mówi: Na komputerze w Manchesterze utworzyłem mały program wykorzystujący tylko 1000 jednostek pamięci, przy czym maszyna dostarczona z jedną szesnastocyfrową liczbą odpowiada drugą w ciągu dwóch sekund. Przeciwstawiłbym się każdemu, kto mógłby wyciągnąć z tych …
1
Czy programowanie genetyczne jest dziś aktualne?
Moim głównym zmartwieniem jest to, czy programowanie genetyczne jest aktywną dziedziną badań i ma obiecujące zastosowania w praktyce. Wydaje się, że w dziedzinie uczenia maszynowego sieci neuronowe są głównym hasłem, o których wspominają dziś główne wiadomości, ale nigdy nie słyszałem o podobnej „historii sukcesu” programowania genetycznego.
2
Czy istnieje jakiś standard eksperymentalnego porównywania środowisk wykonawczych?
Moja sytuacja Piszę artykuł prezentujący moduł oprogramowania, który opracowałem i chcę porównać jego środowisko wykonawcze z innymi modułami dla tego samego zadania. Zdaję sobie sprawę z wad eksperymentów w środowisku uruchomieniowym , ale proszę założyć, biorąc pod uwagę, że w moim przypadku nie można tego obejść. (Potrafię teoretycznie wydedukować niektóre …
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.