FANDOM


Przenosimy się na nonsa.pl!

Po ponad trzynastu latach na serwerach Wikii, otrzymaliśmy niespodziewaną wiadomość – Wikia/Fandom zdecydowała o całkowitym usunięciu Nonsensopedii.
Czas na wyniesienie się stąd mamy do 21 kwietnia. Tego dnia strona nonsensopedia.wikia.com przestanie działać. Administracji nie zostało w takiej sytuacji zbyt wiele opcji. Doszliśmy do wniosku, że jedynym sensownym wyjściem jest przeniesienie się na nowy, niezależny hosting.

Ten artykuł znajdziesz na nowej Nonsensopedii tutaj.
Przenosimy się na nonsa.pl!

Po ponad trzynastu latach na serwerach Wikii, otrzymaliśmy niespodziewaną wiadomość – Wikia/Fandom zdecydowała o całkowitym usunięciu Nonsensopedii.
Czas na wyniesienie się stąd mamy do 21 kwietnia. Tego dnia strona nonsensopedia.wikia.com przestanie działać. Administracji nie zostało w takiej sytuacji zbyt wiele opcji. Doszliśmy do wniosku, że jedynym sensownym wyjściem jest przeniesienie się na nowy, niezależny hosting.
Ten artykuł znajdziesz na nowej Nonsensopedii tutaj.


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!