19Z Zasady

updated on 08.01.2020

Daty ('do - włącznie' - czyli tego dnia do północy)
25.10.2019 - wybór tematu 1. projektu
27.11.2019 - wybór tematu 2. projektu
02.12.2019 - oddanie 1. projektu
27.01.2020 - oddanie 2. projektu
31.01-09.02.2020 - nie ma mnie w PL

Punkty:
1. projekt: max 15 pkt
2. projekt: max 15 pkt
Każdy tydzień spóźnienia: -5 pkt
Ocenianie:
Prezentacja na żywo
Działanie algorytmu
Dokumentacja
Oddawanie projektów:
Mailowo: .pdf z dokumentacją i kod / link do repozytorium (github etc.) - preferowane repo
Projekt 1. Prezentacja działania: wtorek 03.12.2019 w godz. 12.00 - 16.00 w p. 304/302. Jak ktoś nie może to prośba o maila.
Projekt 2. Prezentacja działania: wtorek 28.01.2020 w godz. 12.00 - 16.00 w p. 304/302. Jak ktoś nie może to prośba o maila.
Konsultacje:
Najlepiej mailowo
W razie konieczności na żywo - po wcześniejszym ustaleniu

W razie problemów, pytań itp. proszę pisać (niekoniecznie na odp. do Multiply)
Jeśli nie odpowiadam 2,3 dni, prośba o ping.

Kod programu:
Napisany w jednym ze standardowych języków: Java, Scala, Python, R, C++, C# - najlepiej żeby dał się uruchomić z konsoli na linuxie
Nie korzystamy z istniejących bibliotek mechanizmów sztucznej inteligencji - algorytmy implementujemy samodzielnie
Można korzystać z bibliotek ML do ładowania danych
W projekcie skupiamy się na algorytmach AI - to jest clue projektu
Zawartość dokumentacji (max 3 strony):
1. Treść zadania
2. Przyjęte założenia, doprecyzowanie treści
3. (2pkt) Podział odpowiedzialności w zespole - kto się czym zajmował
4. (5pkt) Zwięzły opis algorytmu/architektura i uzasadnienie sposobu realizacji
5. (5pkt) Raport z przeprowadzonych eksperymentów, sposób testowania, tabelki, wykresy etc.
Zbieramy wyniki i statystyki wykonania tj. liczymy m.in. czas obliczeń, liczbę kroków/generacji, ew. ale niekoniecznie złożoność pamięciową itp.
6. (3pkt) Wnioski, przemyślenia, ew. możliwe usprawnienia
7. Zwięzła instrukcja dla użytkownika programu
Bez szczegółów implementacyjnych tj. opisu struktury klas, funkcji itd.

