Wierk - Wydział Informatyki, Elektroniczne Ramy Kwalifikacji

Wydział Informatyki
Kierunek studiów	Informatyka							Poziom i forma studiów	pierwszego stopnia inżynierskie stacjonarne
Specjalność / Ścieżka dyplomowania	---							Profil kształcenia	ogólnoakademicki
Nazwa przedmiotu	Algorytmy i struktury danych							Kod przedmiotu	INF1ASD
								Rodzaj przedmiotu	obowiązkowy
Forma zajęć i liczba godzin	W	Ć	L	P	Ps	T	S	Semestr	3
	30	30			30			Punkty ECTS	6
Przedmioty wprowadzające	Analiza matematyczna (INF1AMA), Matematyka dyskretna (INF1MDY), Podstawy programowania (INF1PPR), Programowanie obiektowe (INF1POB),
Cele przedmiotu	Celem przedmiotu jest wykształcenie umiejętności oceny efektywności algorytmu oraz projektowania efektywnych rozwiązań jeszcze przed fazą implementacji algorytmu. Student zostanie wyposażony w wiedzę na temat: metod wyznaczania/szacowania kosztów obliczeniowych rozwiązań algorytmicznych, metod projektowania efektywnych rozwiązań algorytmicznych, metod projektowania efektywnych struktur danych, problemów trudnych obliczeniowo. Student wykształci umiejętności: projektowania efektywnych obliczeniowo algorytmów i struktur danych, oceny efektywności zastosowanych rozwiązań, identyfikacji problemów trudnych obliczeniowo i stosowania rozwiązań przybliżonych dla tych problemów. Celem przedmiotu jest również wykształcenie umiejętności skutecznego komunikowania się w zakresie problemów inżynierskich i naukowych z przedstawicielami innych dziedzin. Odniesienia do standardu SFIA: Programming/software development PROG - poziom 3 Software design SWDN - poziom 2 Scientific modelling SCMO - poziom 4
Treści programowe	Wykład: 1. Podstawowe pojęcia (poprawność algorytmu. złożoność obliczeniowa algorytmu, rzędy wielkości funkcji) 2. Rekurencja jako technika kodowania algorytmów 3. Techniki projektowania algorytmów: "dziel i zwyciężaj", zachłanna, programowania dynamiczne 4. Implementacja kolejki priorytetowe (w postaci kopca) 5. Implementacje struktury słownika (drzewa i tablice haszujące) 6. Algorytmy grafowe i struktury danych reprezentujące grafy 7. Klasy złożoności obliczeniowej (P, NP, NPC, NP-hard), przykłady problemów trudnych obliczeniowo 8. Algorytmy z powrotami 9. Algorytmy przybliżone i heurystyczne 10. Inne zagadnienia (algorytmy przetwarzania tekstu, geometria obliczeniowa, projektowanie uniwersalne) Ćwiczenia: 1. Obliczanie złożoności czasowej programów iteracyjnych, określanie rzędu złożoności, znajdywanie efektywnych rozwiązań podstawowych problemów obliczeniowych 2. Ćwiczenia dotyczącej algorytmów rekurencyjnych i "dziel i zwyciężaj": projektowanie algorytmów i obliczanie złożoności 3. Rozwiązywanie problemów obliczeniowych z zastosowaniem techniki zachłannej i programowania dynamicznego 4. Ćwiczenia dotyczące działania wydajnych struktur danych (kopców, drzew i tablic haszujących) 5. Rozwiązywanie problemów grafowych 6. Ćwiczenie związane z techniką powrotów 7. Ćwiczenie umiejętności rozpoznawania problemów trudnych obliczeniowo i stosowania w ich przypadku rozwiązań przybliżonych/heurystycznych Pracownia specjalistyczna: 1. Podstawowe problemy obliczeniowe, optymalizacja algorytmów (porównanie, projektowanie, implementacja) pod względem złożoności czasowej 2. Rozwiązanie problemów obliczeniowych z zakresu rekurencji / "dziel i zwyciężaj" 3. Projektowanie i implementacja wydajnych algorytmów (technika programowania dynamicznego i zachłanna) do rozwiązywania problemów optymalizacji kombinatorycznej 4. Implementacja drzewiastej struktury słownika 5. Rozwiązywanie problemów grafowych
Metody dydaktyczne	metoda projektów, ćwiczenia przedmiotowe, programowanie z użyciem komputera, metoda przypadków, wykład problemowy, wykład informacyjny,
Forma zaliczenia	Wykład: egzamin pisemny Ćwiczenia - dwa sprawdziany Pracownia specjalistyczna: ocena cząstkowych zadań problemowych
Symbol efektu uczenia się	Zakładane efekty uczenia się								Odniesienie do kierunkowych efektów uczenia się
EU1	fundamentalne pojęcia i notacje stosowane w analizie algorytmów i struktur danych oraz w opisywaniu problemów obliczeniowych, decyzyjnych itp., które można rozwiązać za pomocą komputera								INF1_W01 INF1_W05
EU2	standardowe rozwiązania projektowe i implementacyjne algorytmów oraz struktur danych, ich właściwości oraz obszary zastosowań; zna podstawy projektowania uniwersalnego								H1_W01 INF1_W05
EU3	oceniać złożoność czasową i pamięciową algorytmów oraz struktur danych; potrafi porównać różne rozwiązania tego samego problemu								INF1_U04
EU4	zaproponować i zaprojektować lub dobrać algorytmy i struktury danych do efektywnego rozwiązania zadanego inżynierskiego lub naukowego; potrafi oszacować złożoność problemu i zidentyfikować problemy trudne oraz takie, dla których zadowalające jest rozwiązanie przybliżone/heurystyczne								INF1_U04
EU5	zweryfikować poprawność algorytmu podstawowymi metodami formalnymi i symulacyjnymi								INF1_U06
EU6	implementować algorytmy i struktury danych w językach wysokiego poziomu								INF1_U04
EU7	uwzględniania polityki zrównoważonego rozwoju podczas doboru wydajnych algorytmów								H1_K03
Symbol efektu uczenia się	Sposób weryfikacji efektu uczenia się								Forma zajęć na której zachodzi weryfikacja
EU1	egzamin pisemny								W
EU2	egzamin pisemny								W
EU3	sprawdzian								Ć
EU4	sprawdzian								Ć
EU5	ocena cząstkowych zadań problemowych								Ps
EU6	ocena cząstkowych zadań problemowych								Ps
EU7	ocena cząstkowych zadań problemowych								Ps
Bilans nakładu pracy studenta (w godzinach)									Liczba godz.
Wyliczenie
	1 - Udział w wykładach								30
	2 - Udział w ćwiczeniach audytoryjnych i pracowni specjalistycznej								60
	3 - Przygotowanie do ćwiczeń audytoryjnych i pracowni specjalistycznej								10
	4 - Realizacja zadań problemowych z pracowni specjalistycznej								20
	5 - Przygotowanie do zaliczenia ćwiczeń								14
	6 - Udział w konsultacjach								4
	7 - Przygotowanie do egzaminu								10
	8 - Obecność na egzaminie								2
