Streszczenie:
Problem wyszukiwania wzorca w tekście - algorytm naiwny, Rabina-Karpa i Knutha-Morrisa-Pratta. Amortyzowana złożoność obliczeniowa (na przykładzie KMP). Podstawy hashowania (na potrzeby Rabina-Karpa). Idea drzewa Trie jako prostej struktury słownikowej.
Zadania:
http://pl.spoj.pl/problems/KMP/
Materiały:
Streszczenie:
Omówiona została struktura kopca binarnego wraz z implementacją oraz idea binarnego drzewa poszukiwań (BST). Oprócz tego algorytm Dijkstry (z implementacją), Forda-Bellmana (impelementacja ideowo, kilka heurestyk) i sortowanie topologiczne algorytmem Kahna.
Zadania:
https://pl.spoj.pl/problems/DIJKSTRA/
Materiały:
http://pl.wikipedia.org/wiki/Kopiec_binarny
http://pl.wikipedia.org/wiki/Binarne_drzewo_poszukiwa%C5%84
http://www.rafalnowak.pl/wiki/index.php?title=Algorytm_Dijkstry
http://pl.wikipedia.org/wiki/Algorytm_Bellmana-Forda
http://pl.wikipedia.org/wiki/Sortowanie_topologiczne
Streszczenie:
Wstęp do programowania dynamicznego. Różnica między metodą zachłanną, a dynamiczną na przykładzie problemu plecakowego i ciągłego problemu plecakowego. Idea dynamika na drzewie (bottom-up) na przykładzie pokazanego już algorytmu min-max. Najdłuższy wspólny podciąg, pokazanie tricku z liniową pamięcią. Algorytm obliczania odległości edycyjnej.
Zadania:
Materiały:
Wprowadzenie do zachłanności i dynamiki.
Najdłuższy wspólny podciąg.
Odległość edycyjna (w en - ładniej opisana).
Algorytm Pearsona - inny algorytm rozwiązujący problem wydawania reszty.
Streszczenie:
Omówienie w ramach utrwalenia materiału rozwiązań i implementacji do kilku prostych zadań: Kalendarze i Palindroliczby z III OIG oraz Tulipany i Wieże z PA 2011. Przedstawienie set'a z stl
Zadania:
http://main.edu.pl/pl/archive/oig/3/kal
http://main.edu.pl/pl/archive/oig/3/pal
http://main.edu.pl/pl/archive/pa/2011/wie
http://main.edu.pl/pl/archive/pa/2011/tul
Materiały:
Streszczenie:
Pierwsza część spotkania dotyczyła sieci neuronowych: perceptronu, Kohonena, Hopfielda i RBF - ich możliwości, zastosowań i podstaw algorytmów nauki. Podczas części algorytmicznej spotkania omówiono rozwiązania zadań z zestawu 1.