Dane wykorzystane do 2. projektu powinny być rozdzielone na część treningową oraz testową, a rezultaty powinny zostać poddane walidacji k-fold, np. k=5 (chyba, że zadanie ma już wydzielone zbiory lub w treści zapisane jest inaczej)
Tematy 2. projektu:
MM.B.K1 SMS spam filter Napisać program, który korzystając z uczenia Bayesowskiego (Naive Bayes) będzie w stanie zaklasyfikować wiadomości SMS jako SPAM lub nie. Zbiór danych do użycia: SMS Spam Collection Dataset - https://www.kaggle.com/uciml/sms-spam-collection-dataset
MM.B.K2 E-mail spam filter Napisać program, który korzystając z uczenia Bayesowskiego (Naive Bayes) będzie w stanie zaklasyfikować wiadomości e-mail jako SPAM lub nie. Zbiór danych do użycia: Enron-Spam in pre-processed form - http://www2.aueb.gr/users/ion/data/enron-spam/
MM.SVM.K1 Support Vector Machine Zaimplementować klasyfikator oparty na modelu maszyny wektorów nośnych (SVM) w wersji liniowej i nieliniowej (kernel: poly/rbf/sigmoid). Porównać wyniki dla strategii one-vs-one i one-vs-all do klasyfikacji zbioru ręcznie pisanych cyfr. Zbiór danych do użycia: MNIST - http://yann.lecun.com/exdb/mnist/. Uzyskane rezultaty porównać z wynikami dla wybranej implementacji algorytmu ML z dostępnych bibliotek np. Scikit-learn, WEKA, MLlib, Tensorflow/Keras etc.
MM.DD.K1 ID3, C4.5 Zaimplementować algorytmy ID3 i C4.5 do budowy drzew decyzyjnych. Porównać działanie otrzymanych klasyfikatorów. Zbiór danych do użycia: Car Evaluation - https://archive.ics.uci.edu/ml/datasets/Car+Evaluation. Uzyskane rezultaty porównać z wynikami dla wybranej implementacji algorytmu ML z dostępnych bibliotek np. Scikit-learn, WEKA, MLlib, Tensorflow/Keras etc.
MM.DD.K2 AdaBoost Zaimplementować algorytm AdaBoost (Adaptive Boosting) do klasyfikacji bazujący na sekwencji drzew decyzyjnych. Zbiór danych do użycia: Heart Disease - https://archive.ics.uci.edu/ml/datasets/Heart+Disease. Uzyskane rezultaty porównać z wynikami dla wybranej implementacji algorytmu ML z dostępnych bibliotek np. Scikit-learn, WEKA, MLlib, Tensorflow/Keras etc.
MM.DD.K3 Gradient Boosting Zaimplementować algorytm Gradient Boosting do klasyfikacji bazujący na sekwencji drzew decyzyjnych. Zbiór danych do użycia: Wine Quality - https://archive.ics.uci.edu/ml/datasets/Wine+Quality. Uzyskane rezultaty porównać z wynikami dla wybranej implementacji algorytmu ML z dostępnych bibliotek np. Scikit-learn, WEKA, MLlib, Tensorflow/Keras etc.
MM.DD.K4 Random Forest Zaimplementować algorytm lasu losowego (ang. Random Forest) do klasyfikacji. Zbiór danych do użycia: MNIST - http://yann.lecun.com/exdb/mnist/. Uzyskane rezultaty porównać z wynikami dla wybranej implementacji algorytmu ML z dostępnych bibliotek np. Scikit-learn, WEKA, MLlib, Tensorflow/Keras etc.
MM.DD.K5 Random Forest - decision stumps Zaimplementować algorytm lasu losowego (ang. Random Forest) do klasyfikacji oparty na modelu lasu losowego pieńków decyzyjnych (ang. decision stumps). Zbiór danych do użycia: Car Evaluation - https://archive.ics.uci.edu/ml/datasets/Car+Evaluation. Uzyskane rezultaty porównać z wynikami dla wybranej implementacji algorytmu ML z dostępnych bibliotek np. Scikit-learn, WEKA, MLlib, Tensorflow/Keras etc.
MM.SVM.R1 Support Vector Machine Zaimplementować regresor oparty na modelu maszyny wektorów nośnych (SVM) w wersji liniowej i nieliniowej (kernel: poly/rbf/sigmoid). Zbiór danych do użycia: Boston Housing - https://www.kaggle.com/c/boston-housing / http://lib.stat.cmu.edu/datasets/boston. Uzyskane rezultaty porównać z wynikami dla wybranej implementacji algorytmu ML z dostępnych bibliotek np. Scikit-learn, WEKA, MLlib, Tensorflow/Keras etc.
MM.SVM.R2 Support Vector Machine Zaimplementować regresor oparty na modelu maszyny wektorów nośnych (SVM) w wersji liniowej i nieliniowej (kernel: poly/rbf/sigmoid). Zbiór danych do użycia: Wine Quality - https://archive.ics.uci.edu/ml/datasets/Wine+Quality. Uzyskane rezultaty porównać z wynikami dla wybranej implementacji algorytmu ML z dostępnych bibliotek np. Scikit-learn, WEKA, MLlib, Tensorflow/Keras etc.
MM.DD.R1 Gradient Boosting Zaimplementować algorytm Gradient Boosting do predykcji bazujący na sekwencji drzew decyzyjnych. Zbiór danych do użycia: Boston Housing - https://www.kaggle.com/c/boston-housing / http://lib.stat.cmu.edu/datasets/boston. Uzyskane rezultaty porównać z wynikami dla wybranej implementacji algorytmu ML z dostępnych bibliotek np. Scikit-learn, WEKA, MLlib, Tensorflow/Keras etc.
MM.DD.R2 AdaBoost Zaimplementować algorytm AdaBoost (Adaptive Boosting) do predykcji bazujący na sekwencji drzew decyzyjnych. Zbiór danych do użycia: Boston Housing - https://www.kaggle.com/c/boston-housing / http://lib.stat.cmu.edu/datasets/boston. Uzyskane rezultaty porównać z wynikami dla wybranej implementacji algorytmu ML z dostępnych bibliotek np. Scikit-learn, WEKA, MLlib, Tensorflow/Keras etc.
MM.DD.R3 Random Forest Zaimplementować algorytm lasu losowego (ang. Random Forest) do predykcji. Zbiór danych do użycia: Forest Fires - https://archive.ics.uci.edu/ml/datasets/Forest+Fires. Uzyskane rezultaty porównać z wynikami dla wybranej implementacji algorytmu ML z dostępnych bibliotek np. Scikit-learn, WEKA, MLlib, Tensorflow/Keras etc.
MM.DD.R4 Random Forest Zaimplementować algorytm lasu losowego (ang. Random Forest) do predykcji. Zbiór danych do użycia: Boston Housing - https://www.kaggle.com/c/boston-housing / http://lib.stat.cmu.edu/datasets/boston. Uzyskane rezultaty porównać z wynikami dla wybranej implementacji algorytmu ML z dostępnych bibliotek np. Scikit-learn, WEKA, MLlib, Tensorflow/Keras etc.
MM.SN.K1 Perceptron wielowarstwowy Zaproponować architekturę, zaimplementować, wytrenować i przeprowadzić walidację sieci neuronowej do klasyfikacji gatunków irysów. Zbiór danych do użycia: Iris - https://archive.ics.uci.edu/ml/datasets/Iris. Porównać wyniki dla różnej liczby urktytych neuronów.
MM.SN.K2 Perceptron wielowarstwowy Zaproponować architekturę, zaimplementować, wytrenować i przeprowadzić walidację sieci neuronowej do klasyfikacji ręcznie pisanych cyfr. Zbiór danych do użycia: MNIST - http://yann.lecun.com/exdb/mnist/. Porównać wyniki dla różnej liczby urktytych neuronów.
MM.SN.K3 Perceptron wielowarstwowy Zaproponować architekturę, zaimplementować, wytrenować i przeprowadzić walidację sieci neuronowej, która dokonuje predykcji choroby serca. Zbiór danych do użycia: Heart Disease - https://archive.ics.uci.edu/ml/datasets/Heart+Disease / https://www.kaggle.com/ronitf/heart-disease-uci. Porównać wyniki dla różnej liczby urktytych neuronów.
MM.SN.R1 Perceptron wielowarstwowy Zaproponować architekturę, zaimplementować, wytrenować i przeprowadzić walidację sieci neuronowej do predykcji spalonych obszarów lasu w wyniku pożaru. Zbiór danych do użycia: Forest Fires - https://archive.ics.uci.edu/ml/datasets/Forest+Fires. Porównać wyniki dla różnej liczby urktytych neuronów.
MM.SN.R2 Perceptron wielowarstwowy Zaproponować architekturę, zaimplementować, wytrenować i przeprowadzić walidację sieci neuronowej do predykcji ceny domu. Zbiór danych do użycia: Boston Housing - https://www.kaggle.com/c/boston-housing / http://lib.stat.cmu.edu/datasets/boston. Porównać wyniki dla różnej liczby urktytych neuronów.

