1862543793

4 Matematyka w Informatyce i Zarządzaniu | ZIVs7-TGl | TEORIA GRAFÓW I |

Cele przedmiotu: Zapoznanie studentów z podstawowymi pojęciami i twierdzeniami teorii grafów oraz jej zastosowaniami.

Zawartość programowa:

1.    Spójność grafu (4 godziny). Usystematyzowanie i poszerzenie definicji i notacji teorii grafów. Izomorfizm grafów, grupa automorfizmów grafu. Hipoteza rekonstrukcyjna Ulama. Spójność wierzchołkowa i spójność krar wędziowa grafu. Twierdzenia Mengera. Związek twierdzeń Mengera z twierdzeniami minimaksowymi.

2.    Trawersowanie grafów (10 godzin). Cykl i droga Eulera. Charakteryzacja multigrafów eulerowskich i jed-nobieżnych. Znajdowanie cyklu i drogi Eulera - algorytm Fleury’ego. Zadanie chińskiego listonosza - algorytm Edmondsa-Johnsona. Cykl i ścieżka Hamiltona, grafy hamiltonowskie i trasowalne. Domknięcie Bondy’ego-Chvatala grafu. Stabilność własności grafów. Twierdzenia Orego, Diraca, Fana i Chvatala-Erdósa. Inne własności typu hamiltonowskiego. Problem komiwojażera. Rozkład grafu na podgrafy izomorficzne. Systemy trójek Steinera. Rozkład grafu pełnego na cykle Hamiltona.

3.    Drzewa i grafy planarne (8 godzin). Definicja drzewa i warunki równoważne. Problemy alokacji w grafach. Twierdzenie Cayleya o liczbie drzew etykietowanych. Kody Priifera. Graf topologiczny. Graf płaski i graf planarny. Graf dualny do grafu płaskiego. Wzór Eulera dla wielościanów. Bryły platońskie. Minor i minor topologiczny grafu. Twierdzenie Kuratowskiego. Zanurzanie grafów w powierzchnie rodzaju dodatniego.

4.    Kolorowanie grafów (8 godzin). Kolorowanie wierzchołków grafu. Liczba chromatyczna grafu. Twierdzenie Brooksa. Wielomian chromatyczny grafu. Twierdzenie o rozkładzie wielomianu chromatycznego. Historia twierdzenia o czterech kolorach. Kolorowanie wierzchołków z list; twierdzenie Thomassena o pięciu kolorach. Kolorowanie krawędzi grafu. Indeks chromatyczny grafu. Twierdzenie Wizinga i problem klasyfikacji grafów. Twierdzenie Kóniga o indeksie chromatycznym grafu dwudzielnego. Kolorowanie krawędzi z list.

Literatura:

1. R.J. Wilson, Wprowadzenie do teorii grafów, PWN, Warszawawa 2000.

Liczba godzin: 30 godzin wykładu + 30 godzin ćwiczeń.

Forma zaliczenia: ćwiczenia: 2 kolokwia pisemne plus ocena aktywności studenta na ćwiczeniach. Egzamin ustny, sprawdzający znajomość pojęć i twierdzeń oraz wskazanych dowodów poznanych na wykładzie.

OVs9/ZIVs7-SBD | STRUKTURY I BAZY DANYCH

ZIVs7-ZO I ZŁOŻONOŚĆ OBLICZENIOWA

Cele przedmiotu: Przedstawienie zagadnień związanych ze złożonością obliczeniową oraz metod dowodzenia trudności pewnych problemów dyskretnych. Pokazanie sposobów rozwiązywania dyskretnych problemów obliczeniowo trudnych.

Zawartość programowa:

1.    Maszyna RAM. Maszyna Turinga (8 godzin). Podstawowe pojęcia teorii złożoności obliczeniowej. Definicja maszyny RAM i maszyny Turinga. Techniki upraszczające proces pisania oraz modyfikacje maszyny Turinga. Teza Churcha. Złożoność czasowa i pamięciowa. Hierarchie złożoności. Twierdzenie Savitcha.

2.    Klasy problemów P i NP. Problemy AP-zupełne (10 godzin). Problemy decyzyjne. Transformacja wielomianowa. Twierdzenie Cooka. Sześć najsławniejszych problemów NP-zupełnych. Techniki dowodzenia AP-zupełności.

3.    Analiza złożoności problemów i podproblemów za pomocą AP-zupełności (4 godziny). Analiza pod-problemów. Problem 3-kolorowalności grafu. Twierdzenie Brooksa. Problemy liczbowe i silna AP-zupełność. Transformacja pseudowielomianowa. Problem 3-podziału.

4.    Algorytmy aproksymacyjne (8 godziny). Problemy optymalizacyjne. Transformacja w sensie Turinga. Pro-