Wydział Matematyki, Informatyki i Mechaniki UW

Typ Tytuł Opis Dziedzina Termin
Spotkanie festiwalowe Jak rozwiązywać obrazki logiczne?

Obrazek logiczny, zwany też nonogramem, to zadanie polegające na odtworzeniu rysunku na podstawie informacji
o liczbie pól zamalowanych w każdym wierszu i każdej kolumnie. Na zajęciach pokażemy, jak rozwiązywać takie łamigłówki,

generując wszystkie możliwe podziały pewnych liczb na sumę ich nieujemnych składników całkowitych. Policzymy, jak długo

musiałby wykonywać się program komputerowy rozwiązujący takie łamigłówki i jak go usprawnić za pomocą sprytnej graficznej

reprezentacji podziału na składniki.

Nauki matematyczne
  • sob., 2021-09-18 09:30
Spotkanie festiwalowe Metody proporcjonalnego podziału miejsc parlamentarnych

Kiedy myślimy o podziale miejsc parlamentarnych, naszym pierwszym skojarzeniem jest zapewne polityka, a nie matematyka. O ile prowadzenie kampanii wyborczych rzeczywiście należy do świata polityki, o tyle samo liczenie głosów to problem czysto informatyczny/matematyczny. Metoda podziału miejsc parlamentarnych to funkcja (lub algorytm), która za argument przyjmuje zbiór głosów oddanych na poszczególne partie i zwraca wektor opisujący liczbę miejsc parlamentarnych przeznaczonych dla każdej z partii. Dzięki takiemu ujęciu, możemy formalnie analizować i oceniać różne metody podziału miejsc parlamentarnych. Co więcej, możemy starać się uchwycić takie pojęcia jak proporcjonalność czy sprawiedliwość w ściśle matematyczny sposób. To z kolei pozwala nam oceniać, które metody podziału miejsc są sprawiedliwe, a które nie, a w konsekwencji projektować bardziej zaawansowane metody o jeszcze lepszych własnościach.

Nauki matematyczne
  • sob., 2021-09-18 11:00
Spotkanie festiwalowe O podziale łupów pirackich i innych zagadnieniach związanych z podziałami na nie zawsze równe części

Zaczniemy od łamigłówki, w której proste reguły podziału łupów pirackich prowadzą do zaskakujących rozwiązań. Potem pochylimy się nad problemem liczby możliwych podziałów zbioru n-elementowego na rozłączne bloki. Dla małych zbiorów to da się jeszcze ręcznie obliczyć, ale czy istnieje ogólny wzór dla dużych n?

Nauki matematyczne
  • sob., 2021-09-18 12:00
Spotkanie festiwalowe Ile jest części i dlaczego nie tyle, ile się wydaje?

Odpowiemy na kilka pytań kombinatorycznych dotyczących liczby części, które uzyskuje się przy pewnych szczególnych podziałach. Postawimy na pozór oczywiste hipotezy, by następnie je obalić i odkryć, jak jest naprawdę. 

 

Powędrujemy od koła, poprzez prostą i płaszczyznę, aż po przestrzenie wielowymiarowe, przy czym te ostatnie okażą się, wbrew pozorom, najłatwiejsze do zbadania. 

Nauki matematyczne
  • sob., 2021-09-18 13:00
Spotkanie festiwalowe Jak się dzielić, żeby się nie poróżnić, czyli o metodach sprawiedliwego podziału

Na zajęciach zajmiemy się sprawiedliwym podziałem dóbr. To problem, przed którym stajemy wszyscy: dzieci kłócące się o ostatni kawałek tortu, zbójcy dzielący łup czy ministrowie konstruujący budżet państwa. Trudno o bardziej konfliktogenne zajęcie. Czy matematyka może w tym jakoś pomóc?

Opowiem o problemach z podziałem spadku po Babie Jadze, o tym jak krasnoludki dzielą budyń i kroją makowiec i jak trzy osoby o bardzo trudnym charakterze mogą się podzielić pizzą lub drożdżówką tak, żeby wszystkie były zadowolone (a w każdym razie nie miały żalu do pozostałych).

Nauki matematyczne
  • sob., 2021-09-25 10:00
Spotkanie festiwalowe Tajemnica z Talmudu

