Uniwersytet Marii Curie-Skłodowskiej w Lublinie - Centralny System Uwierzytelniania
Strona główna

Algorytmy i struktury danych II

Informacje ogólne

Kod przedmiotu: MFI-I.2L.002
Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Algorytmy i struktury danych II
Jednostka: Wydział Matematyki, Fizyki i Informatyki
Grupy:
Strona przedmiotu: https://kampus.umcs.pl/course/view.php?id=644
Punkty ECTS i inne: (brak) 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.

zobacz reguły punktacji
Język prowadzenia: polski
Wymagania wstępne:

Umiejętność programowania w języku C++, znajomość podstaw matematyki oraz algorytmiki.

Przedmioty wprowadzające:

- Podstawy programowania.

- Programowanie obiektowe.

- Algebra liniowa z geometrią,

- Logika i teoria mnogości

- Matematyka dyskretna.

- Algorytmy i struktury danych I

Godzinowe ekwiwalenty punktów ECTS:

1. Godziny kontaktowe z nauczycielem akademickim

-wykład 30,

-laboratorium 30,

-konsultacje 2,

-egzamin 3.

Razem 65.


2. Samodzielna praca studenta

- samodzielne rozwiązywanie zadań programistycznych 35,

- przygotowanie się do laboratorium 10,

- przygotowanie się do egzaminu 10.


Razem 55.


Samodzielna praca studenta + godziny kontaktowe = 120


Liczba punktów ECTS - 4 w tym 2,17 za godziny kontaktowe oraz 1,83 za samodzielną pracę studentów.

Sposób weryfikacji efektów kształcenia:

Kartkówki - W1.

Programy zaliczeniowe - W1, W2, U1, U2, K1, K2,K3.

Aktywność - K1.

Egzamin przy komputerach - W1, U1, U2, K1.

Pełny opis:

Celem przedmiotu jest zapoznanie studentów z podstawowymi strukturami danych i algorytmami. Wyrobienie u studentów umiejętności tworzenia, analizy i implementacji prostych algorytmów oraz ich wykorzystania do rozwiązywania problemów występujących w praktyce. Laboratoria są skorelowane z wykładem. Utrwala się na nich materiał poznany na wykładzie i rozwiązuje zadania algorytmiczne związane z tematami poszczególnych wykładów.

Tematy poruszane na zajęciach:

1. Algorytmy grafowe:

-znajdowanie najkrótszej ściezki (BFS, alg. Dijkstry, alg. Forda-Bellmana, alg. Floyda-Warshalla),

-znajdowanie minimalnego drzewa rozpinającego graf (alg. Prima, alg. Kruskala),

-znajdowanie maksymalnego przepływu w grafie, skojarzenia w grafie dwudzielnym (alg. Edmondsa-Karpa).

2. Słowniki

- drzewa poszukiwań binarnych (BST),

- drzewa czerwono-czarne,

-drzewa splay,

- B-drzewa,

- drzewa trie,

- tablice haszujące.

3. Algorytmy geometryczne (metoda zamiatania, metoda zamiatania polarnego, szukanie najmniej odległej pary punktów na płaszczyźnie, algorytm Grahama).

4. Algorytmy tekstowe (algorytm Morrisa-Pratta, algorytm Knutha-Morrisa-Pratta, algorytm Karpa-Rabina, algorytm Karpa-Millera-Rosenberga).

5. Algorytmy probabilistyczne (algorytmy Monte Carlo, algorytmy Las Vegas, problem pięciu filozofów, sprawdzanie pierwszości liczby, generatory liczb pseudolosowych).

6. Metody numeryczne (wzór Taylora, Metoda Newtona, interpolacja wielomianowa, całkowanie interpolacyjne).

7. Elementy teorii złożoności.

Literatura:

Literatura podstawowa:

Cormen Thomas H.,Leiserson Charles E., Rivest Ronald L., Stein Clifford, Wprowadzenie do algorytmów, Wydawnictwo NT, Warszawa 2007.

Slajdy z wykładu.

Literatura uzupełniająca

Lech Banachowski, Krzysztof Diks, Wojciech Rytter, Algorytmy i struktury danych, Wydawnictwo NT, Warszawa 2003.

D.Knuth, Sztuka programowania, Wydawnictwo NT, Warszawa 2001.

Ważniak -- http://wazniak.mimuw.edu.pl -- kursy: Metody programowania, Algorytmy i struktury danych, Zaawansowane algorytmy i struktury danych.

Efekty uczenia się:

WIEDZA

W1. Zna podstawowe algorytmy, metody ich konstruowania oraz sposoby analizy - K_W02, K_W04, K_W05, K_W09, K_W10.

W2. Zna dobre praktyki programistyczne -

UMIEJĘTNOŚCI

U1. Posiada umiejętność dobierania odpowiednich struktur danych i algorytmów do wskazanych problemów - K_U09;

U2. Umie ułożyć i analizować algorytm zgodny ze specyfikacją oraz zaimplementować go w języku C++- K_U03, K_U05, K_U06;

KOMPETENCJE SPOŁECZNE

K1. Kreatywność w rozwiązywaniu problemów informatycznych – K_K02

K2. Systematyczność - K_K03

K3. Postępowanie zgodnie z zasadami etyki - K_K04.

Przedmiot nie jest oferowany w żadnym z aktualnych cykli dydaktycznych.
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Marii Curie-Skłodowskiej w Lublinie.
kontakt deklaracja dostępności USOSweb 7.0.2.0-3dcdfd8c8 (2024-03-25)