Pytania otagowane jako induction

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 …
3
Czy indukcja ścieżki jest konstruktywna?
Czytam poprzez książki hott i mam trudności z indukcją ścieżki. Kiedy patrzę na typ w sekcji 1.12.1 : nie mam problemu ze zrozumieniem, co to znaczy (właśnie napisałem typ z pamięci, aby to sprawdzić).ind=A:∏C:∏x,y:A(x=Ay)→U((∏x:AC(x,x,reflx))→∏x,y:A∏p:x=AyC(x,y,p)),ind=A:∏C:∏x,y:A(x=Ay)→U((∏x:AC(x,x,reflx))→∏x,y:A∏p:x=AyC(x,y,p)),\text{ind}_{=_A}:\prod_{C:\prod\limits_{x,y:A}(x=_Ay)\to \mathcal{U}} \left( \left(\prod_{x:A}C(x,x,\text{refl}_x)\right) \to \prod_{x,y:A}\prod_{p:x=_Ay} C(x,y,p) \right), Mam problem z następną samą instrukcją: moje pierwsze wrażenie …
3
Czy „indukcyjne” i „rekurencyjne” mają bardzo podobne znaczenia?
Czy „indukcyjne” i „rekurencyjne” oznaczają bardzo podobne? Na przykład, jeśli istnieje algorytm, który określa wektor n-dim przez określenie jego pierwszych elementów k + 1 na podstawie wyznaczonych pierwszych elementów k i jest inicjalizowany za pomocą pierwszego składnika, czy nazwałbyś go działaniem rekurencyjnym lub indukcyjnym? Używam „rekurencyjnie”, ale dziś ktoś powiedział …
1
Co to jest indukcja indukcyjna?
Co to jest indukcja indukcyjna ? Zasoby, które znalazłem to: książka HoTT na końcu rozdziału 5.7. Artykuł nLab artykuł zatytułowany Definicje indukcyjno-indukcyjne ten post na blogu wspomina także o typach indukcyjno-indukcyjnych Pierwsze dwa odniesienia są dla mnie za krótkie, a dwa ostatnie są zbyt techniczne. Czy ktoś może to wytłumaczyć …
3
Próbuję zrozumieć ten dowód poprawności Quicksort
Ten dowód jest dowodem indukcyjnym i wygląda następująco: P (n) jest twierdzeniem, że „Quicksort poprawnie sortuje każdą tablicę wejściową o długości n”. Przypadek podstawowy: każda tablica wejściowa o długości 1 jest już posortowana (blokada P (1)) Krok indukcyjny: fix n => 2. Napraw niektóre tablice wejściowe o długości n. Trzeba …
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.