Matematyka dyskretna ściąga na egzamin

Zasada indukcji


(M⊂ℕ∧1∈M∧∀x(xM)⇒(x+1)∈M) ⇒ M=ℕ

Zasada minimum

Każdy podzbiór zbioru ma element najmniejszy.

Zasada maksimum

Każdy ograniczony z góry podzbiór zbioru ma element największy.

Zasada Archimedesa

Dla dowolnej liczby rzeczywistej x∈ℝ, dowolnej liczby rzeczywistej x∈ℝ takiej że 0 > y istnieje liczba naturalna k∈ℕ, taka że x < ky. W szczególności jeśli y = 1, to mamy, że dla każdej liczby rzeczywistej x istnieje taka liczba naturalna k, taka że x < k.

Relacja w zbiorze X

Nazywamy nią dowolny podzbiór iloczynu kartezjańskiego X × X

Relacja równoważności

Mówimy że relacja r jest relacją równoważności, gdy jest ona jednocześnie:

Działania na pierścieniach p

Dla dowolnego p∈ℕ i dla a, b ∈ ℤp definiujemy

Równanie modulo p

Funkcja sufitu i sufitu

Dla dowolnej liczby rzeczywistej x zbiór {nZnx} jest ograniczeniem z góry, zatem zgodnie z zasadą maksimum ma element największy, który nazywamy częścią całkowitą i oznaczamy symbolem x. Zwana jest też funkcją podłogi.


x⌋ ≤ x < ⌊x⌋ + 1

Dla dowolnej liczby rzeczywistej x zbiór {mZxm} jest ograniczeniem z dołu, zatem zgodnie z zasadą minimum ma element najmniejszy. Oznaczamy go symbolem x


x⌉ − 1 < x ≤ ⌈x

Własności:

Notacje

Załóżmy, że (an) i (bn) są ciągami liczb rzeczywistych. Mówimy, że an = O(bn), gdy istnieje liczba c ∈ R i liczba n0 ∈ N takie, że nierówność |an| < c|bn| zachodzi dla każdego n > n0.

Z definicji wynika, że jeśli bn ≠ 0 dla każdego n i an = O(bn) to $\left| \frac{a_{n}}{b_{n}} \right| < c$.

Załóżmy, że (an) i (bn) są ciągami liczb rzeczywistych. Mówimy, że an = o(bn), gdy $\operatorname{}\frac{a_{n}}{b_{n}} = 0$. Jeżeli an = o(bn), to także jest an = O(bn).

Własności notacji O:

Niech f, g, h, z będą funkcjami asymptotycznie dodatnimi. Wówczas:

  1. Dla dowolnej c > 0 jeśli f(n) = O(g(n)) to c ⋅ f(n) = O(g(n)).

  2. Jeśli f(n) = O(g(n)) ∧ g(n) = O(h(n)) to f(n) = O(h(n))

  3. Jeśli f(n) = O(g(n)) ∧ h(n) = O(z(n)) to f(n) ⋅ h(n) = O(g(n)⋅z(n)) oraz f(n) + h(n) = O(g(n)+z(n)), a także f(n) + h(n) = O(max{g(n),z(n)})

Piszemy f(n) = Θ(g(n)) gdy istnieją c1, c2 > 0 oraz n0 ∈ N takie, że dla dowolnego n > n0 mamy c1g(n) ≤ f(n) ≤ c2g(n). Własności notacji O przenoszą się na notację Θ.

Piszemy f(n) = Ω(g(n)), gdy istnieją c > 0, n0 ∈ N takie że dla dowolnego n > n0 mamy f(n) ≥ c ⋅ g(n).

Twierdzenie o rekurencji uniwersalnej

Zakładamy, że a ≥ 1, b > 1 są stałymi, a f(n) jest funkcją zmiennej n ∈ N. Załóżmy, że funkcja T(n) jest zdefiniowana dla n przez następującą rekurencję: $T\left( n \right) = aT\left( \frac{n}{b} \right) + f\left( n \right)$, gdzie $\frac{n}{b}$ dane jest przez $\left\lfloor \frac{n}{b} \right\rfloor$ lub $\left\lceil \frac{n}{b} \right\rceil$, wtedy:

Zasada szufladkowa Dirichleta

Nie można umieścić 5 królików w 4 klatkach, tak aby w każdej był co najwyżej jeden królik.

Jeżeli X jest zbiorem x elementowym, a Y jest zbiorem y elementowym i x > y to nie istnieje funkcja różnowartościowa f : X → Y.

Ogólna zasada Dirichleta:

