FANDOM


Twierdzenie matematycznebełkot pseudonaukowy osadzony w świecie matematyki, tzw. „królowej nauk bezużytecznych”. Zdanie składające się w 60% procentach ze słów absolutnie niezrozumiałych i nieznanych dla zwykłych ludzi, w 35% z dziwnych znaczków, których próżny trud szukać na klawiaturze oraz w 5% z zaimków.

Cele tworzenia twierdzeń matematycznych edytuj

  • Pobieranie grantów naukowych.
  • Budowanie podstaw dla tworzenia bardziej zaawansowanych twierdzeń, tak by koledzy z wydziału też mogli pobierać granty.
  • Uwalanie studentów.
  • Pisanie nikomu niepotrzebnych prac naukowych.
  • Organizowanie konferencji naukowych, których jedynym prawdziwym celem jest uczestniczenie wygłaszających prelekcje w bankietach ze szwedzkim stołem i darmową wódą.

Przykład twierdzenia matematycznego edytuj

Niech n będzie potęgą liczby rzeczywistej b, takiej, że $ b>1 $, a f niech będzie bijekcją na zbiór półpełny liczb zespolonych odwrotnie przekształconych. Jeśli dla pewnej dodatniej liczby całkowitej i funkcja T jest zdefiniowana następująco:

$ T(n)=\left\{ \begin{matrix} \ \Theta (1) &: n\ =\ 1 \\ \ a\cdot T(\frac{n}{b}) + f(n)&:n\ =\ b^i \end{matrix} \right. $

to

$ \! T(n)\ =\ \Theta (n^{log_ba})\ +\ \sum_{j = 0}^{\log_bn-1} a^j\cdot f(\frac{n}{b^j}) $

Nic z tego nie rozumiesz? Spokojnie, zobacz jak wygląda dowód prawdziwości tego ustrojstwa:

Dowód edytuj

Korzystając z oszacowania z lematu Pitagorasa dla sumy interpolowanych wielomianów sacharozy pokażemy, że dla kolejnych przypadków zachodzi:

  • $ \! T(n)\ =\ \Theta (n^{log_ba})\ +\ O(n^{log_ba})\ =\ \Theta(n^{log_ba}) $
  • $ \! T(n) = \Theta (n^{log_ba}) + \Theta(n^{log_ba}\cdot \ln\ n) = \Theta(n^{log_ba}\cdot \ln\ n) $
  • $ \! T(n) = \Theta (n^{log_ba}) + \Theta(f(n)) = \Theta(f(n)) $, ponieważ $ \! f(n) = \Omega (n^{log_ba + \epsilon}) $

Oczywistym i jakże widocznym jest fakt, że dla dowolnych n (nie będących potęga b) wartość argumentu $ \! \frac{n}{b} $ może oznaczać $ \left\lfloor \frac{n}{b} \right\rfloor $ lub $ \left\lceil\frac{n}{b} \right\rceil $.

Odpowiednio górne i dolne oszacowanie dla funkcji

$ \! T(n) = a\cdot T(\left\lfloor \frac{n}{b} \right\rfloor )\ +\ f(n) $ (1)

i

$ \! T(n) = a\cdot T(\left\lceil \frac{n}{b} \right\rceil )\ +\ f(n) $ (2)

jest banalne arcybanalne do znalezienia, przy wykorzystaniu własności $ \! \left\lfloor \frac{n}{b} \right\rfloor \geqslant \frac{n}{b} $ i $ \! \left\lceil \frac{n}{b} \right\rceil \leqslant \frac{n}{b} $

Równanie rekurencyjne można oszacować z góry w następujący sposób, tak prosty i oczywisty, że nawet czytający ten dowód czterolatkowie wiedzą jak:

Niech

$ n[i]=\left\{ \begin{matrix} \ n &: i=0\\ \ \left\lceil \frac{n[i-1]}{b} \right\rceil &:i>0 \end{matrix} \right. $

Wtedy schodzenie w dół rekursji oznacza jej rekurencyjne wywoływanie kolejno dla argumentów $ \! n[0],\ n[1],\ n[2],\ \cdots $

$ \! T(n) = T(\left\lceil \frac{n}{b} \right\rceil)=\ T(\left\lceil \frac{\left\lceil \frac{n}{b} \right\rceil }{b} \right\rceil) = \cdots $

Korzystając z nierówności $ \left\lceil a \right\rceil \leqslant a\ +\ 1 $ mamy:

  • $ n[0] \leqslant n $
  • $ n[1] \leqslant \frac{n}{b} + 1 $
  • $ n[2] \leqslant \frac{n}{b^2} + \frac{1}{b} + 1 $
  • $ n[3] \leqslant \frac{n}{b^3} + \frac{1}{b^2} + \frac{1}{b} + 1 $
  • $ \cdots $
  • $ n[i] \leqslant \frac{n}{b^i} + \sum_{k = 0}^{i-1} \frac{1}{b^k} < \frac{n}{b^i} + \sum_{k = 0}^{\infty } \frac{1}{b^k} = \frac{n}{b^i} + \frac{b}{b-1} $

Dla $ i = \left\lfloor \log _bn \right\rfloor $

$ \! n[i] = n[\left\lfloor \log _bn \right\rfloor ] < \frac{n}{b^{\left\lfloor \log _bn \right\rfloor}} + \frac{b}{b-1} \leqslant \frac{n}{b^{\log _bn -1}} + \frac{b}{b-1} = \frac{n}{\frac{n}{b}} + \frac{b}{b-1} \in O(1) $

Oznacza to, że dla wywołań rekursji na poziomie co najmniej $ n[\left\lfloor \log _bn \right\rfloor ] $ i większych rozmiar problemu jest stały.

W ten oto sposób kończymy nasz jakże banalny dowód!