Przeskocz do treści

Delta mi!

Loading
  1. Zastosowania matematyki

    Rozbijanie sieci terrorystycznych za pomocą teorii gier

    Mimo licznych działań skierowanych na zwalczanie terroryzmu wiele organizacji terrorystycznych wciąż się powiększa. Aby poradzić sobie z tym problemem, agencje bezpieczeństwa poszukują nowych sposobów analizy pozwalających lepiej zrozumieć strukturę tych organizacji. Jednym z problemów jest zidentyfikowanie kluczowych członków organizacji terrorystycznej przy użyciu informacji jedynie o tym, jak wygląda sieć terrorystyczna - dzięki temu agencje bezpieczeństwa mogłyby skupić swoje ograniczone zasoby na tych jednostkach. W tym artykule omówimy nowe podejście do tego problemu oparte na teorii gier.

  2. Teoria grafów Drobiazgi

    Cykle Hamiltona na wielościanach foremnych

    Zadanie 44 w książce 100 zadań Hugona Steinhausa dotyczy zamkniętych dróg po krawędziach wielościanu foremnego, które przechodzą dokładnie jeden raz przez każdy wierzchołek, czyli złożonych z krawędzi cykli Hamiltona. Chodzi o to, aby znaleźć wszystkie kształty takich cykli i policzyć, ile ich jest (z dokładnością do położenia) dla każdego wielościanu foremnego.

  3. Zastosowania matematyki

    Demokracja i (NP-)trudne problemy

    Podczas XXVII Kongresu Matematycznego, odbywającego się w Seulu między 13 a 21 sierpnia 2014 roku, prestiżową Nagrodę Nevanlinny (informatyczny odpowiednik Medalu Fieldsa) otrzymał pracujący w USA hinduski informatyk Subhash Khot. W laudacji poświęconej wynikom Khota jego mentor i współautor wielu prac, Sanjeev Arora, wspomniał o przełomowym wyniku uzyskanym przez profesora Uniwersytetu Warszawskiego, Krzysztofa Oleszkiewicza wraz z Elchananem Mosselem i Ryanem O'Donnellem...

  4. Zastosowania matematyki

    O modelowaniu przydziału częstotliwości za pomocą kolorowania grafów

    Teoria grafów to gałąź matematyki, do której powstania impuls dało liczące sobie już ćwierć tysiąclecia słynne zagadnienie mostów królewieckich, rozwiązane przez Leonharda Eulera. Osobiście lubię patrzeć na matematykę nie tylko jako na zbiór problemów ciekawych samych w sobie, ale również jak na model rzeczywistości, narzędzie pozwalające efektywniej radzić sobie z rzeczywistymi zmartwieniami. Obecnie teoria grafów staje się jednym z najpopularniejszych takich narzędzi, używanym chętnie przez matematyków (na rzecz innych gałęzi tej nauki), informatyków, fizyków, chemików, a nawet socjologów. Niniejszy artykuł ma na celu przedstawienie tego, jak zagadnienie kolorowania grafów służyć może za narzędzie przydatne w przydzielaniu częstotliwości nadajnikom w jednym z modeli sieci radiowej.

  5. Teoria grafów

    Kafelkowanie prostokątów i grafy planarne

    Zajmijmy się następującym klasycznym zadaniem: należy pokryć kwadrat jednostkowy kwadratowymi kafelkami o różnych bokach tak, aby żadne dwa kafelki nie nachodziły na siebie. Czytelnik może spróbować poszukać takiego kafelkowania metodą prób i błędów, ale na pierwszy rzut oka nie jest jasne, czy pokrycie o żądanych własnościach w ogóle istnieje...

  6. obrazek

    Geometria

    Elektryzująca metryka pingpongowa

    Wśród wielu typów zagadnień matematycznych bardzo sobie cenię takie, które po wierzchu są elementarne, łatwe na początku i dające się rozwiązać nietypowymi, efektownymi, niecodziennymi metodami. Dobrze jest też, gdy zadania te są wierzchołkiem pewnej góry lodowej, albo – stosując inne porównanie – są początkiem ścieżki wiodącej nas w nieznane.

  7. Gry, zagadki, paradoksy

    Gra Grim i twierdzenie Sprague’a–Grundy’ego

    Pewnie część czytelników Delty zna grę Nim – zarówno jej zasady, jak i właściwą dla niej strategię wygrywającą. W tym artykule chcemy przedstawić inną grę grafową. Grę o prostych zasadach, ale trudniejszą niż Nim do dokładnego przeanalizowania.  grą jest – stworzony przez Jamie Peabody i Karen Willis – Grim. Podamy efektywny sposób orzekania, który gracz ma strategię wygrywającą. Co najciekawsze, można go zastosować do szerokiej klasy tego typu gier dwuosobowych, zawierającej Grima i Nima.

  8. obrazek

    Rys. 1

    Rys. 1

    Algorytmy

    Bardzo oszczędne drzewa (I)

    Wiele struktur danych w komputerze można reprezentować w postaci drzewa binarnego. Aby przechować takie drzewo w pamięci komputera, należy dla każdego węzła zapamiętać numer jego lewego i prawego syna oraz, jeśli to potrzebne, numer węzła będącego jego ojcem. Wystarczą nam do tego trzy tablice.

  9. Algorytmy

    Skojarzenia...

    Ten numer Delty jest zdominowany przez tematykę skojarzeń w grafach. Dla przypomnienia: graf nieskierowany to zbiór wierzchołków połączonych krawędziami, skojarzenie zaś w tym grafie to taki podzbiór krawędzi math  że każdy wierzchołek grafu jest incydentny z co najwyżej jedną krawędzią z  math

  10. Algorytmy Informatyczny kącik olimpijski

    Dwa przyjęcia

    W niedawno wydanej książce W poszukiwaniu wyzwań – zbiorze zadań z konkursów programistycznych – Filip Wolski opisał rozwiązanie zadania Dwa przyjęcia z finału XII Olimpiady Informatycznej. W zadaniu tym występuje math osób, z których niektóre się znają (wiemy które). Chcemy podzielić ten zbiór na dwa rozłączne podzbiory (przyjęcia) w taki sposób, aby zmaksymalizować liczbę osób, które mają parzystą liczbę znajomych na przyjęciu, na którym przebywają...

  11. Matematyka Deltoid

    Ekstrema

    W wielu problemach matematycznych warto rozważać elementy ekstremalne – największe, najkrótsze, najbliższe... Metoda ta bywa często przydatna w zadaniach dotyczących punktów płaszczyzny lub grafów, czyli punktów łączonych liniami.

  12. Algorytmy

    Jak złapać terrorystę?

    Któż z nas nie bawił się jako dziecko w chowanego? Zabawa ta sprawia dzieciom wiele radości, mimo że z algorytmicznego punktu widzenia jest bardzo prosta. Jeżeli bowiem wszyscy ukrywający się czekają uczciwie w swoich kryjówkach, to zawsze uda się ich znaleźć – wystarczy, jeżeli szukający przejrzy wszystkie miejsca.