Przeskocz do treści

Delta mi!

  1. Gry, zagadki, paradoksy

    Gry

    W wielu grach dla któregoś z graczy istnieje strategia wygrywająca, czyli taka "recepta" na grę, która pozwala zawsze zwyciężyć, niezależnie od ruchów przeciwnika. Jednak strategię taką, nawet jeśli istnieje, nie zawsze łatwo wskazać. Na szczęście często można. Czasem wystarczą do tego proste pomysły typu symetria, czasem zaś potrzebne są metody bardziej wyrafinowane. W niektórych grach nawet bez żadnej strategii wynik jest z góry przesądzony. Ilustrują to poniższe przykłady...

  2. obrazek

    Teoria węzłów

    Okręgi Boromeuszy, czyli matematyk rozplątuje supełki

    Widoczny obok splot trzech rurek to logo włoskiego rodu Boromeuszy. Splot ten ma interesującą własność: rozcięcie i usunięcie dowolnej z tych rurek sprawia, że pozostałe dwie nie są ze sobą w żaden sposób połączone. W tym miejscu pojawia się naturalne pytanie - czy da się skonstruować splot o podobnej własności dla więcej niż trzech rurek?

  3. Planimetria Mała Delta

    Gwiazda potęgowa

    Dawno, dawno temu żył sobie beztrosko król wraz ze swoją piękną córką. Jak to czasem w zbyt szczęśliwych królestwach bywa, pewnego razu czarnoksiężnik przybył na dwór, żeby porwać królewnę i uwięzić ją w swojej upiornej wieży. Zgodnie z zasadami dobrego wychowania mrocznych czarodziei, do których należał, musiał dać mieszkańcom królestwa możliwość ocalenia królewny przed swoim niecnym planem...

  4. Planimetria

    Wpisywanie

    W geometrii dyskretnej przyjęło się mówić, że wielokąt jest wpisany w inny wielokąt, gdy ma wierzchołki na prostych zawierających boki tego drugiego wielokąta. Od czasu Hilberta tego zwrotu używa się i w przypadku "zwyczajnej" geometrii.

  5. 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.

  6. Gry, zagadki, paradoksy

    Gra w sumo

    Czy Czytelnik zna grę w przeciąganie liny? Dwie drużyny ciągną dwa końce liny w przeciwne strony, a wygrywa ta, której uda się przeciągnąć linę na swoją stronę. Ściślej, gra kończy się w momencie wyjścia środka liny (zazwyczaj oznaczonego wstążką) z umówionego pola gry. Matematycy przypisują tę samą nazwę podobnej grze rozgrywającej się w dwóch (i więcej) wymiarach, w której to środek liny może poruszać się w wielu kierunkach, a nie tylko lewo-prawo. Trudno sobie jednak takie przeciąganie wyobrazić, dlatego przyjąłem termin gra w sumo.

  7. obrazek

    Sztuczna inteligencja Co to jest?

    Głębokie uczenie maszyn

    Czy zastanawialiście się kiedyś nad tym, czym jest inteligencja? Większość definicji zakłada posiadanie zdolności do rozumowania, uczenia się, adaptacji do zmieniającego się otoczenia. Najczęściej mówi się o inteligencji ludzi i zwierząt - organizmów mających mózg, a więc organ biologiczny. Czy inteligencja musi być jednak domeną jedynie istot, które uważamy obecnie za żywe? Wielu Czytelników słyszało zapewne również o inteligencji "sztucznej", określanej tak dlatego, że nie występuje ona w sposób naturalny w przyrodzie, ale w emergentny sposób pojawia się w maszynach i algorytmach tworzonych dzięki innej inteligencji, np. człowieka.

  8. Kryptologia

    Kryptologia postkwantowa

    Jednym z ważniejszych osiągnięć informatyki opartej o komputer kwantowy, które zresztą eksponujemy w tym numerze Delty, jest opracowanie efektywnego (wielomianowego od rozmiaru danych) algorytmu na rozkład dużych liczb na czynniki pierwsze. Wspaniały, budzący zachwyt wynik. Nie dość, że przepiękny, korzystający z bardzo ładnego fragmentu matematyki, to jeszcze pozwalający wierzyć, że komputer kwantowy złożony z n kubitów jest istotnie lepszy od komputera klasycznego, zawierającego pamięć o n bitach. Albo inaczej: że (też prezentowany w tym numerze) model obliczeń komputera kwantowego ma istotnie większą siłę wyrazu (przy założeniu wielomianowego czasu działania) niż klasyczny model Turinga czy inne równoważne.

  9. 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...

  10. Zastosowania matematyki

    (Nie)sprawiedliwe wybory

    Ustalenie wspólnego stanowiska przez grupę ludzi wymaga często w pierwszym kroku wyboru metody podjęcia zbiorowej decyzji. Kluczowe stają się wówczas pytania: Jaka metoda jest sprawiedliwa? Jaka metoda najlepiej odzwierciedli preferencje członków grupy?

  11. obrazek

    Algebra

    Symetrie ciał i grupy: teoria Galois

    Poniższa opowieść była na tyle ważna dla młodego, zaledwie dwudziestoletniego, matematyka Évariste'a Galois, że poświęcił ostatni dzień przed pojedynkiem, aby spisać ją w liście do przyjaciela. Niestety, nie dostał od losu szansy na kontynuowanie swoich prac, ale jakiś czas po jego śmierci matematycy zrozumieli znaczenie jego pomysłów. Ślady teorii, z której zarysem Czytelnik zapoznać się może w dalszej części artykułu, odnaleźć można w wielu gałęziach współczesnej matematyki. Jej bezpośrednim następstwem jest wiele efektownych rozwiązań problemów, których ludzkość szukała przez setki lat: nierozwiązalność (przez pierwiastniki) równań wielomianowych stopnia 5 lub wyższego, niekonstruowalność pewnych wielokątów foremnych (cyrklem i linijką), a także niewykonalność klasycznych konstrukcji geometrycznych, czyli podwojenia sześcianu, trysekcji kąta i kwadratury koła.

  12. obrazek

    Rys. 1

    Rys. 1

    Planimetria Deltoid

    Łuki Talesa

    Odcinek AB widać z punktu C pod kątem ff , gdy ?ACB = ff: Z twierdzenia o kątach wpisanych wynika, że jeśli punkty C i D leżą na okręgu po tej samej stronie jego cięciwy AB; to widać ją z C i |D pod tym samym kątem (Rys. 1).

  13. 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.

  14. Geometria Drobiazgi

    Małe Wszechświaty

    Astrofizycy ostatnio twierdzą, że "Wszechświat jest płaski", co w ich żargonie oznacza, iż średnia krzywizna Wszechświata jest równa zeru (i tylko lokalnie jest zakłócana przez grawitację). Jeśli mają rację, to matematyka dowodzi, że Wszechświat przyjmuje jeden z 18 możliwych kształtów.