Przeskocz do treści

Delta mi!

  1. obrazek

    Teoria liczb Drobiazgi

    Rozsądnego algorytmu brak

    Na obrazku widać przenumerowanie szesnastu z 17 równo rozmieszczonych punktów na okręgu. Obok "normalnych" czarnych numerków podano dziwnie rozmieszczone czerwone. Zrobiono to w ten sposób, że nawinięto na ten okrąg półprostą, na której zaznaczono punkty odpowiadające kolejnym potęgom 3.

  2. Algorytmy Co to jest?

    Algorytm faktoryzacji Shora

    W 1994 roku Peter Shor, pracujący wówczas w Bell Labs w New Jersey, pokazał, jak przy użyciu hipotetycznego komputera kwantowego rozłożyć w czasie wielomianowym dowolną liczbę naturalną na czynniki pierwsze. W tamtym czasie algorytmy kwantowe dopiero raczkowały. To właśnie odkrycie Shora spowodowało wielki rozwój tej dziedziny. Społeczność informatyków zrozumiała, że gdyby udało się zbudować komputer kwantowy rozsądnej wielkości, to świat stałby się istotnie inny. Nie jest bowiem znany żaden algorytm dla problemu faktoryzacji, czyli rozkładu na dzielniki pierwsze, który działa w czasie wielomianowym na komputerze klasycznym. Co więcej, nawet nie znaleziono algorytmu losowego, który z dużym prawdopodobieństwem w zazwyczaj niedługim czasie faktoryzuje liczbę: nie jest po prostu znana zupełnie żadna rozsądna heurystyka...

  3. Algebra

    Combinatorial Nullstellensatz w teorii liczb

    W Delcie 7/2017 przedstawiliśmy kilka "olimpijskich" zastosowań twierdzenia Combinatorial Nullstellensatz. Okazuje się, że zamiast "zwykłych" wielomianów wielu zmiennych możemy rozważać wielomiany o współczynnikach będących resztami z dzielenia przez pewną liczbę pierwszą |p; z dodawaniem i mnożeniem modulo p: Poniżej przedstawimy trzy klasyczne twierdzenia, których proste dowody są oparte na Combinatorial Nullstellensatz w wersji "resztowej". Twierdzenia te są szczególnie bliskie zastosowaniom olimpijskim.

  4. obrazek

    Teoria liczb Mała Delta

    Obsesja dużych liczb

    Kiedy miałem kilka, kilkanaście lat, wraz ze starszym bratem często graliśmy w grę. Należało w swojej kolejce podać liczbę większą od wskazanej przez poprzednika. Przegrywał oczywiście ten, kto nie był w stanie podać liczby większej. Czasami ponosiła nas fantazja i mówiliśmy "nieskończoność" albo "nieskończoność plus nieskończoność". Dziś już wiem, że nieskończoność liczbą nie jest, a działania na nieskończonościach są bardziej wyrafinowane, niż podejrzewałem. Gdyby i Tobie, drogi Czytelniku, przyszło kiedyś wymienić (albo usłyszeć) jakąś dużą liczbę, możesz sięgnąć do poniższej listy. Nie są to bowiem byle jakie liczby...

  5. Teoria liczb

    Liczby pierwsze jako niewiadome

    W historii ludzkiego poznania mało jest tak fascynujących pojęć jak liczby pierwsze. Chociaż dzisiaj wiemy o nich znacznie więcej niż 120 lat temu, to jeszcze więcej dotyczących ich pytań pozostaje bez odpowiedzi. Celem tej notki jest pokazanie, że trudno jest ocenić na pierwszy rzut oka, czy pytanie dotyczące liczb pierwszych jest łatwe, czy też bardzo trudne - poza zasięgiem współczesnej nauki.

  6. Teoria liczb

    Dywany Antoniego - nie tylko bajka o pewnych zastosowaniach ciągu Fibonacciego

    Dawno, dawno temu, za drugą górą, za trzecią rzeką żył sobie królewicz Leonardo pochodzący ze szlachetnego rodu Fibonaccich. No, może nie całkiem królewicz, ale piąty syn dyplomaty włoskiego. Może nie całkiem za trzecią rzeką, bo urodził się za ósmą doliną i trzynastoma bagnami, dokładniej w Pizie w 1175 roku. Zatem przynajmniej rzeczywiście żył dawno, dawno temu. Choć w pewnym sensie żyje do dzisiaj w swoich uczniach, bowiem wieść o liczbach Fibonacciego rozeszła się po świecie i szumi o nich niejeden las...

  7. Teoria liczb

    Kongruencje z królikiem

    Artykuł o powyższym tytule wypada rozpocząć od przypomnienia, czym są kongruencje. Jeśli dwie liczby naturalne |a i b dają tę samą resztę z dzielenia przez liczbę naturalną n (innymi słowy, jeśli |a− b jest podzielne przez n ), uczenie jest stwierdzić, że a i b przystają do siebie modulo n i fakt ten zanotować jako a ≡ b modn: W tym kontekście znaczek " ≡ " (lub raczej to, co on sobą reprezentuje) nazywamy właśnie kongruencją.

  8. Teoria liczb

    Prawda o matematykach

    Jakie jest największe miasto na świecie? Czy wirus jest organizmem żywym? Jaki jest najpiękniejszy obraz Tycjana? Są to proste pytania, na które nie ma jednoznacznej odpowiedzi. Przyczyną jest brak jasno określonych kryteriów. Jedną z cech wyróżniających matematykę spośród innych dziedzin życia i nauki jest to, że każde pojęcie ma swoją precyzyjną definicję. Wydaje się więc, że na każde pytanie matematyczne jest jednoznaczna odpowiedź, którą można formalnie uzasadnić. W konsekwencji, nic nie jest brane "na wiarę". Okazuje się, że nie do końca tak jest!

  9. Algebra

    Najłatwiejsze zadanie?

    Na drugim etapie tegorocznej Olimpiady Matematycznej pojawiło się pewne zadanie. Pojawiło się ono na zawodach z numerem 1 i (zgodnie z oczekiwaniami) okazało się bardzo łatwe - rozwiązała je znacząca większość uczestników. Przedstawimy szkic rozwiązania... x

  10. Teoria liczb

    Bity w szufladkach

    Tak zwana zasada szufladkowa Dirichleta, jakże lubiana przez rozmaite komitety olimpiad matematycznych, łączy w sobie dwie atrakcyjne cechy. Z jednej strony jest tak prosta, że nawet dziecko w przedszkolu jest w stanie ją zrozumieć, z drugiej zaś zawiera zupełnie nieoczywisty element niekonstruktywny. Głosi ona mianowicie, że wkładając do n szuflad więcej niż n przedmiotów, mamy pewność, że w którejś szufladzie będą co najmniej dwa obiekty. W której - nie wiadomo, ale na pewno w którejś.