RAZEM:									150
Wskaźniki ilościowe									GODZINY	ECTS
Nakład pracy studenta związany z zajęciami wymagającymi bezpośredniego udziału nauczyciela									96 (6)+(2)+(8)+(1)	3.8
Nakład pracy studenta związany z zajęciami o charakterze praktycznym									104 (4)+(2)+(5)+(3)	4.2
Literatura podstawowa	1. T.H. Cormen, C.E. Leiserson, R.L. Rivest, S. Clifford, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2022 2. R. Neapolitan, K. Namipour, Podstawy algorytmów z przykładami w C++, Helion, Warszawa, 2006 3. A.V. Aho, J.E. Hopcroft, J.D. Ullman, Projektowanie i analiza algorytmów komputerowych, PWN, Warszawa, 2007
Literatura uzupełniająca	1. L. Banachowski, W. Rytter, K.M. Diks, Algorytmy i struktury danych, Wydawnictwo Naukowe PWN, Warszawa, 2018 2. A. Drozdek, D. L. Simon, Struktury danych w języku C, WNT, Warszawa, 2003 3. N. Wirth, Algorytmy + struktury danych = programy, WNT, Warszawa, 2004
Jednostka realizująca	Katedra Informatyki Teoretycznej								Data opracowania programu
Program opracował(a)	dr inż. Anna Borowska,dr Joanna Karbowska-Chilińska								2023.04.04