Uniwersytet Mikołaja Kopernika w Toruniu - Centralny punkt logowaniaNie jesteś zalogowany | zaloguj się
katalog przedmiotów - pomoc

Teoria grafów w ujęciu algorytmicznym

Informacje ogólne

Kod przedmiotu: 1000-I1Z1101 Kod Erasmus / ISCED: (brak danych) / (0613) Tworzenie i analiza oprogramowania i aplikacji
Nazwa przedmiotu: Teoria grafów w ujęciu algorytmicznym
Jednostka: Wydział Matematyki i Informatyki
Grupy: Inf., I st., stacjonarne, 2 rok, przedmioty do wyboru
Inf., I st., stacjonarne, 3 rok, przedmioty do wyboru
Inf., II st, stacjonarne, przedmioty do wyboru
Wszystkie przedmioty z WMiI
Punkty ECTS i inne: 6.00
Język prowadzenia: polski
Wymagania wstępne:

Wstęp do informatyki - znajomość podstawowych konstrukcji algorytmicznych/programistycznych.

Elementy matematyki dyskretnej - elementy złożoności obliczeniowej, podstawowe algorytmy matematyki dyskretnej (poszukiwania, porządkowanie)

Algorytmy i struktury danych = podstawowe algorytmy i struktury danych (lista, tablica, kolejka, stos, struktury dynamiczne).

Rodzaj przedmiotu:

przedmiot fakultatywny

Całkowity nakład pracy studenta:

6 punktów ECTS

Efekty uczenia się - wiedza:

Wiedza z podstawowego zakresu teorii grafów i algorytmicznego rozwiązywania problemów grafowych.

Efekty uczenia się - umiejętności:

Umiejętność stosowania metod algorytmicznych do problemów definiowanych na grafach, w tym także na grafach z obciążonymi wierzchołkami i połączeniami.

Efekty uczenia się - kompetencje społeczne:

Wiele problemów grafowych odnosi się do relacji, które mogą modelować relacje społeczne. Teoria grafów dostarcza wielu metod analizy i obliczeń w obszarze kontaktów społecznych. Na ile przekłada się to na kompetencje społeczne - trudno określić.

Metody dydaktyczne:

Wykład połączony z ćwiczeniami. Problemowy sposób wprowadzania treści, ich wyjaśnienia, a następnie rozwiązywania problemów na ćwiczeniach.


Ponadto, zagadnienia teoretyczne są traktowane w sposób algorytmiczny/informatyczny. Na przykład, dowody moją postać algorytmów i uzasadnienia ich poprawności. Przy okazji analizowana jest złożoność obliczeniowa prezentowanych metod algorytmicznych.

Metody dydaktyczne podające:

- wykład informacyjny (konwencjonalny)
- wykład problemowy

Metody dydaktyczne poszukujące:

- ćwiczeniowa

Skrócony opis:

Grafy występują w wielu obszarach matematyki, takich jak: kombinatoryka, teoria macierzy, algebra, logika, optymalizacja. Wraz z rozwojem informatyki, grafy nabrały dużego znaczenia jako modele obliczeniowe. Stało się to źródłem algorytmicznych technik, stosowanych zarówno w rozważaniach teoretycznych, jak i w rozwiązywaniu praktycznych problemów grafowych.

Najciekawsze jest połączenie teorii z podejściem algorytmicznym, które zapewnia teoretyczną poprawność rozważań, a jednocześnie dostarcza rozwiązań algorytmicznych. Typowe dla algorytmicznego podejścia są dowody algorytmiczne twierdzeń, będące jednocześnie dowodami twierdzeń i źródłem algorytmów, dla których te twierdzenia są dowodami ich poprawności.

Celem tych zajęć jest przedstawienie podstawowych rezultatów z zakresu algorytmicznej teorii grafów, klasycznych, jak i najnowszych kierunków badan. Ćwiczenia są okazją do rozwinięcia materiału z wykładu i praktycznej weryfikacji wybranych rozwiązań algorytmicznych.

Pełny opis:

1. Cele

Grafy występują w wielu obszarach matematyki, doczekały się również swojej teorii, którą można przedstawiać na gruncie innych dziedzin matematyki, takich jak: kombinatoryka, teoria (rachunek) macierzy, algebra, logika, algorytmy i struktury danych, optymalizacja kombinatoryczna. Wraz z rozwojem informatyki, grafy nabrały dużego znaczenia jako strukturalne modele obliczeniowe wielu sytuacji teoretycznych i praktycznych. Stało się to źródłem algorytmicznych technik, stosowanych zarówno w rozważaniach teoretycznych, jak i w rozwiązywaniu praktycznych problemów grafowych.

Najciekawsze jest połączenie teorii z podejściem algorytmicznym, które zapewnia teoretyczną poprawność rozważań, a jednocześnie dostarcza rozwiązań algorytmicznych. Typowe dla algorytmicznego podejścia są dowody algorytmiczne twierdzeń, będące jednocześnie dowodami twierdzeń i źródłem algorytmów, dla których te twierdzenia są dowodami ich poprawności.

