Pytania dotyczące ogólnych metod i technik dowodzenia wielu twierdzeń. Pytając o dowód pojedynczego stwierdzenia, zamiast tego użyj tagów odnoszących się do tego, czego dotyczy dowód.
Istnieje wiele pytań dotyczących sposobu analizowania czasu pracy algorytmów (patrz np runtime-analiza i algorytm-analysis ). Wiele z nich jest podobnych, na przykład ci, którzy proszą o analizę kosztów zagnieżdżonych pętli lub algorytmy dzielenia i zdobywania, ale większość odpowiedzi wydaje się...
Słyszałem o indukcji (strukturalnej). Pozwala budować struktury skończone z mniejszych i zapewnia zasady dowodowe dla uzasadnienia takich struktur. Pomysł jest wystarczająco jasny. A co z koindukcją? Jak to działa? Jak można powiedzieć coś rozstrzygającego o nieskończonej strukturze? Są...
Istnieje wiele metod, aby udowodnić, że dany język nie jest regularny , ale co muszę zrobić, aby udowodnić, że jakiś język jest prawidłowy? Na przykład, jeśli otrzymam informację, że jest regularne, jak mogę udowodnić, że następujące jest również regularne?L
W teorii obliczalności i złożoności (i być może w innych dziedzinach) redukcje są wszechobecne. Istnieje wiele rodzajów, ale zasada pozostaje ta sama: pokaż, że jeden problem jest co najmniej tak samo trudny jak jakiś inny problem poprzez odwzorowanie instancji z na równoważne z rozwiązaniem w ....
Planuję uczyć kurs zimowy na różną liczbę tematów, z których jednym będą kompilatory. Teraz natknąłem się na ten problem, myśląc o zadaniach do wykonania przez cały kwartał, ale to mnie zaskoczyło, więc mogę go użyć jako przykładu. public class DeadCode { public static void main(String[] args) {...
Rozumiem dowód nierozstrzygalności problemu zatrzymania (podany na przykład w podręczniku Papadimitriou), oparty na przekątnej. Chociaż dowód jest przekonujący (rozumiem każdy jego krok), nie jest dla mnie intuicyjny w tym sensie, że nie widzę, jak ktoś by go wyprowadził, zaczynając od samego...
Kiedy wyjaśniłem dowód Baker-Gill-Solovay, że istnieje wyrocznia, którą możemy mieć, , oraz wyrocznia, z którą możemy otrzymać P ≠ N P przyjacielowi, pojawiło się pytanie, dlaczego takie techniki nie nadają się do udowodnienia problemu P ≠ N P i nie mogłem udzielić zadowalającej odpowiedzi.P = N...
Mam chciwy algorytm, który, jak podejrzewam, może być poprawny, ale nie jestem pewien. Jak sprawdzić, czy jest poprawny? Jakich technik należy użyć do udowodnienia, że chciwy algorytm jest poprawny? Czy istnieją wspólne wzorce lub techniki? Mam nadzieję, że stanie się to pytaniem referencyjnym,...
Każdy nierozstrzygnięty problem, który znam, należy do jednej z następujących kategorii: Problemy nierozstrzygalne z powodu diagonalizacji (pośrednie samodzielne odniesienie). Problemy te, podobnie jak problem zatrzymania, są nierozstrzygalne, ponieważ można użyć rzekomego decydenta dla języka do...
Biorę kurs złożoności i mam problem z wymyśleniem redukcji między problemami NPC. Jak znaleźć redukcje między problemami? Czy istnieje ogólna sztuczka, której mogę użyć? Jak podejść do problemu, który wymaga ode mnie udowodnienia, że jest nim
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...
Mój problem polega na tym, jak mogę udowodnić, że gramatyka jest jednoznaczna? Mam następującą gramatykę: S→statement∣if expression then S∣if expression then S else SS→statement∣if expression then S∣if expression then S else SS → statement ∣ \mbox{if } expression \mbox{ then } S ∣ \mbox{if }...
Mam dwa sposoby tworzenia listy przedmiotów w losowej kolejności i chciałbym ustalić, czy są one równie uczciwe (obiektywne). Pierwszą metodą, której używam, jest skonstruowanie całej listy elementów, a następnie wykonanie losowania (powiedzmy losowanie Fisher-Yates). Druga metoda jest raczej...
Logika konstruktywistyczna to system, który usuwa Prawo Akceptowanego Środka, a także Podwójną Negację, jako aksjomaty. Jest opisany na Wikipedii tutaj i tutaj . W szczególności system nie dopuszcza dowodu sprzeczności. Zastanawiam się, czy ktoś wie, jak to wpływa na wyniki dotyczące maszyn...
Biorąc pod uwagę problem obliczeniowy, czy naprawdę jest możliwe znalezienie dolnych granic dla takiego obliczenia? Przypuszczam, że sprowadza się to do zdefiniowania pojedynczego kroku obliczeniowego i jakiego modelu używamy jako dowodu, ale biorąc pod uwagę to, czy naprawdę udowadniamy dolną...
Określanie języków formalnych poprzez nadawanie gramatyki formalnej jest częstym zadaniem: potrzebujemy gramatyki nie tylko do opisu języków, ale także do ich analizy, a nawet do właściwej nauki . We wszystkich przypadkach ważne jest, aby gramatyka była poprawna , czyli generowała dokładnie...
Szukam wyjaśnienia, w jaki sposób można udowodnić, że dwa modele obliczeń są równoważne. Czytałem książki na ten temat, z tym wyjątkiem, że pominięto dowody równoważności. Mam podstawowe pojęcie o tym, co to znaczy, że dwa modele obliczeń są równoważne (widok automatów: jeśli akceptują te same...
W matematyce istnieje wiele dowodów na istnienie, które nie są konstruktywne, więc wiemy, że istnieje pewien obiekt, chociaż nie wiemy, jak go znaleźć. Szukam podobnych wyników w informatyce. W szczególności: czy istnieje problem, który możemy udowodnić, że można go rozstrzygać bez pokazywania...
Przed przeczytaniem „Sztuki programowania komputerowego” (TAOCP) nie zastanawiałem się głęboko nad tymi pytaniami. Używałbym pseudokodu do opisywania algorytmów, rozumienia ich i szacowania czasu działania tylko o rzędach wzrostu. TAOCP gruntownie zmienia zdanie. TAOCP używa angielskiego...
Twierdzenie Master jest pięknym narzędziem do rozwiązywania pewnych rodzajów nawrotów . Jednak często nakładamy połysk na integralną część podczas jej nakładania. Na przykład podczas analizy Mergesort z radością wychodzimy T(n)=T(⌊n2⌋)+T(⌈n2⌉)+f(n)T(n)=T(⌊n2⌋)+T(⌈n2⌉)+f(n)\qquad T(n) =...