Algorytmy i struktury danych

Informacje ogólne

Kod przedmiotu:

EF0-DI>AISD

Kod Erasmus / ISCED:

(brak danych) / (brak danych)

Nazwa przedmiotu:

Algorytmy i struktury danych

Jednostka:

Katedra Informatyki i Automatyki

Grupy:

Przedmioty 2 sem. - informatyka st. I-go stopnia

Punkty ECTS i inne:

5.00 Podstawowe informacje o zasadach przyporządkowania punktów ECTS:

roczny wymiar godzinowy nakładu pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się dla danego etapu studiów wynosi 1500-1800 h, co odpowiada 60 ECTS;
tygodniowy wymiar godzinowy nakładu pracy studenta wynosi 45 h;
1 punkt ECTS odpowiada 25-30 godzinom pracy studenta potrzebnej do osiągnięcia zakładanych efektów uczenia się;
tygodniowy nakład pracy studenta konieczny do osiągnięcia zakładanych efektów uczenia się pozwala uzyskać 1,5 ECTS;
nakład pracy potrzebny do zaliczenia przedmiotu, któremu przypisano 3 ECTS, stanowi 10% semestralnego obciążenia studenta.

Język prowadzenia:

polski

Pełny opis:

Wykład omawia klasyczne struktury danych takie jak: listy, stosy, kolejki, drzewa i grafy oraz podstawowe algorytmy na tych strukturach z uwzględnieniem złożoności. Zajęcia praktyczne koncentrują się na rozwiązywaniu zadań praktycznych oraz przygotowaniu programów w wybranym języku.

Treści kształcenia

- Złożoność obliczeniowa programów. Pojęcia złożoności czasowej i złożoności obliczeniowej oraz szacowanie złożoności. Notacje asymptotyczne i ich interpretacja matematyczna.

- Model obliczeniowy RAM i komendy maszyny RAM. Zapis algorytmów w pseudokodzie.

- Reprezentacja pamięciowa oraz podstawowe algorytmy na wybranych strukturach dynamicznych (listy stosy, kolejki i grafy).

- Struktury drzewiaste i ich właściwości. Drzewa binarne. Rekursja.

- Drzewa poszukiwań binarnych (BST) i ich właściwości. Operacje na drzewach BST.

- Definicja, podstawowe cechy oraz algorytmy na kopcach (heap). Kolejki priorytetowe.

- Poszukiwanie w drzewach (strategie "wszerz", "wgłąb" i "najpierw najlepszy"). Generowanie dróg rozwiązań.

- Sortowanie - podstawowe definicje oraz sformułowanie problemu. Prezentacja oraz ocena złożoności wybranych algorytmów sortowania. Dowód poprawności wybranego algorytmu sortowania.

- Zaawansowane strategie budowy algorytmów - programowanie dynamiczne i algorytmy zachłanne.

- Praktyczne wykorzystanie notacji asymptotycznych. Analiza przykładowych programów w języku maszyny RAM. Ocena czasowej i pamięciowej złożoności obliczeniowej.

- Zapis w pseudokodzie algorytmów operujacych na listach, stosach i kolejkach. Rozwiązywanie problemów z wykorzystaniem rekursji.

- Rozwiązywanie problemów z wykorzystaniem struktur opartych na drzewach binarnych (drzewa BST, kopce)

- Rozwiązywanie problemów metodą przeszukiwania w drzewach.

- Konstruowanie oraz praktyczna weryfikacja wybranych algorytmów sortowania.

- Opracowanie i uruchomienie programów weryfikujących skuteczność wybranych algorytmów.

Literatura:

Literatura wykorzystywana podczas zajęć wykładowych

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein - Wprowadzenie do algorytmów - Wydawnictwo Naukowe PWN, 2012 (można wykorzystać także wcześniejsze wydania). -

A.V. Aho,J.E. Hopcroft, J.D. Ullman - Projektowanie i analiza algorytmów - Wydawnictwo Helion. - 2003.

