Matematyka dyskretna

Zasady zaliczenia

Ćwiczenia są zaliczane na podstawie obecności, która jest obowiązkowa, można mieć do 3 nieusprawiedliwionych nieobecności. Ocena za cały kurs będzie wystawiana na podstawie punktów, przydzielanych za:

  • zaliczenie wykładu: 50 pkt
  • 2 kolokwia na ćwiczeniach: 2 × 10 pkt (przemnożone przez 1.5 i zaokrąglone w górę)
  • aktywność na ćwiczeniach: 20 pkt

    • Wyniki zaliczeń pisemnych mogą być weryfikowane przez prowadzących.


    Ocena będzie wystawiana na podstawie skali

  • 50-59 pkt: 3.0
  • 60-69 pkt: 3.5
  • 70-79 pkt: 4.0
  • 80-89 pkt: 4.5
  • 90-100 pkt: 5.0
  • 90-100 pkt: 5.0

    • Listy zadań

  • Lista 0
  • Lista 1
  • Lista 2
  • Lista 3
  • Lista 4
  • Lista 5
  • Lista 6
  • Lista 7
  • Lista 8
  • Lista 9
  • Lista 10

    • Zagadnienia zaliczeniowe

    Teoria informacji:

  • Entropia, entropia łączna, entropia warunkowa, informacja wzajemna, entropia względna. Metody ich obliczania. Podstawowe własności, relacje między nimi, diagram Venna entropii.
  • Nierówność Jensena.
  • Kodowanie, kodowanie jednoznacznie dekodowalne, kodowanie przedrostkowe i jego drzewo decyzyjne. Średnia długość kodowania.
  • Nierówność Krafta. Nierówność informacyjna dla kodowań.
  • Kodowanie Huffmana.
  • Pojęcie kanału komunikacyjnego oraz pojemności kanału informacyjnego.
  • Prawdopodobieństwa wejściowe (a priori) i wyjściowe (a posteriori) kanału.
  • Pojemność kanału symetrycznego.

    • Rekursja:

  • Definicja wzoru rekurencyjnego. Przykłady: silnia, ciąg Fibonacciego.
  • Rekursja liniowa o stałych współczynnikach. Wielomian charakterystyczny. Rozwiązania z pojedynczymi oraz wielokrotnymi pierwiastkami wielomianu charakterystycznego. Rozwiązania równań jednorodnych i niejednorodnych.
  • Operator przesunięcia. Funkcje generujące i ich podstawowe własności. Rozwiązywanie problemów rekursji liniowej za pomocą funkcji generujących.
  • Notacja dużego O, Θ oraz Ω. Uniwersalne twierdzenie o rekursji i jego zastosowanie do analizy złożoności algorytmów rekurencyjnych.

    • Grafy:

  • Podstawowe typy i rodzaje grafów.
  • Problem mostów królewickich. Znajdowanie spacerów po grafie (zamkniętych i otwartych).
  • Drzewa i ich podstawowe własności. Znajdowanie drzew rozpinających i minimalnych drzew rozpinających algorytmem Prima.
  • Drzewa binarne. Drzewa składniowe (AST). Zapisywanie wyrażeń za pomocą AST. Notacja polska i AST.
  • Kompletne drzewa binarne i ich kodowanie.

    • Zaliczenie poprawkowe

    Termin: 05.07 (piątek) godz. 13:15. Miejsce: sala A.1.14 w C19. Do zaliczenia tego kursu zdający musi umieć:

  • Obliczać entropię, entropię łączną, warunkową, informację wzajemną, entropię relatywną, kiedy rozkład zmiennych jest znany.
  • Korzystać z diagramów Venna do obliczania różnych rodzajów entropii. Korzystać z niezależności zmiennych. Korzystać z jednoznacznej zależności zmiennych (tj. gdy Y jest 1-1 funkcją X).
  • Obliczać średnią długość kodowania.
  • Kodować za pomocą algorytmu Huffmana.
  • Obliczać prawdopodobieństwa wyjściowe p(y) oraz prawdopodobieństwa a posteriori p(x|y) w kanale informacyjnym, mając dane prawdopodobieństwa wejściowe p(x) oraz prawdopodobieństwa przejścia p(y|x).
  • Rozpoznawać kanały symetryczne oraz obliczać ich pojemność.
  • Używać rekursji oraz indukcji do analizy ciągów, np. do udowadniania ich prostych własności.
  • Obliczać rekurencyjnie wartości silni i ciągu Fibonacciego.
  • Podawać postać ogólną rozwiązania liniowego równania rekurencyjnego o stałych współczynnikach oraz uwzględnić warunki początkowe. Też dla równania jednorodnego oraz niejednorodnego; gdy wartości własne wielomianu charakterystycznego są różne lub się powtarzają.
  • Korzystać z funkcji generujących do rozwiązywania równań liniowych, w których niejednorodność jest zmienna w czasie, ale ma znaną prostą funkcję generującą. Obejmuje to tylko przypadki, w których otrzymana funkcja generująca będzie funkcją wymierną.
  • Rozpoznawać podstawowe klasy grafów i przykłady grafów.
  • Wzorując się na problemie mostów królewickich wyznaczać spacery po grafie, które przez każdą krawędź przechodzą tylko 1 raz. Trzy przypadki: kiedy istnieje spacer otwarty (początek i koniec nie w tym samym wierzchołku), spacer zamknięty (tj. cykl), kiedy nie istnieje ani jedno ani drugie.
  • Podawać przykładowe drzewa rozpinające grafu wyznaczone dowolną metodą.
  • Podawać minimalne drzewo rozpinające dla grafu ważonego wyznaczone metodą Prima.
  • Konstruować drzewa składniowe. Sczytywać wyrażenia z drzew składniowych w notacji standardowej (wrostkowej) i polskiej (przedrostkowej).

    • Zadania na zaliczeniu będą bezpośrednio odnosić się do powyższych podpunktów, prosząc o ich zastosowanie na konkretnych przykładach. Próg zaliczenia to 70%.

    Wyniki

    Indeks Wykład Indeks Wykład
    276021 25 277444 28
    276054 28 277434 32
    277446 29 277489 25
    277492 25 276003 24
    275972 27 277495 29
    277504 34 277468 22
    277445 42 275977 22
    277435 35 277427 26
    277491 23 277471 29
    277501 13 277475 20
    275961 21 277477 29
    277474 25 277499 12
    277464 30 277428 49
    277484 41 276049 15
    277457 28 267667 31
    277488 42 277478 33
    277440 40 277450
    277480 21 276042 32
    277426 18 282106 37
    277466 42 277453 14
    277494 32 277503 26
    277430 35 272013 40
    277437 30 277425 23
    277449 30 277452 26
    277506 25 277429 42
    277443 36 277473 14
    274682 25 277486 33
    277431 33 275929 23
    277500 33 277497 27
    277502 277424 34
    277439 36 277469 27
    277462 21 277448 37
    275906 39 248823
    277438 47 277442 32
    277422 40 277465 16
    282214 32 276222 21
    276051 14 277476 27
    277461 23 277479 42
    277441 32 277487 36
    277454 39 277482 23
    277481 40 277432 21
    277423 27 277472 21
    277460 26 272991 14
    277496 11 282898 30
    277436 26 277433 29
    277505 26

    Wyniki grupa JŚ

    Nr indeksu Kol1 Kol2 Pkt kol łączne przel.
    276054 5 10 23
    275972 8 7 23
    277504 2 8 15
    277491 3 5 12
    277501 7 5 18
    275961 3 6 14
    277488 9 10 29
    277440 10 10 30
    277480 7 9 24
    277500 3 8 17
    277502 0
    277439 9 9 27
    276051 1 9 15
    277496 4 1 8
    277436 9 9 27
    277434 8 10 27
    277489 7 7 21
    277495 8 7 23
    277468 6 5 17
    277475 0 9 14
    277450 0 0 0
    277453 1 7 12
    277452 8 9 26
    277497 5 8 20
    277476 6 2 12
    272991 7 4 17
    282898 5 8 20