Pytania otagowane jako proof-techniques

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.

1
Jak udowodnić poprawność algorytmu losowego?
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 metodą iteracyjną, która utrzymuje losowość listy przy każdym wstawieniu. W pseudokodzie funkcja …
4
Czy w logice konstruktywistycznej istnieją niezdecydowane języki?
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 Turinga i języków formalnych? Zauważam, że prawie każdy …
1
Jak pokazać, że L = L (G)?
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 pożądane słowa. Często możemy dyskutować na wysokim szczeblu, dlaczego …
1
Jak napisać dowód przy użyciu indukcji na długości ciągu wejściowego?
W moim kursie teorii obliczeń wiele naszych problemów wiąże się z wykorzystaniem indukcji na długości łańcucha wejściowego do udowodnienia twierdzeń o automatach skończonych. Rozumiem indukcję matematyczną, ale kiedy pojawiają się struny, naprawdę się potykam. Byłbym bardzo wdzięczny, gdyby ktoś krok po kroku robił taki dowód. Oto przykładowy problem (ćwiczenie 2.2.10 …
1
Rozwiązywanie dziel i zdobywaj rekurencje, jeśli współczynnik podziału zależy od
Czy istnieje ogólna metoda rozwiązania problemu ponownego wystąpienia formularza: T(n)=T(n−nc)+T(nc)+f(n)T(n)=T(n−nc)+T(nc)+f(n)T(n) = T(n-n^c) + T(n^c) + f(n) dla c&lt;1c&lt;1c < 1 lub bardziej ogólnie T(n)=T(n−g(n))+T(r(n))+f(n)T(n)=T(n−g(n))+T(r(n))+f(n)T(n) = T(n-g(n)) + T(r(n)) + f(n) gdzie g(n),r(n)g(n),r(n)g(n),r(n) są niektórymi funkcjami subliniowymi nnn . Aktualizacja : Przejrzałem linki podane poniżej, a także przejrzałem wszystkie relacje powtarzalności …
1
Rygorystyczny dowód słuszności założenia
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) = T\left(\left\lfloor \frac{n}{2} \right\rfloor\right) + T\left(\left\lceil \frac{n}{2} \right\rceil\right) + f(n) do T′(n)=2T′(n2)+f(n)T′(n)=2T′(n2)+f(n)\qquad T'(n) = 2 T'\left(\frac{n}{2}\right) + f(n) biorąc …
2
Jak opisywać algorytmy, je udowadniać i analizować?
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 mieszanego z krokami i goto do opisywania algorytmu, i wykorzystuje schematy blokowe do łatwiejszego zobrazowania …
4
Pokazuje, że problem w X nie jest X-Complete
Egzystencjalna teoria Real jest w PSPACE , ale nie wiem, czy to jest PSPACE zupełnych . Jeśli uważam, że tak nie jest, jak mogę to udowodnić? Mówiąc bardziej ogólnie, biorąc pod uwagę problem z pewną klasą złożoności X , jak mogę pokazać, że nie jest to X-Complete ? Na przykład …
5
Jak udowodnić, że problem NIE jest NP-Complete?
Czy istnieje jakaś ogólna technika dla udowodnienia, że ​​problem NIE jest NP-Complete? Dostałem to pytanie na egzaminie, które poprosiło mnie o wykazanie, czy jakiś problem (patrz poniżej) jest NP-Complete. Nie mogłem wymyślić żadnego prawdziwego rozwiązania, a właśnie udowodniłem, że było w P. Oczywiście nie jest to prawdziwa odpowiedź. NP-Complete jest …
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.