Pytania i zagadnienia (semestr 2)
Omówić prawo mnożenia i rozwiązać przykład : ile jest ciągów binarnych n – elementowych.
Omówić prawo dodawania i rozwiązać przykład : Ile liczb dwucyfrowych ma parzysty iloczyn cyfr a ile nieparzysty.
Ogólne prawo mnożenia, i rozwiązać przykład : ile jest ciągów 3 literowych bez powtórzeń utworzonych ze zbioru {a,b,c,d,e,f} zawierających literę e .
Zasada bijekcji, podać przykład wykorzystania.
Ogólna zasada bijekcji, podać przykład wykorzystania.
Schematy wyboru (losowanie k elementów z n elementowego zbioru) gdy istotna jest kolejność wylosowanych elementów i mogą się one powtarzać.
Schematy wyboru (losowanie k elementów z n elementowego zbioru) gdy istotna jest kolejność wylosowanych elementów i nie mogą się one powtarzać.
Schematy wyboru (losowanie k elementów z n elementowego zbioru) gdy nie istotna jest kolejność wylosowanych elementów i nie mogą się one powtarzać.
Schematy wyboru (losowanie k elementów z n elementowego zbioru) gdy nie istotna jest kolejność wylosowanych elementów i mogą się one powtarzać.
Współczynniki dwumianowe, podstawowe właściwości.
Tożsamości kombinatoryczne.
Podziały zbiorów. współczynniki wielomianowe.
Zasada szufladkowa Dirichleta.
Zależności rekurencyjne, równanie charakterystyczne, podstawowe przykłady.
Zależność dla rekurencji na głębokość 2.
Funkcje tworzące i wykładnicze funkcje tworzące.
Zastosowanie funkcji tworzących do rozwiązywania równań rekurencyjnych.
Operacje na funkcjach tworzących, obliczanie postaci zwartej funkcji tworzących.
Pojęcie metryki w przestrzeni An (A jest alfabetem), odległość Hamminga słów ‘a’.
Detekcja błędów, podać przykład kodu wykrywającego 2 błędy.
Korekcja błędów, podać przykład kodu korygującego 1 błąd.
Omówić kod z wielokrotnym powtarzaniem.
Podać przykład 4 słów binarnych o odległości Hamminga 4.
Podać przykład macierzy Hadamara.
Omówić produkt mnożenia (w sensie Kroneckera) macierzy Hadamara.
Omówić podstawowe własności kodu liniowego.
Omówić podstawowe pojęcia teorii grafów( graf, podgraf, trasy, ścieżki, drogi, cykle)
Omówić grafy planarne, spójne, eulerowskie, hamiltonowskie
Omówić spójność grafów, zbiór rozspajający, rozcięcie grafu, mosty, zbiór rozdzielający.
Reprezentacja macierzowa grafów nieskierowanych.
Reprezentacja macierzowa grafów skierowanych.
Grafy skierowane z wagami, macierz wag minimalnych grafu, algorytm Warshalla.
Asymptotyka funkcji liczbowych, hierarchia.
Notacja O, przekształcenia typu O.
Przestrzeń zdarzeń, podstawowe twierdzenia rachunku prawdopodobieństwa, niezależność zdarzeń, prawdopodobieństwo całkowite.
Zmienne losowe dyskretne, rozkład prawdopodobieństwa zmiennej losowej.
Dystrybuanta rozkładu zmiennej losowej dyskretnej.
Wartość oczekiwana, odchylenie standardowe.
Wariancja zmiennej losowej.
Zmienne losowe ciągłe, rozkład prawdopodobieństwa zmiennej losowej.
Próby, rozkład z próby.
Rozkład zmiennych losowych wielowymiarowy, korelacje.