Matematyka dyskretna

Liczba godzin wykładu: 30 ćwiczeń: 30 laboratoriów:

Wymagania przedmiotowe

Sylabus

1. Metody dowodzenia twierdzeń i podstawowe prawa przeliczania - Zasada indukcji matematycznej - Zasada szufladkowa - Zasada bijekcji - Prawo dodawania i mnożenia

2. Schematy wyboru i tożsamości kombinatoryczne - Wariacje z powtórzeniami - Wariacje i kombinacje bez powtórzeń - Kombinacje z powtórzeniami - Permutacje z powtórzeniami - Zasada włączania-wyłączania - Notacja asymptoptyczna - Dwumian Newtona

3. Zależności rekurencyjne - Proste zależności rekurencyjne - Liniowe równania rekurencyjne - Ciąg Fibonacciego i liczby Catalana

4. Aparat funkcji tworzących - Formalne szeregi potęgowe - Funkcje tworzące - Uogónienie wzoru Newtona - Rozwiązywanie równań rekurencyjnych

5. Podstawowe pojęcia teorii grafów - Grafy nieskierowane i skierowane - Macierze incydencji i przyległości - Izomorfizm. Grafy oznaczone i nieoznaczone - Podgrafy - Szlaki, spacery, ścieżki, cykle i drzewa - Przeszukiwanie grafów

6. Spójność i najkrótsze ścieżki - Spójność grafów - Krawędź cięcia, wierzchołek cięcia - Silna spójność grafu - Odległości w grafie - Grafy z wagami na krawędziach

7. Drzewa. Rozpięte drzewa - Lasy, drzewa i ich własności - Drzewa rozpięte - wzór rekurencyjny - Minimalne drzewa rozpięte - Kod Pruffera

8. Skojarzenia w grafach - Twierdzenia Berge'a i Halla - Problem optymalnego przydziału zadań

9. Obchody Eulera i cykle Hamiltona - Grafy Eulera - Problem chińskiego listonosza - Grafy Hamiltona - Problem wędrującego komiwojażera

10. Przepływy w sieciach - Przepływ w sieci - Twierdzenie Forda-Fulkersona - Przepływ o minimalnym koszcie

11. Kolorowanie wierzchołków i krawędzi grafu - Liczba i indeks chromatyczny - Twierdzenia Brooksa i Vizinga - Kolorowanie krawędzi grafu

12. Grafy planarne i kolorowanie map - Grafy płaskie i dualne do nich - Twierdzenie Kuratowskiego, wzór Eulera - Mapy i ich kolorowanie. Problem czterech kolorów

Cel przedmiotu

Przedmiot poświęcony jest podstawowym pojęciom, problemom i metodom matematyki dyskretnej, w tym również podstawom teorii grafów.

Literatura

Nazwa przedmiotu w języku angielskim

Wymagania przedmiotowe (w j. angielskim)

Sylabus (w j. angielskim)

Cel przedmiotu (w j. angielskim)


KategoriaPrzedmiot

Sylabus: Matematyka dyskretna (ostatnio edytowane 2011-05-24 10:13:00 przez localhost)