Algorytmika praktyczna lato 2024/25

Język wykładowy Polski
Opiekun Artur Kraska
Liczba godzin 30 (wyk.) 30 (ćw.)
Rodzaj Informatyczny 1
ECTS 6
Polecany dla I roku Tak
Egzamin Tak

Opis przedmiotu:

Przedmiot ten jest drugim krokiem (zaraz po *wstępie do informatyki*) przygotowującym do startu w zawodach algorytmicznych takich jak Olimpiada Informatyczna, ICPC czy Codeforces. Wiedza ta przydatna będzie również na innych zajęciach, na przykład na *metodach implementacji algorytmów*. Na przedmiocie przedstawimy uczestnikom klasyczne algorytmy oraz techniki programistyczne, używane na takich zawodach. Głównym zamysłem jest nie tylko poznanie przez nich wybranych algorytmów, ale powinni oni również zdobyć umiejętność ich implementacji oraz zrozumienie na takim poziomie, aby można było je w miarę potrzeby zmodyfikować. Planowo, na wykładzie skupimy się głównie na zrozumieniu idei algorytmów oraz ich poprawności. Za to ćwiczenia będą polegały przede wszystkim na prezentacji swoich implementacji oraz omówieniu jak wpłyną na działanie tych algorytmów poszczególne modyfikacje w kodzie. ##### Planowana tematyka wykładu: * Podstawy teorii liczb * Sumy zbiorów rozłącznych (Find Union) * Techniki o złożoności pierwiastkowej * Programowanie dynamiczne * Drzewa przedziałowe * Znajdowanie najniższego wspólnego przodka w drzewie * Silnie spójne składowe * 2-SAT * Mosty i punkty artykulacji * Szukanie najkrótszych ścieżek w grafach * Haszowanie * Algorytmy tekstowe * Geometria * Podstawy teorii gier ##### Wymagania: * Znajomość materiału ze *wstępu do informatyki* * Znajomość języka C++

Wykłady

Lista
Prowadzący Termin zajęć Limit Zapisani Kolejka
Artur Kraska
pn 12:00-14:00 (s. 25) 76 53 0

UWAGA! Wyższa liczba oznacza wyższy priorytet, po zapisaniu do grupy zostajemy usunięci z kolejek o niższym priorytecie.

Ćwiczenia

Lista
Prowadzący Termin zajęć Limit Zapisani Kolejka
Artur Kraska
pn 14:00-16:00 (s. 103) 20 20 0
Karol Pokorski
wt 14:00-16:00 (s. 103) 20 13 0
Artur Kraska
śr 14:00-16:00 (s. 104) 20 20 0

UWAGA! Wyższa liczba oznacza wyższy priorytet, po zapisaniu do grupy zostajemy usunięci z kolejek o niższym priorytecie.


Konsultacje prowadzących:


Imię i nazwisko Pokój Konsultacje
Artur Kraska 204 Środa 13-14 (wcześniej należy poinformować mnie mailowo).
Karol Pokorski 311 proszę do mnie napisać e-mail