Kurs C 2013 - propozycje projektów

Poniżej znajdują się propozycje projektów dla mojej grupy laboratoryjnej. Tematy zostały dobrane tak, aby dać studentom jak największe pole do interpretacji i dopracowania własnych wariantów danego problemu. Tematy projektów zostały podzielone na grupy. Projekty z danej grupy dotyczą problemów specyficznych dla określonej dziedziny informatyki, nie wliczając w to tematów zaproponowanych przez samych studentów.

Tematy dobrałem tak, aby studenci wykazali się minimalną chęcią samodzielnego zdobywania wiedzy informatycznej (w większości przypadków trzeba będzie coś dodatkowo przeczytać i (oczywiście) zrozumieć, zanim przystąpi się do implementacji).

Przy wybieraniu tematu i ustalaniu zakresu w jakim chcecie go zrealizować należy kierować się zdrowym rozsądkiem. Nie nakładajcie na siebie pracy, której później nie będziecie w stanie zrealizować. Bądźcie świadomi tego, że dla was priorytetem powinno być zalicznie obowiązków (Logika i Analiza Matematyczna) z jak najlepszym wynikiem. Program, który napiszecie w ramach projektu na kurs C nie musi być duży, aby mieć szanse na otrzymanie maksymalnej liczby punktów. Należy jedynie spełnić kilka warunków techniczno-estetycznych, które są podane na końcu tego dokumentu.

Oto moje propozycje:

Struktury danych:

Drzewo trie

Napisać strukturę danych typu słownik, która jako klucze będzie przechowywać słowa nad skończonym alfabetem (np. angielskim), a jako wartości pewien określony typ danych. Drzewo trie jest to ukorzenione drzewo, które w każdym wierzchołku przechowuje literę. Węzły są ze sobą połączone w taki sposób, aby czytając po koleji litery na dowolnej ścieżce od korzenia do liścia otrzymać słowo należące do naszego słownika. Z każdym liściem (czyli słowem) związana jest wartość określonego z góry typu.

Prostą wersją tego zadania byłoby napisanie w C modułu trie, w którym przyjęlibyśmy typ danych przechowywanych przez słownik, jako liczby naturalne. Taki słownik można by wykorzystać do efektywnego zliczania słów w tekście, co też można przyjąć jako część zadania.

Trudniejsza wersja to wykorzystanie klas i szablonów w C++ do stworzenia ogónej wersji słownika, który podczas tworzenia może przyjąć za wartości dowolny typ danych.

Materiały pomocnicze:

Kopiec binarny

Kopiec binarny jest (prostą!) strukturą danych realizującą tzw. kolejkę priorytetową. Od takiej struktury oczekujemy, że w szybkim czasie możemy zwrócić minimalny (lub maksymalny) element z aktualnie przechowywanego zbioru elementów.

Zadaniem jest napisać moduł w C/C++, w którym znajdować się będzie implementacja kopca binarnego. Jako podstawowy test poprawności należy napisać algorytm sortowania przez kopcowanie i pokazać jego działanie dla przykładowych danych.

Jako jeden z wariantów tego zadania można stworzyć interfejs graficzny, w którym pokazana będzie symulacja działania kopca binarnego dla najważniejszych operacji (usuwanie elementy maksymalnego i dodawanie elementu do kopca).

Jako część zadania można przetestować działanie swojej implementacji dla jakiegoś algorytmu wykorzystującego kolejki priorytetowe (np. algorytm Prima lub algorytm Dijkstry).

Materiały pomocnicze:

Drzewo zbalansowane

Drzewo binarne jest zbalansowane, jeśli czas wykonania operacji wstawiania, usuwania i wyszukiwania klucza w tym drzewie jest proporcjonalne do log n, gdzie n jest liczbą wierzchołków w drzewie. Napisz implementację jednego (lub kilku) drzew zbalansowanych. Do wyboru: drzewo AVL, drzewo czerwono-czarne lub drzewiec.

Implementacje w C/C++ należy przechowywać w osobnych modułach.

Materiały pomocnicze:

Algorytmika:

Otoczka wypukła

Problem otoczki wypukłej jest podstawowym problemem w dziedzinie geometrii obliczeniowej. Mamy dany zbiór punktów na płaszczyźnie i chcemy znaleźć najmniejszy wielokąt wypukły zawierający w sobie wszystkie te punkty.

Zadanie polega na napisaniu dowolnego algorytmu znajdowania otoczki wypukłej i przedstawienie jak on działa krok po kroku korzystając z interfejsu graficznego.

Zamiast intefejsu graficznego można zaimplementować kilka algorytmów i porównać czasy ich działania na przykładowych danych. Wyniki można wtedy przedstawić w konsoli.

Materiały pomocnicze:

Widoczność

Problem widoczności stanowi ważne zagadnienie w planowaniu ruchu robotów (i nie tylko) i posiada wiele ciekawych wariantów. My zajmiemy się tym najprostszymi. Jako dane przyjmujemy wielokąty wypukłe rozmieszczone na płaszczyźnie (można się ograniczyć do kilku wybranych figur np. kwadrat, prostokąt i trójkąt) oraz punkt obserwatora (oko robota). Chcemy się dowiedzieć jakie figury są widoczne z tego punktu (zakładamy że oko robota może obracać się o 360 stopni).

Zadanie można urozmaicać na wiele sposobów, kilka z nich to:

Dla tego zadania mile widziany jest interfejs graficzny.

Materiały pomocnicze:

Najkrótsze ścieżki w grafie

Napisać program z interfejsem graficznym do tworzenia i manipulowania grafami (skierowanymi i/lub nieskierowanymi). Co powinno dać się zrobić:

