Harmonogram zajęć MiNI Akademii Matematyki w pierwszej połowie roku 2023

14.04.2023, godz.15.30 Gabriel Pietrzkowski, Co wynika z wzoru Picka? Finał Konkursu Matematycznego,

Udowodnimy zależność łączącą pole powierzchni wielokąta prostego, którego wierzchołki są punktami kratowymi na płaszczyźnie, a liczbą punktów kratowych zawartych w jego wnętrzu i na jego brzegu.

22.04.2023, godz. 14.00, Anna Zamojska Dzienio, Czym jest obliczalność?

Teoria obliczalności zajmuje się badaniem, jakie problemy są rozstrzygalne, czyli co można obliczyć w sposób efektywny, a jeszcze inaczej: co można rozwiązać za pomocą komputera. Dzięki wynikom uzyskanym m.in. przez Gödla, Churcha, Turinga już w latach 30-tych XX wieku (a więc przed erą komputerów!) wiadomo, że istnieją problemy w matematyce, które nie są rozstrzygalne. Spróbujemy zrozumieć to zjawisko. Dowiemy się także, dlaczego matematycy zainteresowali się tą tematyką na początku XX wieku. Podczas warsztatów pogłębimy rozumienie pojęcia funkcji obliczalnej, konstruując maszyny Shoenfielda dla wybranych funkcji. Będziemy więc programować za pomocą kartki i ołówka (lub tablicy i kredy).

13.05.2023, godz. 14.00, Konstanty Szaniawski, Kiedy zachłanność popłaca

Rozwiązanie wielu problemów optymalizacyjnych można skonstruować interacyjnie tzn. krok po kroku. Jeśli w każdym kroku wybieramy element lub sposób rozbudowy, który w największym stopniu poprawi aktualne rozwiązanie to mówimy, że stosujemy podejście zachłanne. Dla wielu problemu podejście zachłanne daje optymalne rozwiązanie, jeśli kryterium zachłanności jest odpowiednio dobrane. Oczywiście tak nie jest zawsze, a zdarza się, że algorytm zachłanny jest gwarancją porażki. Okazuje się jednak, że potrafimy rozróżnić problemy, dla których daje optymalne rozwiązanie od tych dla których zachłanne rozwiązanie optymalne być nie musi. Szalenie pomocne są przy tym matroid - struktura matematyczna, którą nie wszyscy dostrzegają na co dzień. Pokażemy na przykładach szeregowania zadań, planowania harmonogramu, kompresji tekstu, kiedy algorytm zachłanny daje najlepsze wyniki i co to ma wspólnego z matroidami.

3