Algebra obliczeniowa
Prowadzący
Damian Orlef [orlef.damian@gmail.com]
Opis
Na warsztatach zajmiemy się tym, co kryje się pod niepozornym tematem układów równań wielomianowych. Przede wszystkim będziemy dążyć do odpowiedzi na pytanie, jak można je rozwiązywać algorytmicznie, zakładając, że potrafimy w jakiś sposób rozwiązywać równania z jedną niewiadomą. Zaczniemy od wyróżnienia wygodnej dla nas reprezentacji: nauczymy się znajdować tzw. bazy Groebnera. Ta wiedza pozwoli nam m.in. wyciągać wnioski o wynikaniu pewnych równań z innych, a ją z kolei można z łatwością przełożyć na automatyczne dowodzenie twierdzeń w geometrii euklidesowej.
Ciekawe będą nie tylko nasze wyniki, ale też sposób ich otrzymania, np. już sam problem dzielenia wielomianów
wielu zmiennych z resztą doprowadzi nas do ładnej kombinatoryki o smaku geometrii dyskretnej
Zajmiemy się też, niejako po drodze, bardzo ładnymi związkami między zbiorami rozwiązań a samymi równaniami. Możliwe, że sami nie zauważymy, kiedy zboczymy na ścieżki geometrii algebraicznej. Na warsztatach omówimy też bardziej fragmentarycznie inne ciekawe zagadnienia dotyczące wielomianów. Przekonamy się np. być może, jak na tw. Pascala można spojrzeć z perspektywy samych równań i tak też je udowodnić, bez użycia brutalnej siły. Więcej potencjalnych ciekawostek w programie zajęć.
Program i forma zajęć
Program będzie się zawierał w sumie następujących tematów:
- ideały wielomianów
- algorytm dzielenia wielomianów z resztą w przypadku wielu zmiennych
- bazy Groebnera: istnienie i znajdowanie, twierdzenie Hilberta o bazie
- rozwiązywanie układów równań, może rugownik
- Nullstellensatz i jego wersja rzeczywista
- tw. Bezout dla wielu zmiennych, tw. Pascala
- teoria niezmienników, np. wielomiany symetryczne
- lemat Schwartza-Zippela, czyli o szczypcie losowości
- geometria tropikalna
- lemat Baszy
Same warsztaty będą polegały na rozwiązywaniu dosyć elementarnych zadań (przez uczestników!), które doprowadzą nas do dosyć sporego zrozumienia własności układów równań, jak i rozważanych algorytmów. Zaprezentuję również
przykładowy darmowy program(y), który ma zaimplementowane omawiane procedury. Zaproponuję zadania do rozwiązania
za ich pomocą w czasie poza zajęciami (w tym takie kryjące w sobie ciekawe matematyczne historie), ale chętnie pomogę i będę dostępny do konsultacji. Polecać też będę zmierzenie się z problemem implementacji omawianych procedur.
Wymagania
Chciałbym, żeby każdy wiedział, że jest coś takiego jak liczby zespolone i co to jest wielomian jednej zmiennej. Tych/te rzeczy nauczą/sprawdzą zadania kwalifikacyjne i skrypt, który się pojawi niedługo po nich. Przyda się wiedzieć, że wielomian jednej zmiennej ma nie więcej pierwiastków, niż stopień. Bardzo okazjonalnie może zróżniczkujemy jakiś wielomian, a potencjalnie skorzystamy gdzieś z wyznaczników macierzy, ale jeśli tak, to przytoczymy potrzebne własności. W skrypcie napiszę też definicje i przykłady paru prostych przydatnych pojęć, np. ideału wielomianów i warto je będzie poznać przed zajęciami, choć na samych warsztatach zostaną przypomniane.
Poza tym może wśród zadań pojawić się dowód jakiegoś prostego faktu, którego będziemy już używać na zajęciach jako znanego, żeby się nie zanudzić przy rozpisywaniu dowodu (ale sam fakt przytoczę).
Skrypt
Zachęcam do lektury skryptu, w którym podałem ważne dla nas definicje. Link.
Skrypt może ulec aktualizacji o nowy materiał, ale nie będę go wymagał.
Zadania kwalifikacyjne
Są tutaj. Należy rozwiązać co najmniej 4 zadania z "zadań podstawowych". Przy tym założeniu, kwalifikację gwarantuję od 11 punktów, ale być może nie będzie trzeba mieć ich tylu. Zachęcam do zrobienia wszystkich zadań, nawet jeśli nie chce się ich spisywać i wysyłać.
Do 15 czerwca być może dopiszę jeszcze parę zadań, ale z zachowaniem powyższych warunków i punktacji
za zadania istniejące.
Rozwiązania proszę przysyłać na adres [orlef.damian@gmail.com], z tytułem zaczynającym się od
"[WWW10kwalifikacja]", najlepiej w formacie PDF (a na pewno nie chcę docx). Można wysyłać wielokrotnie rozwiązania tych samych zadań, postaram się sprawdzać na bieżąco.
Zadania można wysyłać do 4 lipca 2014, do godziny 23:59.
Kontakt
W razie wszelkich pytań piszcie na [orlef.damian@gmail.com], ciekawość jest mile widziana!