Twierdzenie matematyczne

Z Nonsensopedii, polskiej encyklopedii humoru

Skocz do: nawigacji, szukaj

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.

[edytuj] Cele tworzenia twierdzeń matematycznych

  • 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ą.

[edytuj] Przykład twierdzenia matematycznego

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:

[edytuj] Dowód

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!

Nasze strony
Przyjaciele