Informatyka

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

7
Czy wszystkie języki są kompletne wymienne?
Uwaga: chociaż umiem programować, jestem całkiem początkującym w teorii CS. Zgodnie z tą odpowiedzią Kompletność Turinga jest abstrakcyjną koncepcją obliczalności. Jeśli język jest kompletny Turinga, jest on w stanie wykonać dowolne obliczenia, które może wykonać każdy inny kompletny język Turinga. I każdy program napisany w dowolnym języku kompletne Turinga mogą …
4
Jaka jest różnica między typem a rodzajem?
Uczę się języka programowania Haskell i staram się owinąć głowę, jaka jest różnica między a typea a kind. Jak rozumiem, a kind is a type of type. Na przykład a ford is a type of cari a car is a kind of vehicle. Czy to dobry sposób, aby o tym …
2
Jak udowodnić, że język jest pozbawiony kontekstu?
Istnieje wiele technik, aby udowodnić, że język nie jest pozbawiony kontekstu, ale jak udowodnić, że język jest pozbawiony kontekstu? Jakie są techniki, aby to udowodnić? Oczywiście jednym ze sposobów jest wykazanie gramatyki bezkontekstowej dla tego języka. Czy istnieją jakieś systematyczne techniki znajdowania gramatyki bezkontekstowej dla danego języka? Dla stałych języków, …
2
Ogólna zasada, aby wiedzieć, czy problem może być NP-zupełny
To pytanie zostało zainspirowane komentarzem na StackOverflow . Oprócz znajomości problemów NP-zupełnych z książki Garey Johnson i wielu innych; czy istnieje ogólna zasada, aby wiedzieć, czy problem wygląda jak NP-zupełny? Nie szukam czegoś rygorystycznego, ale czegoś, co działa w większości przypadków. Oczywiście za każdym razem, gdy musimy udowodnić, że problem …
3
Czy język par słów o równej długości, których odległość hamowania wynosi 2 lub więcej, jest pozbawiona kontekstu?
Czy następujący kontekst językowy jest bezpłatny? L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L={uxvy∣u,v,x,y∈{0,1}+,|u|=|v|,u≠v,|x|=|y|,x≠y}L = \{ uxvy \mid u,v,x,y \in \{ 0,1 \}^+, |u| = |v|, u \neq v, |x| = |y|, x \neq y\} Jak wskazał sdcvvc, słowo w tym języku można również opisać jako połączenie dwóch słów o tej samej długości, których odległość młotkowania wynosi …
6
Co jest najbardziej wydajne dla GCD?
Wiem, że algorytm Euclida jest najlepszym algorytmem do uzyskania GCD (wielkiego wspólnego dzielnika) listy dodatnich liczb całkowitych. Ale w praktyce możesz kodować ten algorytm na różne sposoby. (W moim przypadku zdecydowałem się na Javę, ale C / C ++ może być inną opcją). Potrzebuję użyć najbardziej wydajnego kodu w moim …
2
Wersja optymalizacyjna problemów decyzyjnych
To pytanie zostało przeniesione z Teoretycznej wymiany stosów komputerowych, ponieważ można na nie odpowiedzieć w ramach wymiany stosów komputerowych. Migrował 7 lat temu . Wiadomo, że każdy problem optymalizacji / wyszukiwania ma równoważny problem decyzyjny. Na przykład problem najkrótszej ścieżki Optymalizacja / Wersja: Biorąc pod uwagę nieukierunkowane nieważony wykres a …
2
Czy Dominosa NP-Hard?
To pytanie zostało przeniesione z Mathematics Stack Exchange, ponieważ można na nie odpowiedzieć na Computer Science Stack Exchange. Migrował 6 lat temu . Dominosa to stosunkowo nowa gra logiczna. Jest odtwarzany na siatce . Przed rozpoczęciem gry kości domina są umieszczane na siatce (tworząc idealne kafelki ). W następnym kroku …
1
Dwie definicje zrównoważonych drzew binarnych
Widziałem dwie definicje zrównoważonych drzew binarnych, które wyglądają inaczej dla mnie. Drzewo binarne jest zrównoważone, jeśli dla każdego węzła utrzymuje, że liczba wewnętrznych węzłów w lewym poddrzewie i liczba wewnętrznych węzłów w prawym poddrzewie różnią się co najwyżej o 1. Drzewo binarne jest zrównoważone, jeśli dla dowolnych dwóch liści różnica …
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.