1DI1302 - Algorytmy i struktury danych

Course secondName name: 

Algorithms and Data Structures

Course is a part of following study programmes:

• Informatyka Stosowana Semester: 3 Study stage: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Study plan version (The specialization can have different study programme versions. This number indicates the study plan version.): WPS2018Z/2019L
• Informatyka Stosowana Semester: 3 Study stage: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Study plan version (The specialization can have different study programme versions. This number indicates the study plan version.): WPS2024Z/2025L
• Informatyka Stosowana Semester: 3 Study stage: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Study plan version (The specialization can have different study programme versions. This number indicates the study plan version.): WPS2019Z/2020L
• Informatyka Stosowana Semester: 3 Study stage: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Study plan version (The specialization can have different study programme versions. This number indicates the study plan version.): WPS2016Z/2017L
• Informatyka Stosowana Semester: 3 Study stage: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Study plan version (The specialization can have different study programme versions. This number indicates the study plan version.): WPS2023Z/2024L
• Informatyka Stosowana Semester: 3 Study stage: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Study plan version (The specialization can have different study programme versions. This number indicates the study plan version.): WPS2017Z/2018L
• Informatyka Stosowana Semester: 3 Study stage: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Study plan version (The specialization can have different study programme versions. This number indicates the study plan version.): WPS2021Z/2022L
• Informatyka Stosowana Semester: 3 Study stage: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Study plan version (The specialization can have different study programme versions. This number indicates the study plan version.): WPS2020Z/2021L
• Informatyka Semester: 3 Study stage: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Study plan version (The specialization can have different study programme versions. This number indicates the study plan version.): 13
• Informatyka Semester: 3 Study stage: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Study plan version (The specialization can have different study programme versions. This number indicates the study plan version.): 14
• Informatyka Stosowana Semester: 3 Study stage: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Study plan version (The specialization can have different study programme versions. This number indicates the study plan version.): 22
• Informatyka Stosowana Semester: 3 Study stage: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Study plan version (The specialization can have different study programme versions. This number indicates the study plan version.): 21
• Informatyka Semester: 3 Study stage: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Study plan version (The specialization can have different study programme versions. This number indicates the study plan version.): 12
• Informatyka Stosowana Semester: 3 Study stage: Model 2, inżynierskie I-go stopnia, stacjonarne, polski, Study plan version (The specialization can have different study programme versions. This number indicates the study plan version.): WPS2022Z/2023L

Ellective in catalogs:

Found 0 items. (Show details)

Short content: 

Zapoznanie studenta z następującymi zagadnieniami: metody tworzenia algorytmów i dowodzenia ich poprawności, pojęcie złożoności obliczeniowej czasowej i pamięciowej, najczęściej używane struktury danych: listy, drzewa, kopce, tablice, grafy, hasze i związane z nimi algorytmy, relacja pomiędzy danymi i algorytmami, podstawowe abstrakcyjne typy danych: kolejki, zbiór, słownik. Wybrane algorytmy przetwarzania danych: sortowanie tablic, operacje na drzewach binarnych i BST, kompresja, algorytmy dla grafów, wyszukiwanie wzorca. Problemy NP trudne, NP-zupełność, sztuczna inteligencja jako metoda rozwiązywania problemów o wielkiej złożoności obliczeniowej.
Kurs jest podstawą do tworzenia oprogramowania we wszystkich językach imperatywnych. Przygotowuje studenta do pracy jako projektant oprogramowania, programista, analityk oprogramowania.

Syllabus details: 

Podstawowe pojęcia, złożoność obliczeniowa. Analiza algorytmów i dowodzenie poprawności. Algorytmy sortowania tablic. Sortowanie o złożoności liniowej. Struktury wykorzystujące wskaźniki: listy, drzewa, grafy. Listy liniowe, drzewa wyważone, haszowanie. Opakowywanie struktur danych, abstrakcyjne typy danych. Kontenery w Javie. Wybrane algorytmy kompresji. Programowanie dynamiczne. Wybrane algorytmy działające na grafach. Wyszukiwanie wzorca w napisach. Algorytmy ewolucyjne. Problemy NP-zupełne.

Literature: 

1. Cormen, Leiserson, Rivest, Stein - Wprowadzenie do algorytmów, wyd. 2, WNT 2004;
2. Lafore - Java. Algorytmy i struktury danych, Helion 2003
3. Knuth - Sztuka programowania, WNT 2002

Grading criteria: 

Zgodnie z regulaminem kursu.

Notes: 

Courses which this course is based on (prerequisities):

• [1DI1206] Języki i metody programowania 2
• [1DI1108] Języki i metody programowania 1

• Educational effect for specializations Informatyka Stosowana, Informatyka Stosowana:
• Wiedza

  Kod	Efekt Kształcenia dla kierunku	Procent	Efekt kształcenia dla przedmiotu	Sposób sprawdzania
  I1_W04a	ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu podstaw programowania	+ (33%)	ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu podstaw programowania	egzamin
  I1_W04b	ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu algorytmów i złożoności	+++ (100%)	ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu algorytmów i złożoności obliczeniowej	egzamin
  I1_W04f	ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu języków i paradygmatów programowania	++ (66%)	ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu kodowania algorytmów w językach proceduralnych i obiektowych	egzamin, projekty
  I1_W04j	ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu inżynierii oprogramowania	++ (66%)	ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu roli algorytmów w programach komputerowych	egzamin, projekty
  I1_W05c	ma szczegółową wiedzę związaną z zagadnieniami z wybranego zakresu informatyki, dotyczącą analizy i projektowania oprogramowania	++ (66%)	ma szczegółową wiedzę związaną z zagadnieniami z analizy i projektowania algorytmów	egzamin, projekt
  I1_W06a	ma podstawową wiedzę o trendach rozwojowych z zakresu informatyki	+ (33%)	ma podstawową wiedzę o trendach rozwojowych z zakresu algorytmiki	egzamin
  I1_W08a	zna podstawowe, stosowane przy rozwiązywaniu prostych zadań inżynierskich z zakresu informatyki metody	+ (33%)	zna podstawowe, stosowane przy rozwiązywaniu prostych zadań inżynierskich z zakresu Informatyki - metody projektowania algorytmów	egzamin