Dla dowolnych liczb naturalnych s, r, t takich, że s > r ⋅ t i dowolnej funkcji f : S → T, gdzie liczba elementów S jest równa s, a liczba elementów T jest równa t, istnieje takie b ∈ T, że zbiór f−1(b) ma więcej niż r elementów.

Definicja i własności funkcji tworzącej

Załóżmy, że a1, a2, a3, … jest ciągiem liczbowym. Funkcję $F\left( z \right) = \sum_{n = 0}^{\infty}{a_{n}z^{n}}$ nazywamy funkcją tworzącą ciągu an, gdzie z ∈ (−R,R), gdzie R jest promieniem zbieżności.

Jeśli (an) i (bn), n = 0, 1, 2, … są dwoma ciągami liczb a funkcje A$\left( z \right) = \sum_{n = 0}^{\infty}{a_{n}z^{n}}$ i $B\left( z \right) = \sum_{n = 0}^{\infty}{b_{n}z^{n}}$ odpowiednio ich funkcjami tworzącymi to następujące operacje na ciągach generują następujące funkcje tworzące:

Operatory Δ i E

Załóżmy że yn jest ciągiem, czyli y1, y2, y3, … . Różnicą ciągu nazywamy ciąg y2 − y1, y3 − y2, … i oznaczamy go Δ(yn).

Operator E: Ep(x) = y(x+p), gdzie dodatkowo E0(x) = y(x) = I (operator identyczności).


Δ = E − I


E = Δ + I

Twierdzenie Montmorta o sumowaniu nieskończonym:

Niech Ean = an + 1 i Δan = an + 1 − an. Wówczas $a_{0} + a_{1}x + a_{2}x^{2} + \ldots + a_{r}x^{r} + \ldots = \frac{a_{0}}{1 - x} + \frac{x\Delta a_{0}}{\left( 1 - x \right)^{2}} + \frac{x\Delta^{2}a_{0}}{\left( 1 - x \right)^{3}} + \ldots$

Podać wzór na liczbę elementów zbioru A + B+ … znając liczbę ich przesunięć (podany wzór)

Kombinatoryka

Wariacją bez powtórzeń k wyrazową zbioru n elementowego nazywamy każdy k wyrazowy ciąg różnych elementów tego zbioru i wyliczmy ją ze wzoru $\frac{n!}{\left( n - k \right)!}$.

Wariacją z powtórzeniami k wyrazową zbioru n elementowego nazywamy każdy k wyrazowy ciąg elementów tego zbioru i wyliczmy ją ze wzoru nk.

Permutacją zbioru n elementowego nazywamy każdą n wyrazową wariację bez powtórzeń tego zbioru. Wyliczamy ze wzoru n!

Kombinacją k elementową zbioru A n elementowego nazywamy dowolny k elementowy podzbiór zbioru A. Liczba wszystkich kombinacji jest równa $\begin{pmatrix} n \\ k \\ \end{pmatrix}$.

Kombinacje z powtórzeniami: n przedmiotów można umieścić na k miejscach na $\begin{pmatrix} n + k - 1 \\ k - 1 \\ \end{pmatrix} = \frac{\left( n + k - 1 \right)!}{\left( k - 1 \right)!n!}$ sposobów.

Permutacje z powtórzeniami: Liczba permutacji zbioru n elementowego o podzbiorach A1, …,  Ak takich że liczba elementów zbioru Aj = n i elementy zbioru Aj są dla nas nie rozróżnialne, to liczba permutacji jest równa $\frac{n!}{n_{1}! \cdot \ldots \cdot n_{k}!}$


Wyszukiwarka

Podobne podstrony:
ŚCIĄGA NA EGZAMIN rozród
sciaga na egzamin. z fizy, PWR, Chemia, Fizyka II, Egzamin
etr2 sciaga na egzamin koziola, Mechatronika, 2 Rok
DMK Ściąga na egzamin
sciaga na egzamin
!!!Ściąga na egzamin Starosta!!! 7FES4X73YD5BCFEM3LSA23PTZXHXYHFFEGJGVQI
ściąga na egzamin
ściąga na egzamin z tłuszczów
jakaś ściąga na egzamin, Surowce nieorganiczne
ściąga na egzamin z genetyki, Rolnictwo, Genetyka
sciaga na egzamin gleba
Ściąga na egzamin z zabezpieczeń
ściągi i egzaminy, ściąga na egzamin, 1
sciąga na egzamin2
Ściaga na egzamin 11
16 145221 Sciaga na egzamin z mikro, ekonomia

więcej podobnych podstron