W razie wątpliwości możliwe jest doprecyzowanie i/lub modyfikacja treści/zakresu zadania, ale w taki sposób aby zadany problem nie został sprowadzony do trywialnej postaci
Tematy 1. projektu:
MM.P1 Problem komiwojażera - alg. przeszukiwania Zaimplementować i przetestować algorytm A* dla problemu komiwojażera. Porównać działanie algorytmu A* z algorytmem zachłannym i przeszukiwaniem brute force (dla bf przerwać obliczenia w pewnym momencie). WE: plik ze współrzędnymi punktów. WY: najkrótszy cykl łączący punkty.
MM.P2 Najkrótsza ścieżka w grafie ważonym Zaimplementować i przetestować algorytm A* dla zadania znalezienia ścieżki o najmniejszej wadze od punktu A do B. Porównać działanie algorytmu A* z algorytmem zachłannym i przeszukiwaniem brute force (dla bf przerwać obliczenia w pewnym momencie). WE: plik z listą krawędzi grafu (punkt początkowy, końcowy i waga), punkt startowy A i docelowy B. WY: najkrótsza ścieżka od punktu A do punktu B i jej koszt.
MM.AP3 N-puzzle Napisać program rozwiązujący N-puzzle (N = n^2 – 1, gdzie n = {2, 3, ...} jest parametrem, eg. https://en.wikipedia.org/wiki/15_puzzle). Do przeszukiwania przestrzeni stanów należy wykorzystać algorytm BFS oraz algorytm A* lub IDA*. WE: liczba N do wygenerowania planszy lub plik z układem. WY: wynikowa sekwencja ruchów lub informacja że nie da się ułożyć.
MM.P4 Labirynt Napisać program porównujący działanie algorytmów przeszukiwania BFS, DFS, IDFS dla problemu znalezienia drogi w labiryncie. Przestrzeń dyskretna - dozwolone ruchy to góra, dół, lewo, prawo. WE: plik ze strukturą labiryntu z we/wy (dla większych użyć jakiegoś generatora). WY: znaleziona najkrótsza ścieżka i/lub mapka z zaznaczoną ścieżką.
MM.P5 Najkrótsza droga bez kolizji Na płaszczyźnie umieszczono skończony zbiór przeszkód stanowiących przeszkody na drodze. Należy znaleźć najkrótszą możliwą ścieżkę bez kolizji między dwoma punktami. Do znalezienia ścieżki wykorzystać algorytm A* dla dwóch różnych heurystyk. Przestrzeń dyskretna - dozwolone ruchy to góra, dół, lewo, prawo i na skosy. WE: plik z mapą i przeszkodami, punkty we/wy. WY: znaleziona najkrótsza ścieżka i/lub mapka z zaznaczoną ścieżką.
MM.P6 Najkrótsza ścieżka w grafie ważonym - ACO Zaimplementować algorytm mrówkowy - ACO (Ant Colony Optimization) do wyznaczania najkrótszej ścieżki w grafie ważonym od punktu A do B. Porównać działanie algorytmu z przeszukiwaniem brute force. WE: plik z listą krawędzi grafu (punkt początkowy, końcowy i waga), punkt startowy i docelowy. WY: najkrótsza ścieżka od punktu A do punktu B i jej koszt.
MM.AE1 Pokrycie tryskaczami Napisać program dokonujący optymalnego rozkładu tryskaczy na danym obszarze zamkniętym w przestrzeni dyskretnej. Tryskacz zapewnia pokrycie obszaru ‘kołowego’ o średnicy D i jego zasięg może być ograniczony przez ściany. Tryskacze mogą być umieszczane tylko w punktach wewnętrznych obszaru. Przedmiotem minimalizacji jest liczba tryskaczy. WE: plik z mapą/definicją obszaru, średnica D, minimalne pokrycie w % do zakończenia działania algorytmu. WY: położenie tryskaczy oraz uzyskany % pokrycia.
MM.AE2 Problem komiwojażera - alg. ewolucyjne Rozwiązanie powinno opierać się na wybranym algorytmie ewolucyjnym z pewnym modelem osobników oraz odpowiednio zaimplementowanymi operacjami krzyżowania i mutacji. Sensownie przedstawić postęp w działaniu algorytmu (np. Wypisując kluczowe informacje diagnostyczne). WE: plik z definicją mapy/grafu, WY: najkrótszy cykl łączący punkty.
MM.AE3 Szeregowanie zadań Zaimplementować algorytm ewolucyjny planujący wykonanie N zadań na M procesorach w taki sposób aby suma opóźnień w wykonaniu była jak najmniejsza. Na jedno zadanie składa się: czas trwania T i deadline wykonania - wartość D. Obliczenia przerwać po pewnej liczbie generacji bez poprawy wyniku. WE: plik z listą zadań, liczba M procesorów. WY: harmonogram zadań i suma opóźnień.
MM.AE4 Tangram Zaimplementować algorytm ewolucyjny układający planszę zadanego kształtu dla układanki Tangram (eg. https://en.wikipedia.org/wiki/Tangram). Dla uproszczenia przyjąć, że elementy składowe zadanego kształtu nie podlegają obracaniu. WE: plik z konfiguracją docelowego kształtu, pożądany stopień adaptacji w %. WY: finalny rezultat z danymi o generacji/osobniku.
MM.AG1 Problem plecakowy Do plecaka o pojemności C chcemy zapakować przedmioty o jak największej wartości. Każdy przedmiot definiowany jest przez wartość W i objętość O jaką zajmuje w plecaku. Zastosować algorytm genetyczny i zamodelować pewien sposób reprezentacji genotypu do rozwiązania tego problemu. WE: plik z listą przedmiotów opisanych wartością W i objętością O, pojemność plecaka C. WY: przedmioty mieszczące się w plecaku, które maksymalizują jego wartość.
MM.AG2 Magiczny kwadrat Zadanie polega na wygenerowaniu kwadratu NxN, w którym elementami są liczby (1, 2, ..., n^2) ułożone tak, aby w każdym wierszu, kolumnie i przekątnej suma wartości liczb była taka sama i wynosiła n*(n^2 + 1)/2. WE: liczba N, maksymalna liczba iteracji. WY: wygenerowany kwadrat.
MM.AG3 Podział kart na 2 stosy Masz N kart z wartościami od 1 do N. Przy pomocy algorytmu genetycznego należy podzielić je na dwa stosy, gdzie suma wartości kart na pierwszym stosie ma wartość jak najbliższą do A, a iloczyn wartości kart na drugim stosie jak najbliższa wartości B. WE: liczba kart N, suma kart A, iloczyn kart B, satysfakcjonujący poziom dopasowania w %. WY: podział kart na stosy z wynikami działań.
MM.AG4 Kolorowanie mapy Zastosować algorytm genetyczny do kolorowania mapy N kolorami w taki sposób aby żadne dwa sąsiednie wierzchołki grafu nie miały tego samego koloru. WE: plik z grafem, liczba N kolorów, % dopasowania lub maksymalna liczba iteracji. WY: pokolorowany graf lub jakaś jego czytelna reprezentacja.
MM.GD1 Gra w Czwórki Wykorzystując algorytm min-max i odcinanie alfa-beta zaprojektować i zaimplementować algorytm umożliwiający rozegranie gry w Czwórki (eg. https://en.wikipedia.org/wiki/Connect_Four). Działanie algorytmu należy zaprezentować w formie prostej interaktywnej aplikacji graficznej/konsolowej umożliwiającej rozegranie gry zgodnie z jej regułami przeciwko komputerowi. WE: kto rozpoczyna grę, rozmiar planszy NxM (n, m >= 4), maksymalna głębokość przeszukiwania przestrzeni stanów. WY: prosty interfejs gry.
MM.GD2 Gra w Warcaby Wykorzystując algorytm min-max i odcinanie alfa-beta zaprojektować i zaimplementować algorytm umożliwiający rozegranie gry w Warcaby. Działanie algorytmu należy zaprezentować w formie prostej interaktywnej aplikacji graficznej/konsolowej umożliwiającej rozegranie gry zgodnie z jej regułami przeciwko komputerowi. WE: kto rozpoczyna grę, maksymalna głębokość przeszukiwania przestrzeni stanów. WY: prosty interfejs gry.
MM.GD3 Gra w Kółko i Krzyżyk Wykorzystując algorytm min-max i odcinanie alfa-beta zaprojektować i zaimplementować algorytm umożliwiający rozegranie gry w Kółko i Krzyżyk. Działanie algorytmu należy zaprezentować w formie prostej interaktywnej aplikacji graficznej/konsolowej umożliwiającej rozegranie gry zgodnie z jej regułami przeciwko komputerowi. WE: kto rozpoczyna grę, rozmiar planszy N (n >= 3), maksymalna głębokość przeszukiwania przestrzeni stanów. WY: prosty interfejs gry.
MM.GD4 Gra w Reversi Wykorzystując algorytm min-max i odcinanie alfa-beta zaprojektować i zaimplementować algorytm umożliwiający rozegranie gry w Reversi (eg. https://en.wikipedia.org/wiki/Reversi). Działanie algorytmu należy zaprezentować w formie prostej interaktywnej aplikacji graficznej/konsolowej umożliwiającej rozegranie gry zgodnie z jej regułami przeciwko komputerowi. WE: kto rozpoczyna grę, maksymalna głębokość przeszukiwania przestrzeni stanów. WY: prosty interfejs gry.
MM.GD5 Gra w Izolację Wykorzystując algorytm min-max i odcinanie alfa-beta zaprojektować i zaimplementować algorytm umożliwiający rozegranie gry w Izolację (eg. https://www.cs.umb.edu/~yunxu/isola/rules.html). Działanie algorytmu należy zaprezentować w formie prostej interaktywnej aplikacji graficznej/konsolowej umożliwiającej rozegranie gry zgodnie z jej regułami przeciwko komputerowi. WE: kto rozpoczyna grę, maksymalna głębokość przeszukiwania przestrzeni stanów. WY: prosty interfejs gry.

Generalnie chciałbym też, żeby w ramach projektu nauczyć się/zrobić sensowny, w miarę nowoczesny technologicznie projekt, którego kod jest czytelny, da się go łatwo 'sklonować', zbudować i uruchomić, ale to są tylko dodatki, które nie są do końca oceniane.

Aby wychodząc z elki, nie produkować kodu jaki niestety można gdzieniegdzie zobaczyć :)