• Umiejętności

  Kod	Efekt Kształcenia dla kierunku	Procent	Efekt kształcenia dla przedmiotu	Sposób sprawdzania
  E1_U05	Potrafi planować własne uczenie się, ma umiejętności samokształcenia.	++ (66%)	ma umiejętności samokształcenia się	egzamin, projekt
  I1_U01	Potrafi pozyskiwać informacje z literatury, baz danych oraz innych właściwie dobranych źródeł w wersji drukowanej i elektronicznej, w tym w Internecie, także w języku angielskim albo francuskim lub niemieckim w zakresie informatyki, potrafi integrować uzyskane informacje, dokonywać ich interpretacji, a także wyciągać wnioski, formułować i uzasadniać opinie.	++ (66%)	potrafi pozyskiwać informacje z literatury, baz danych oraz innych właściwie dobranych źródeł w wersji drukowanej i elektronicznej w tym w Internecie, także w języku angielskim lub niemieckim w zakresie Informatyki, potrafi integrować uzyskane informacje	projekt
  I1_U02	Potrafi porozumiewać się przy użyciu różnych technik w środowisku zawodowym związanym z informatyką oraz w innych środowiskach.	++ (66%)	potrafi porozumiewać się przy użyciu różnych technik w środowisku zawodowym związanym z Informatyką oraz w innych środowiskach	projekt zespołowy
  I1_U04	Potrafi przygotować i przedstawić w języku polskim i języku angielskim albo francuskim lub niemieckim prezentację ustną, dotyczącą szczegółowych zagadnień z zakresu informatyki.	+ (33%)	potrafi przygotować i przedstawić w języku polskim prezentację ustną, dotyczącą szczegółowych zagadnień z zakresu Informatyki - algorytmika	egzamin ustny
  I1_U08b	potrafi planować i przeprowadzać eksperymenty, w tym symulacje komputerowe	+ (33%)	potrafi planować i przeprowadzać symulacje komputerowe, interpretować uzyskane wyniki i wyciągać wnioski	projekt
  I1_U08c	potrafi planować i przeprowadzać eksperymenty, w tym interpretować uzyskane wyniki i wyciągać wnioski	+ (33%)	potrafi planować i przeprowadzać symulacje komputerowe, interpretować uzyskane wyniki i wyciągać wnioski	projekt
  I1_U15	Potrafi ocenić przydatność rutynowych metod i narzędzi służących do rozwiązania prostego zadania inżynierskiego o charakterze praktycznym, charakterystycznego dla informatyki oraz wybrać i zastosować właściwą metodę i narzędzia.	+ (33%)	potrafi ocenić przydatność rutynowych metod i narzędzi służących do rozwiązania prostego zadania inżynierskiego o charakterze praktycznym, charakterystycznego dla Informatyki oraz wybrać i zastosować właściwą metodę i narzędzia	projekt
  I1_U16	Potrafi, zgodnie z zadaną specyfikacją, zaprojektować oraz zrealizować proste urządzenie, obiekt, system lub proces, typowe dla informatyki, używając właściwych metod, technik i narzędzi.	+ (33%)	potrafi zaprojektować oraz zrealizować, przy użyciu właściwych metod, technik i narzędzi, zgodnie z zadaną specyfikacją, typowe dla Informatyki, prosty system	projekt

• Kompetencje społeczne

  Kod	Efekt Kształcenia dla kierunku	Procent	Efekt kształcenia dla przedmiotu	Sposób sprawdzania
  E1_K01	Jest przygotowany do przeprowadzenie krytycznej analizy posiadanej wiedzy, ma świadomość posiadanych kompetencji i umie pozyskać informacje potrzebne do realizacji postawionych przed nim zadań.	+ (33%)	rozumie potrzebę uczenia się przez całe życie, potrafi inspirować i organizować proces uczenia się innych osób	projekt
  E1_K03	Jest przygotowany do współdziałania i pracy w grupie, przyjmowania w niej różnych ról, działając zawodowo na rzecz społeczeństwa.	+ (33%)	potrafi współdziałać i pracować w grupie, przyjmując w niej różne role	projekt zespołowy

• • ECTS with teacher assistance: 3 
  • ECTS on practical activities: 5 
• • ECTS justification:

  • Zajęcia kontaktowe z nauczycielem: 

    Uczestnictwo w wykładach pozwala zdobyć wiedzę z zakresu przedmiotu, konsultacje i nadzór nad realizacją projektu i egzamin są elementami porządkowania i weryfikacji wiedzy i umiejętności.

  • Classes / work without teacher assistance: 

    Wykonanie projektów i przygotowanie do egzaminu wymaga dodatkowej pracy samokształceniowej: studiowania literatury i praktycznej pracy nad oprogramowaniem.

  • • Total number of student hours: 120 
  • Total number of ECST reflects the total number of hours of student's work.