Jedna z historii w Talmudzie Babilońskim opisuje następującą sytuację. Mężczyzna mający trzy żony umiera. W kontrakcie małżeńskim obiecał im kolejno 100, 200 i 300 starożytnych srebrnych monet. Niestety, gdy umierał jego majątek był zbyt mały, aby spełnić te obietnice. Jak sprawiedliwie rozdzielić majątek między żony? W Talmudzie przedstawione są trzy warianty problemu oraz ich rozwiązania, jednak przez prawie dwa tysiące lat nikt nie rozumiał, jaki jest sens tych rozwiązań i jaką ogólną metodę opisują. Tajemnicę tą rozwiązali dopiero Robert Aumann i Michael Maschler pod koniec XX wieku i o tym opowiemy na wykładzie.

Nauki matematyczne
  • sob., 2021-09-25 11:00
Spotkanie festiwalowe O podziałach na orbity

Rozważać będziemy kolorowania brył i figur geometrycznych, a kolorować będziemy ich wierzchołki, krawędzie lub ściany. Każde takie kolorowanie można utożsamić z funkcją przypisującą każdemu z wierzchołków lub każdej z krawędzi czy ścian element pewnego zbioru kolorów K. Przy takiej definicji trzeba przyjąć, że dwa kolorowania nie są identyczne, innymi słowy – są różne, jeśli pewna ściana, krawędź czy wierzchołek ulegnie pokolorowaniu na inny kolor w jednym kolorowaniu niż w drugim. Liczbę tak rozumianych kolorowań łatwo można policzyć, korzystając z wiedzy szkolnej, ale tak postawiony problem jest mało praktyczny. My jednak przyglądać będziemy się liczbie nie różnych, a rozróżnialnych kolorowań. Za pokolorowane w sposób nierozróżnialny uznamy figury lub bryły, jeśli można jedną z nich przekształcić, na przykład przez pewien obrót, w taki sposób, żeby po tym przekształceniu zobaczyć identyczne kolorowanie jak drugiej. Liczba rozróżnialnych w tym sensie kolorowań jest trudniejsza do znalezienia. Powiemy o kluczowym dla tego problemu pojęciu grupy przekształceń i działaniu tej grupy na zbiorze obiektów podlegających kolorowaniu. Dowiemy się, czym przy działaniu grupy na zbiorze są orbity i dlaczego tworzą one podział interesującego nas zbioru. Przyjrzymy się, dlaczego wskazanie odpowiedniej grupy przekształceń jest konieczne dla ścisłego sformułowania naszego problemu i dlaczego grupa przekształceń, a co za tym idzie i liczba kolorowań, może być inna, gdy rozważamy dziecięcą kolorowankę na papierze, a inna, gdy projekt witraża. Sformułujemy również kluczowe dwa twierdzenia w tej teorii: Twierdzenie Pólyi i prowadzący do niego Lemat Burnside'a, które powiedzą nam, jak liczba orbit wpływa na liczbę kolorowań. Jeżeli czas pozwoli, naszkicujemy dowody tych twierdzeń.

Nauki matematyczne
  • sob., 2021-09-25 12:00
Spotkanie festiwalowe Gra pijanego pułkownika

Na wykładzie przedstawię klasyczny problem współczesnej teorii gier -  grę Pułkownik Blotto. W grze tej dwóch graczy, każdy bez wiedzy o decyzji drugiego gracza, rozdziela swoje oddziały pomiędzy kilka pól bitew. Celem każdego z graczy jest zdobycie przewagi na większej liczbie pól niż przeciwnik. Gra Pułkownik Blotto została zaproponowana przez Emila Borela w 1921 w celu zilustrowania przydatności strategii losowych. Okazuje się, że optymalnym dla każdego z graczy jest losowe wybieranie przydziału oddziałów do pól bitew tak, by być jak najbardziej nieprzewidywalnym dla przeciwnika. Ten prosty model konfliktu ma wiele zastosowań, od oczywistych zastosowań militarnych po rywalizację wyborczą, rywalizację marketingową, czy bezpieczeństwo sieci komputerowych. Na wykładzie opowiem o tym, co wiemy o optymalnych przydziałach losowych dla graczy oraz wspomnę o tym, czego jeszcze nie wiemy.

Nauki matematyczne
  • sob., 2021-09-25 13:00