Pathfinding

Napisz program, który dla dwuwymiarowej mapy rozmiaru n x m znajdzie najkrótszą ścieżkę między pewnymi dwoma wyznaczonymi polami na planszy. Mapa jest złożona z jednakowej wielkości kwadratowych pól. Między polami można poruszać się w poziomie, pionie i na skos. Pole może przyjmować dwa stany: albo jest puste i można po nim chodzić, albo stoi na nim ściana (można dodać inne typy pól: trawa, woda itp. Przejście przez takie pole zajmuje więcej czasu niż przez pole puste). Użyj algorytmu A-star i klasycznego algorytmu Dijkstry. Porównaj je ze sobą w postaci symulacji.

Główną częścią zadania jest przedstawienie symulacji działania obu algorytmów działających równolegle w tym samym czasie. Mile widziany interfejs graficzny (chociaż w samej konsoli pewnie też się da to zrobić).

Materiały pomocnicze:

Analiza numeryczna i algebra:

Całkowanie

Zaimplemenuj kilka popularnych metod obliczania całki oznaczonej. Do wyboru (w kolejności, zaczynając od najprostszej):

Wykonaj testy na kilku wybranych (nietrywialnych) funkcjach i przeprowadź porównanie zaimplementowanych metod.

Materiały pomocnicze:

Rysowanie wykresów funkcji jednej zmiennej

Napisz program z interfejsem graficznym, który będzie rysował wykresy funkcji dla kilku wybranych klas (np. kwadratowe + liniowe; trygonometryczne). Program powinien mieć możliwość wybrania typu funkcji, określenia jego parametrów (np. współczynników przy funkcji kwadratowej) oraz zmiany skalowania osi. Dodatkowo można wprowadzić możliwość zapisania aktualnego wykresu jako obraz w formacie jpg, png lub bmp (wystarczy wybrać jeden z nich).

Macierze

Napisz moduł operujący na macierzach. Zdefiniuj odpowiednią strukturę/klasę i zaimplementuj najważniejsze operacje na macierzach. Pamiętaj o dynamicznej alokacji pamięci.

Wykorzystaj napisany moduł do rozwiązania następującego problemu: dla podanych n równań linowych, przy pomocy znanych metod rozwiąż ten układ. Można użyć algorytm eliminacji Gaussa, dekompozycję LU lub dowolnie inny algorytm.

Materiały pomocnicze:

Przetwarzanie danych i WWW:

Rozkład jazdy MPK

Napisz program, który dla odpowiednich zapytań użytkownika zwróci pewne sformatowane dane ze strony http://www.wroclaw.pl/rozklady-jazdy. Typowe rodzaje zapytań:

Web Crawler

Napisać program, który dla podanego adresu www, ściągnie na dysk wszystkie pliki o danym rozszerzeniu/typie z tej strony i jej podstron. Typowym zastosowaniem może być chęć ściągnięcia wszystkich zdjęć/obrazków ze strony.

Interfejs graficzny mile widziany, szczególnie w przypadku ściągania obrazków.

Organizer

Napisz aplikację zarządzającą notatkami. Notatki powinny być przechowywane w plikach tekstowych i pogrupowane w folderach zgodnie z kategorią. Jako część programu dodaj opcję wyszukiwania notatek po słowach kluczowych/tagach lub po tekście.

Sztuczna inteligencja:

Algorytmy ewolucyjne

Algorytmy ewolucyjne stanowią zbiór metod obliczeniowych bazujących na teorii ewolucji. Są one podstawą teorii optymalizacji metaheurystycznej. Metody te zapożyczają pojęcia z dziedziny biologii takie jak: reprodukcja, mutacja, rekombinacja, selekcja. Algorytmy ewolucyjne służą do znalezenia przybliżonych rozwiązań trudnych problemów obliczeniowych np. TSP. Kandydaci na rozwiązania problemu optymalizacyjnego (w przypadku TSP są to permutacje) są nazywani osobnikami. Osobników łączy się w populacje i wyznacza się ich przystosowanie do środowiska przy pomocy pewnej funkcji przystosowania. Następnie, w zależności od przyjętej strategii aplikujemy operatory ewolucyjne dla danej populacji (np. mutacja, krzyżowanie, selekcja), dopóki nie osiągniemu pewnego kryterium stopu. Początkową populację możemy wylosować lub wyznaczyć przy pomocy różnych algorytmów np. algorytmów zachłannych.

Zaimplementuj prosty algorytm ewolucyjny dla problemu TSP. Znajdź w internecie gotowe dane testowe (takie, które mają podane optima dla sowich instancji) i pokaż jak bliskie od optymalnego rozwiązania zwraca Twój algorytm.

Materiały pomocnicze:

Kółko-krzyżyk 5x5

Napisz grę w kółko-krzyżyk o rozmiarach 5x5. Zasady gry są analogiczne do klasycznej wersji 3x3: wygrywa gracz, który jako pierwszy utworzy linię pionową, poziomą lub ukośną swojego znaku o długości 5.

Gra powinna mieć opcję gry z komputerem. Postaraj się tak zaprogramować ruchy komputera, aby nigdy nie przegrywał.

Propozycje własne:

Jeśli komuś nie podobają się żadne z powyższych tematów i/lub mają w planach coś ciekawszego, to należy się ze mną skontaktować. Po negocjacjach, ustaleniu zakresu pracy i mojej akceptacji można pisać dowolny program (pamiętając o zdrowym rozsądku!).

Szczegóły techniczne:

Uwagi estetyczne:

Pomocne informacje: