Politechnika Warszawska - Centralny System Uwierzytelniania
Strona główna

Algorytmy matematyki dyskretnej

Informacje ogólne

Kod przedmiotu: 1120-MA000-LSP-0503
Kod Erasmus / ISCED: (brak danych) / (brak danych)
Nazwa przedmiotu: Algorytmy matematyki dyskretnej
Jednostka: Wydział Matematyki i Nauk Informacyjnych
Grupy: Przedmioty obieralne, wydz. MiNI PW
Punkty ECTS i inne: 0 LUB 4.00 (w zależności od programu) 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
Skrócony opis:

Program przedmiotu:

Wykład:

1. Generowanie podstawowych struktur kombinatorycznych.

2. Metody reprezentacji grafów w pamięci komputera.

3. Zastosowanie algorytmów przeszukiwania grafów do badania spójności grafu, wyznaczania drzewa rozpinającego grafu, znajdowania składowych dwuspójnych grafu .

4. Znajdowanie cykli w grafie.

5. Wyznaczanie najkrótszej drogi w grafie.

6. Algorytmy znajdujące minimalne drzewo rozpinające w grafie.

7. Wyznaczanie maksymalnego przepływu w sieci. Zastosowania algorytmów wyznaczających maksymalny przepływ w sieci do rozwiązywania problemów optymalizacyjnych.

8. Problem chińskiego listonosza.

9. Problem komiwojażera. Algorytmy przybliżone.

10. Badanie planarności grafów.

Laboratoria:

Implementacja metod i algorytmów związanych z tematyką przedstawianą na wykładzie (na każdych zajęciach inne zadanie)

Przedmioty poprzedzające: Matematyka Dyskretna, Algorytmy i Struktury Danych

Literatura:

1. L. Banachowski, K. Diks, W. Rytter – „Algorytmy i struktury danych”, WNT, 2006.

2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, Clifford Stein – „Wprowadzenie do algorytmów”, WNT, 2007.

3. W. Lipski – „Kombinatoryka dla programistów”, WNT, 2004.

4. R. Sedgewick – „Algorytmy w C++. Grafy”, Read Me, 2003.

5. M. Sysło, N. Deo, J. Kowalik – „Algorytmy optymalizacji dyskretnej”, PWN 1995.

Metody i kryteria oceniania:

Regulamin zaliczenia przedmiotu:

Wykład: Kolokwium zaliczeniowe na ostatnim wykładzie. 5 zadań analogicznych do przykładów robionych na wykładzie i zadań domowych z listy zadań do samodzielnego rozwiązania. Ich wykonanie wymagać będzie znajomości pojęć i metod przedstawionych na wykładzie. Do zdobycia maksymalnie 40 punktów. Zaliczenie wykładu przy uzyskaniu co najmniej 20 punktów.

Laboratoria:

Za każde zadanie wykonane na laboratoriach można będzie uzyskać określoną liczbę punktów. Za wszystkie zadania będzie można zdobyć maksymalnie 60 punktów. Zaliczenie laboratoriów przy uzyskaniu co najmniej 31 punktów.

Ocena końcowa wyznaczana na podstawie sumy punktów (przy czym aby uzyskać pozytywną ocenę zarówno wykład jak i laboratoria muszą być zaliczone): 51-60 punktów w sumie - 3.0, 61-70 - 3.5, 71-80 - 4.0, 81-90 - 4.5, powyżej 90 - 5.0. Do kolokwium zaliczeniowego dopuszczeni będą wszyscy studenci zapisani na wykład. Możliwe będzie powtórne pisanie kolokwium.

Zajęcia w cyklu "rok akademicki 2020/2021 - sem. letni" (zakończony)

Okres: 2021-02-20 - 2021-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Krzysztof Bryś
Prowadzący grup: (brak danych)
Lista studentów: (nie masz dostępu)
Zaliczenie: Zaliczenie na ocenę

Zajęcia w cyklu "rok akademicki 2019/2020 - sem. letni" (zakończony)

Okres: 2020-02-22 - 2020-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Krzysztof Bryś
Prowadzący grup: Krzysztof Bryś, Kacper Sarnacki
Lista studentów: (nie masz dostępu)
Zaliczenie: Zaliczenie na ocenę

Zajęcia w cyklu "rok akademicki 2018/2019 - sem. letni" (zakończony)

Okres: 2019-02-18 - 2019-09-30
Wybrany podział planu:
Przejdź do planu
Typ zajęć:
Laboratorium, 30 godzin więcej informacji
Wykład, 30 godzin więcej informacji
Koordynatorzy: Krzysztof Bryś
Prowadzący grup: Krzysztof Bryś, Kacper Sarnacki
Lista studentów: (nie masz dostępu)
Zaliczenie: Zaliczenie na ocenę
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Politechnika Warszawska.
pl. Politechniki 1, 00-661 Warszawa tel: (22) 234 7211 https://pw.edu.pl kontakt deklaracja dostępności USOSweb 7.0.0.0-7 (2024-03-18)