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)
|
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 |
Przejdź do planu
PN WT ŚR CZ PT |
Typ zajęć: |
Laboratorium, 30 godzin
Wykład, 30 godzin
|
|
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 |
Przejdź do planu
PN WT ŚR CZ PT |
Typ zajęć: |
Laboratorium, 30 godzin
Wykład, 30 godzin
|
|
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 |
Przejdź do planu
PN LAB
LAB
WT ŚR WYK
CZ PT |
Typ zajęć: |
Laboratorium, 30 godzin
Wykład, 30 godzin
|
|
Koordynatorzy: | Krzysztof Bryś | |
Prowadzący grup: | Krzysztof Bryś, Kacper Sarnacki | |
Lista studentów: | (nie masz dostępu) | |
Zaliczenie: | Zaliczenie na ocenę |
Właścicielem praw autorskich jest Politechnika Warszawska.