Celem tych zajęć jest przedstawienie podstawowych rezultatów z zakresu algorytmicznej teorii grafów, zarówno klasycznych, jak i najnowszych kierunków badan. Ćwiczenia będą okazją do rozwinięcia materiału z wykładu i praktycznej weryfikacji wybranych rozwiązań algorytmicznych.

Materiał tych zajęć może być przydatny podczas zajęć z zakresu algebry, optymalizacji dyskretnej i kombinatorycznej, złożoności obliczeniowej, niektórych działów metod numerycznych.

2. Treści

1. Algorytmy, struktury danych, złożoność obliczeniowa – przypomnienie i rozwinięcie

2. Elementy teorii grafów

• elementy grafów i ich własności: drogi, cykle, drzewa częściowe, skojarzenia, pokrycia;

• algorytmy na grafach – przeszukiwanie grafów, grafowe struktury danych;

• stopnie wierzchołków;

• izomorfizm i automorfizm grafów;

• rodzaje grafów: grafy dwudzielne, planarne, doskonałe, grafy przecięć – charakteryzacje i algorytmy.

3. Drzewa

• jako grafy – charakteryzacje, własności;

• jako podgrafy rozpinające grafy – szczególne typy, zastosowania;

• jako modele algorytmów – wnioski algorytmiczne;

• uogólnienia drzew: drzewa Steinera, k-drzewa.

4. Wybrane problemy teorio-grafowe i ich algorytmiczne aspekty

• istnienie i własności dróg i cykli, w tym problemy eulerowskie i hamiltonowskie;

• kolorowanie wierzchołków i krawędzi grafach, w szczególności w grafach planarnych;

• skojarzenia i pokrycia w grafach – przykłady związków minimaksowych, zastosowania.

5. Zbiory częściowo uporządkowane (posety)

• własności posetów;

• reprezentacje grafowe poset i ich własności oraz zastosowania;

• problemy kombinatoryczne na posetach – optymalne rozszerzenia liniowe i ich zastosowania.

Literatura:

Literatura podstawowa:

1. Corman T.H., Leiserson C.E., Rivest R.L., Wprowadzenie do algorytmów, WNT, Warszawa 1997.

2. Diestel R., Graph Theory, Springer, Heidelberg 2005.

3. Lipski W., Kombinatoryka dla programistów, WNT, Warszawa 1982.

4. Sysło M.M., Deo N., Kowalik J.S., Algorytmy optymalizacji dyskretnej z programami w języku Pascal, WN PWN, Warszawa 1993, 1995, 1997.

5. Sysło M.M., Piramidy, szyszki i inne konstrukcje algorytmiczne, WSiP, Warszawa 1998.

6. West D.B., Introduction to Graph Theory, 2nd edition, Prentice Hall, 2001.

7. Wilson R.J., Wprowadzenie do teorii grafów, WN PWN, Warszawa 1998.

Literatura uzupełniająca:

8. Coffman E.G., Jr. (red.), teoria szeregowania zadań, WNT, Warszawa 1980.

9. Ford L.R. Jr., Fulkerson D.R., Przepływy w sieciach, PWN, Warszawa 1969.

10. Graham R.L., Knuth D.E., Patashnik O., Matematyka konkretna, WN PWN, Warszawa 1996.

11. Korte B., Vygen J., Combinatorial Optimization. Theory and Algorithms. 3rd edition, Springer, Heidelberg 2006.

12. Schrijver A., Combinatorial Optimization: Polyhedra and Efficiency, Vol. A-C, Springer, Heidel-berg 2003.

13. Sysło M.M., Algorytmy, WSiP, Warszawa 1997, 2002.

14. Vazirani V.V., Algorytmy aproksymacyjne, WNT, Warszawa 2005.

Metody i kryteria oceniania:

- ocena ciągła, bieżące przygotowanie do zajęć

- końcowe zaliczenie ćwiczeń na podstawie aktywności na zajęciach

- pisemny egzamin końcowy

Praktyki zawodowe:

Nie przewiduje się praktyk zawodowych związanych z tym przedmiotem.

Zajęcia w cyklu "Semestr zimowy 2017/18" (zakończony)

Okres: 2017-10-01 - 2018-02-25
Wybrany podział planu:


powiększ
zobacz plan zajęć
Typ zajęć: Laboratorium, 30 godzin, 16 miejsc więcej informacji
Wykład, 30 godzin, 150 miejsc więcej informacji
Koordynatorzy: Maciej Sysło
Prowadzący grup: Maciej Sysło
Lista studentów: (nie masz dostępu)
Zaliczenie: Przedmiot - Egzamin
Laboratorium - Zaliczenie na ocenę
Wykład - Egzamin
Opisy przedmiotów w USOS i USOSweb są chronione prawem autorskim.
Właścicielem praw autorskich jest Uniwersytet Mikołaja Kopernika w Toruniu.