Informatyka

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

3
Algorytm sprawdzający, czy język jest pozbawiony kontekstu
Czy istnieje algorytm / systematyczna procedura sprawdzania, czy język jest pozbawiony kontekstu? Innymi słowy, biorąc pod uwagę język określony w formie algebraicznej (pomyśl o czymś takim jak ), sprawdź, czy język jest pozbawiony kontekstu, czy nie . Wyobraź sobie, że piszemy serwis internetowy, który pomaga uczniom we wszystkich zadaniach domowych; …
1
cięcia gilotynowe a cięcia ogólne
Problemy z cięciem to problemy, w których pewien duży obiekt powinien zostać pocięty na kilka małych obiektów. Na przykład, wyobraź sobie, że masz fabrykę, która współpracuje z dużymi arkuszami surowego szkła, o szerokości i długość L . Istnieje kilku nabywców, z których każdy chce nieograniczoną liczbę małych tafli szkła. Kupujący …
1
Kiedy stosować SAT vs Constraint Satisfaction?
Jeśli mam trudny problem, jednym ze standardowych sposobów jest wyrażenie go jako instancji SAT i próby uruchomienia na nim solvera SAT. Innym standardowym podejściem jest wyrażenie go jako problemu satysfakcji z ograniczeń i próba użycia solvera CSP. Obaj czują się nieco niejasno pod względem tego, jakie problemy można naturalnie wyrazić …
3
Czy istnieje teoria hierarchii wyjątków?
Znam kilkanaście języków programowania, które w pewien sposób mają wyjątki, ale doszedłem do wniosku, że mam dwie „patologiczne” tendencje. Wydaje się, że nie ma wspólnego wzorca lub hierarchii wyjątków. Każdy język w zasadzie rozwija własną wersję, a jeśli wyjątki staną się standardem, wówczas wyjątki, które można znaleźć w standardzie, byłyby …
1
Czy układanki „zero-jedynkowe” są kompletne NP?
Interesuje mnie niewielki wariant układania płytek, układanka „układanka”: każda krawędź (kwadratowej) płytki jest oznaczona symbolem z , a dwie płytki można umieścić obok siebie do siebie iff symbol na przeciwległej krawędzi jednego kafelka to k, a symbol na przeciwległej krawędzi drugiego kafelka to ˉ k , dla niektórych k ∈ …
2
Co jest trudniejsze: tasowanie posortowanej talii lub sortowanie potasowanej talii?
Masz tablicę różnych elementów. Masz dostęp do komparatora (funkcja czarnej skrzynki, która bierze dwa elementy a i b i zwraca prawdziwy iff a &lt; b ) oraz naprawdę losowe źródło bitów (funkcja czarnej skrzynki nie przyjmuje argumentów i zwraca niezależnie jednakowo losowy bit). Rozważ następujące dwa zadania:nnnaaabbba&lt;ba&lt;ba < b Tablica …
1
Liczba cykli hamiltonowskich na wykresie Sierpińskiego
Jestem nowy na tym forum i jestem tylko fizykiem, który robi to, aby utrzymać swój mózg w dobrej formie, więc proszę okaż łaskę, jeśli nie używam najbardziej eleganckiego języka. Proszę również zostawić komentarz, jeśli uważasz, że inne tagi byłyby bardziej odpowiednie. Próbuję rozwiązać ten problem, dla którego muszę obliczyć liczbę …
2
Jakie są zalety Randomized Quicksort?
W książce algorytmy randomizowane , Motwani i Raghavan otworzyć zapoznaniu się z opisem ich funkcji RandQS - randomizowane Quicksort - przy czym czop, służy do podziału zbioru na dwie części, jest wybierana losowo. Przez jakiś czas dręczyłem nad tym (co prawda trochę słabe) mózgi, ale nie byłem w stanie zobaczyć, …
3
Jak czytać zasady pisania?
Zacząłem czytać coraz więcej prac naukowych dotyczących języków. Uważam to za bardzo interesujące i dobry sposób, aby dowiedzieć się więcej o programowaniu w ogóle. Zazwyczaj jednak pojawia się sekcja, z którą zawsze się zmagam (na przykład część trzecia tego ), ponieważ brakuje mi teoretycznego zaplecza informatycznego: Typ reguł. Czy są …
2
Redukcja wielomianu z dowolnego problemu NP-zupełnego do ograniczonego PCP
Podręczniki wszędzie założyć, że Bounded post Korespondencja Problem jest NP-zupełny (nie więcej niż NN.N indeksy dozwolony z powtórzeń). Nigdzie jednak nie pokazano prostej (jak w czymś, co student może zrozumieć) wielomianowej redukcji czasu z innego problemu pełnego NP. Jednak każda redukcja, o której mogę myśleć, ma charakter wykładniczy (według NN.N …
1
Udowodnienie (nie) wykonalności tego N-tego pierwszego wznowienia
Jak wynika z mojego poprzedniego pytania , bawiłem się hipotezą Riemanna jako zagadnieniem matematyki rekreacyjnej. W trakcie tego procesu doszłam do dość interesującego nawrotu i jestem ciekawa jego nazwy, jej redukcji i podatności na rozwiązywanie luki między liczbami pierwszymi. Krótko mówiąc, możemy zdefiniować odstęp między każdą liczbą pierwszą jako powtórzenie …
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.