K. Świder - Wykłady z algorytmów i struktur danych z zadaniami - Oficyna Wydawnicza PRz, 2004 (wersja elektroniczna http://prz-rzeszow.pl/~kswider/asd/).. -

Literatura wykorzystywana podczas zajęć ćwiczeniowych/laboratoryjnych/innych

K. Świder - Wykłady z algorytmów i struktur danych z zadaniami - Oficyna Wydawnicza PRz, 2004 (wersja elektroniczna http://prz-rzeszow.pl/~kswider/asd/).. -

Literatura uzupełniająca

A.V. Aho,J.E. Hopcroft, J.D. Ullman - Algorytmy i struktury danych - Wydawnictwo Helion. - 2003.

R. Lafore - Java. Algorytmy i struktury danych - Wydawnictwo Helion. - 2004

Publikacje naukowe

B. Jędrzejec; K. Świder - Automatically conducted learning from textually expressed vacationers’ opinions - . - 2018

Efekty uczenia się:

Student, który zaliczył moduł	Formy zajęć/metody dydaktyczne prowadzące do osiągnięcia danego efektu kształcenia	Sposoby weryfikacji każdego z wymienionych efektów kształcenia
Ma podstawową wiedzę z zakresu wybranych technik projektowania algorytmów oraz rozumie, jak można poprawić ich efektywność i przejrzystość	wykład, ćwiczenia problemowe, laboratorium	kolokwium, egzamin cz. pisemna, egzamin cz. ustna
Ma podstawową wiedzę na temat złożoności i wydajności algorytmów oraz rozumie znaczenie ich poprawności	wykład, ćwiczenia problemowe, laboratorium	kolokwium, egzamin cz. pisemna, egzamin cz. ustna
Ma podstawową wiedzę z zakresu elementarnych struktur danych (np. listy kolejki i stosy) oraz potrafi wykonywać podstawowe operacje na tych strukturach.	wykład, ćwiczenia problemowe, laboratorium	kolokwium, egzamin cz. pisemna, egzamin cz. ustna
Ma podstawową wiedzę na temat sposobów reprezentowania oraz zastosowań drzew i grafów	wykład, ćwiczenia problemowe, laboratorium	kolokwium, egzamin cz. pisemna, egzamin cz. ustna
Ma podstawową wiedzę na temat powszechnie stosowanych algorytmów sortowania, potrafi wyjaśnić ich działanie oraz ocenić złożoność wybranych algorytmów.	wykład, ćwiczenia problemowe, laboratorium	kolokwium, egzamin cz. pisemna, egzamin cz. ustna

Metody i kryteria oceniania:

na ocenę 3	na ocenę 4	na ocenę 5
Ma podstawową wiedzę z zakresu wybranych technik projektowania algorytmów oraz rozumie, jak można poprawić ich efektywność i przejrzystość	nie tylko osiągnął poziom wiedzy i umiejętności wymagany na ocenę 3, ale również potrafi pisać poprawne programy przede wszystkim dzięki lepszemu ich rozumieniu, a nie tylko poprawianiu metodą prób i błędów	nie tylko osiągnął poziom wiedzy i umiejętności wymagany na ocenę 4, ale również potrafi zastosować umiejętności rozwiązywania problemów zarówno dla znanych, jak i nieznanych (nowych) przypadków.
Ma podstawową wiedzę na temat złożoności i wydajności algorytmów oraz rozumie znaczenie ich poprawności	nie tylko osiągnął poziom wiedzy i umiejętności wymagany na ocenę 3, ale również ma pogłębioną wiedzę na temat złożoności i wydajności algorytmów oraz rozumie znaczenie ich poprawności	nie tylko osiągnął poziom wiedzy i umiejętności wymagany na ocenę 4, ale również wykazuje się biegłością oraz kreatywnością w dziedzinie badania złożoności algorytmów.
Ma podstawową wiedzę z zakresu elementarnych struktur danych (np. listy kolejki i stosy) oraz potrafi wykonywać podstawowe operacje na tych strukturach.	nie tylko osiągnął poziom wiedzy i umiejętności wymagany na ocenę 3, ale również ma pogłębioną wiedzę z zakresu elementarnych struktur danych (listy kolejki i stosy) oraz operacji na tych strukturach.	nie tylko osiągnął poziom wiedzy i umiejętności wymagany na ocenę 4, ale również wykazuje się biegłością oraz kreatywnością z zakresu elementarnych struktur danych (listy kolejki i stosy) oraz operacji na tych strukturach.
Ma podstawową wiedzę na temat sposobów reprezentowania oraz zastosowań drzew i grafów	nie tylko osiągnął poziom wiedzy i umiejętności wymagany na ocenę 3, ale również ma pogłębioną wiedzę na temat sposobów reprezentowania oraz zastosowań drzew i grafów.	nie tylko osiągnął poziom wiedzy i umiejętności wymagany na ocenę 4, ale również wykazuje się biegłością oraz kreatywnością z zakresu reprezentowania oraz zastosowań drzew i grafów
Ma podstawową wiedzę na temat powszechnie stosowanych algorytmów sortowania, potrafi wyjaśnić ich działanie oraz ocenić złożoność wybranych algorytmów.	nie tylko osiągnął poziom wiedzy i umiejętności wymagany na ocenę 3, ale również ma pogłębioną wiedzę na temat algorytmów sortowania oraz potrafi ocenić złożoność większej liczby algorytmów.	nie tylko osiągnął poziom wiedzy i umiejętności wymagany na ocenę 4, ale również wykazuje się biegłością oraz kreatywnością w zakresie znajomości oraz zastosowań algorytmów sortowania.

Zajęcia w cyklu "Semestr letni 2023/24" (zakończony)

Okres:	2024-02-24 - 2024-06-21	Wybrany podział planu: tygodniowy cykl przedmiotu Przejdź do planu PN WYK WT ĆW ĆW LAB LAB LAB LAB ĆW ĆW LAB LAB ŚR LAB LAB CZ PT
Typ zajęć:	Ćwiczenia, 15 godzin więcej informacji Laboratorium, 15 godzin więcej informacji Wykład, 30 godzin więcej informacji
Koordynatorzy:	Dariusz Rzońca
Prowadzący grup:	Grzegorz Dec, Dominik Ożóg, Dariusz Rzońca
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin

Zajęcia w cyklu "Semestr letni 2024/25" (zakończony)

Okres:	2025-02-27 - 2025-06-22	Wybrany podział planu: tygodniowy cykl przedmiotu Przejdź do planu PN WYK WT LAB LAB ĆW ĆW LAB LAB ĆW ŚR LAB LAB CZ LAB LAB LAB ĆW LAB LAB PT ĆW ĆW
Typ zajęć:	Ćwiczenia, 15 godzin więcej informacji Laboratorium, 15 godzin więcej informacji Wykład, 30 godzin więcej informacji
Koordynatorzy:	Dariusz Rzońca
Prowadzący grup:	Grzegorz Dec, Dominik Ożóg, Mateusz Pomianek, Dariusz Rzońca
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin

Zajęcia w cyklu "Semestr letni 2025/26" (zakończony)

Okres:	2026-02-28 - 2026-06-22	Wybrany podział planu: tygodniowy cykl przedmiotu Przejdź do planu PN WYK WT LAB LAB LAB LAB LAB LAB ĆW ĆW ŚR ĆW ĆW LAB LAB CZ LAB LAB PT ĆW
Typ zajęć:	Ćwiczenia, 15 godzin więcej informacji Laboratorium, 15 godzin więcej informacji Wykład, 30 godzin więcej informacji
Koordynatorzy:	Dariusz Rzońca
Prowadzący grup:	Tomasz Krzeszowski, Mateusz Pomianek, Dariusz Rzońca, Marek Sarnecki
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin

Zajęcia w cyklu "Semestr letni 2026/27" (jeszcze nie rozpoczęty)

Okres:	2027-02-27 - 2027-06-22	Wybrany podział planu: tygodniowy cykl przedmiotu Przejdź do planu PN WT ŚR CZ PT
Typ zajęć:	Ćwiczenia, 15 godzin więcej informacji Laboratorium, 15 godzin więcej informacji Wykład, 30 godzin więcej informacji
Koordynatorzy:	Dariusz Rzońca
Prowadzący grup:	Tomasz Krzeszowski, Mateusz Pomianek, Dariusz Rzońca, Marek Sarnecki
Lista studentów:	(nie masz dostępu)
Zaliczenie:	Egzamin

Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Rzeszowska im. Ignacego Łukasiewicza.