Pojęcia podstawowe
- algorytm, pseudokod
- problem sortowania, poprawność algorytmu sortowania
- algorytm sortowania przez wstawianie
- niezmienniki pętli
- efektywność algorytmów
- model RAM
- obliczanie czasu wykonania algorytmu
- znaczenie przypadków: najgorszego, średniego, i najlepszego
- rząd wzrostu funkcji
- efektywność asymptotyczna i notacja asymptotyczna
Algorytmy sortowania
- zagadnienia sortowania: sortowanie w miejscu, sortowanie stabilne,
podejście inkrementacyjne, podejście dziel-i-rządź
- algorytm sortowania przez scalanie (mergesort)
- kopce: reprezentacja i budowa
- algorytm sortowania przez kopcowanie (heapsort)
- algorytm sortowania szybkiego (quicksort), wybór elementu rozdzielającego
Sortowanie w czasie liniowym
- sortowanie przez porównywanie: czas działania
- algorytm sortowania przez zliczanie
- algorytm sortowania pozycyjnego
- algorytm sortowania kubełkowego
Podstawowe struktury danych
- stosy: implementacja tablicowa, implementacja wskaźnikowa
- kolejki: model bufora kołowego, implementacja tablicowa
- listy: implementacja wskaźnikowa, listy z wartownikiem
- drzewa binarne i niebinarne: reprezentacja wskaźnikowa
Tablice z haszowaniem
- tablice bezpośrednio adresowane
- funkcje haszujące, kolizje
- rozwiązywanie kolizji metodą łańcuchową
- haszowanie niezależne jednostajnie
- metody haszowania: dzielenie, mnożenie, mnożenie z przesunięciem
- kryptograficzne funkcje skrótu, zastosowanie soli
- adresowanie otwarte: próbkowanie liniowe, haszowanie podwójne
Binarne drzewa przeszukiwań BST
- zagadnienie zrównoważenia drzewa BST
- przegląd drzew: porządek preorder, inorder, postorder
- przeszukiwanie drzewa BST
- inne operacje: znajdowanie elementu minimalnego, maksymalnego, poprzednika, i następnika
- budowa drzew BST: dodawanie i usuwanie elementu
- warunek niepowtarzalności kluczy
Drzewa zrównoważone AVL
- drzewa binarne w pełni zrównoważone, drzewa częściowo zrównoważone AVL
- przywracanie równowagi częściowej po dodaniu węzła: pojedyncza i podwójna rotacja
Programowanie dynamiczne
- obliczanie liczb Fbonacciego: rekurencyjne, iteracyjne, rekurencyjne ze spamiętywaniem
- zagadnienie rozkroju pręta: optymalna podstruktura problemu, podejście wstępujące i zstępujące
- budowa optymalnych drzew przeszukiwań: rozkłady prawdopodobieństw wyszukiwania kluczy i niekluczy, wartość oczekiwana czasu wyszukiwania
Grafy
- terminologia: węzły/wierzchołki, łuki/krawędzie, pętle, grafy skierowane i nieskierowane, stopień wierzchołka, ścieżki i cykle w grafach, grafy acykliczne, grafy spójne/silnie spójne, składowe spójne/silnie spójne, grafy z wagami, przeszukiwanie grafów
- reprezentacje grafów: listy sąsiedztwa i tablice sąsiedztwa
- przeszukiwanie grafu wszerz BFS, własności
- przeszukiwanie grafu wgłąb DFS, własności
Minimalne drzewa rozpinające
- problem minimalnego drzewa rozpinającego
- algorytm Kruskala
- algorytm Prima
Znajdowanie najkrótszych ścieżek w grafach
- problem najkrótszych ścieżek z wybranego węzła w grafach
- problem połączeń z ujemnymi wagami
- reprezentacja grafu poprzedników
- podstawowe własności i algorytmy: relaksacja krawędzi, nierówność trójkąta
- algorytm Bellmana-Forda
- algorytm Dijkstry
Wprowadzenie do sztucznej inteligencji
- pojęcie inteligencji, własności inteligencji naturalnej, uczenie maszynowe
- reprezentacja w przestrzeni stanów, przeszukiwanie
- heurystyki i funkcje oceny stanu
- metody gradientowe, algorytm wyżarzania
- przeszukiwanie grafów: wszerz, wgłąb, ograniczenie głębokości z iteracyjnym pogłębianiem
- zastosowanie heurystyk, algorytm najpierw-najlepszy
- algorytm A
*: własności, heurystyki dopuszczalne, warianty A* z ograniczonymi wymaganiami pamięciowymi
- metody konstrukcji heurystyk: metoda problemu uproszczonego, wykorzystanie bazy danych wzorców, modelowanie statystyczne
Przeszukiwanie dla gier
- algorytm minimaks
- zastosowanie heurystyki w procedurze minimaks
- odcięcia alfa-beta w algorytmie minimaks - własności
- uogólnienia algorytmu minimaks: gry wieloosobowe, gry z elementami losowymi, gry z niepełną informacją
Przeszukiwanie z więzami
- zagadnienie przeszukiwania z więzami CSP
- więzy binarne i więzy globalne
- graf więzów, spójność łukowa, analiza spójności łukowej, przywracanie spójności łukowej, propagacja więzów
- przeszukiwanie z nawracaniem dla zagadnień CSP
- połączenie przeszukiwania z analizą spójności łukowej
Wprowadzenie do sztucznych sieci neuronowych
- model perceptronu, wagi i bias, sigmoidalna funkcja aktywacji, inne funkcje aktywacji
- perceptron wielowarstwowy MLP, warstwa wejściowa, warstwy ukryte, warstwa wyjściowa, połączenia między warstwami, architektura sieci jednokierunkowej
- algorytm wstecznej propagacji błędów, poszukiwanie rozwiązania metodą gradientu prostego i stochastycznego
- funkcja kosztu w uczeniu: funkcja średniokwadratowa, funkcja entropii krzyżowej
- funkcja aktywacji softmax
- przeuczenie sieci neuronowych, wykrywanie przeuczenia za pomocą walidacji, metody regularyzacji: L1, L2, dropout
- metodologia budowy sieci jednokierunkowych: inicjalizacja wag, dobór (hiper)parametrów
Modele głębokie
- uczenie sieci głębokich, problem znikającego/eksplodującego gradientu
- zastosowanie konwolucji: przetwarzanie za pomocą konwolucji, współdzielenie wag, mapy cech
- budowa sieci konwolucyjnych: warstwy konwolucji, agregacja obszarów
Rekurencyjne sieci neuronowe
- warstwowe rekurencyjne sieci neuronowe RNN
- długoterminowa pamięć krótkotrwała LSTM: bramki wejściowa, wyjściowa, zapominania
Reprezentacja probabilistyczna
- niepełna i niepewna wiedza o świecie
- prawdopodobieństwo bezwarunkowe: aksjomaty, reprezentacja graficzna
- zmienne losowe, zdarzenia atomowe, łączny rozkład prawdopodobieństwa JPD, obliczanie prawdopodobieństw zdarzeń, prawdopodobieństwa marginesowe
- prawdopodobieństwo warunkowe, reguła Bayesa
- wnioskowanie przyczynowo-skutkowe, wnioskowanie diagnostyczne
- budowa sieci przekonań, reprezentacja prawdopodobieństw CPT
Podejmowanie prostych decyzji
- preferencje agenta, reprezentacja za pomocą funkcji użyteczności, zasada MEU
- sieci decyzyjne, obliczanie decyzji agenta zgodnej z zasadą MEU
- użyteczności wieloatrybutowe
- wartość informacji VPI