Matematyka dyskretna 2014 - teoria

Matematyka dyskretna 2014 - teoria, Ujk Informatyka 2014, Matematyka Dyskretna

[ Pobierz całość w formacie PDF ]
//-->Matematyka dyskretnaTematy na część teoretyczną egzaminuRekurencjaCiąg rekurencyjnyCiągiem rekurencyjnym nazywamy ciąg podany przepisem:an+1= F(an, an-1,…, an-k+1; n)gdzie funkcja F zależy od wyrazówan,…, an-k+1oraz w szczególności może zależeć odn.Liczbęknazywamy rzędem rekurencji. Ponadto, aby określić rekurencję zadajemy k pewnychwyrazów ciągu.Problem wież HanoiZadanie polega na tym, aby krążki początkowo nałożone na pręt 1 w kolejności odnajwiększego na spodzie do najmniejszego na górze przenieść na inny pręt. W danym ruchumożemy przenosić z pręta na pręt tylko po jednym krążku, ponadto nie wolno położyćwiększego krążka na mniejszym.Najmniejsza liczba ruchów potrzebna do rozwiązania problemu jest dana wzorem:h1=1;1. hn+1= 2hn+1 dla n ≥ 1Rozwiązaniem podanej wyżej rekurencji(1) jest:2. hn= 2n– 1PIOTR ŁASKAWSKI1Znając podany wyżej wzór(2) możemy natychmiast otrzymać liczbę kroków potrzebną narozwiązanie problemu dla dowolnegon.Ciąg FibonacciegoZdefiniowany jest w następujący sposób, że dwa pierwsze wyrazy są równe jedności,a każdy następny jest sumą dwóch poprzednich:F1= 1, F2= 1,Fn= Fn-1+ Fn-2, n > 2Kilka początkowych wyrazów ciągu:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,...Złoty podziałZłoty podział, podział harmoniczny, złota proporcja, boska proporcja –podział odcinka na dwie części tak, by stosunek długości dłuższej z nich do krótszej był takisam, jak całego odcinka do części dłuższej.Złoty Podział występuje w przyrodzie, sztuce i architekturze, gdzie uznawany jest zaidealną proporcję:���� =1 + √5~1.618032���� + ��������= = ������������Problem ruina graczaZagadnienie jest następujące: hazardzista rozpoczyna grę w kasynie posiadającpewną liczbęijednakowych monet. Powiedzmy, że gra w oczko. Gra ma takie reguły, że wkolejnych rozdaniach z prawdopodobieństwempgracz wygrywa – wtedy stand jegoposiadania wzrasta o jedną monetę, lub z prawdopodobieństwemqprzegrywa – wówczastraci jedną monetę. Oczywiściep + q = 1,bo musi wygrać albo przegrać. Rozdania sąpowtarzane „do skutku”. Jeśli hazardzista traci wszystko, to bankrutuje. Jeśli natomiast jegostan posiadania wzrośnie do n monet, to rozbija bank.PIOTR ŁASKAWSKI2Sytuację przedstawia poniższy rysunek:Mamy tu do czynienia z tzw.skończonym automatem probabilistycznym. Skończonyodnosi się do skończonej liczby stanów,probabilistycznyoznacza, że odbywają się losowaniadotyczące przejść ze stanu do stanu. Gracz rozpoczyna ze stanu początkowegoi,odbywa sięlosowanie(rozdanie) i gracz z prawdopodobieństwempprzesuwa się do stanui+1lub zprawdopodobieństwemqdo stanui-1,itd. Automat ma dwastany akceptujące,0 i n. Stan 0oznacza „spłukanie”, a stan n rozbicie banku – w obu przypadkach gra się kończy. Procescałej gry polega na przypadkowym błądzeniu po diagramie aż do znalezienia się w którymś zdwóch stanów akceptujących.KombinatorykaPermutacje. Permutacje z powtórzeniami.Permutacją bez powtórzeń zbioru złożonego z n różnych elementów nazywamy każdy nwyrazowy ciąg utworzony ze wszystkich wyrazów zbioru. Wszystkich możliwych permutacji zbioru n-elementowego jest:��������= ����!Permutacjąelementową z powtórzeniami, w której elementyrazy,, jest każdypowtarzają się podaną liczbę razy����!����1! ∗ ����2! ∗ … ∗ ��������!powtarzają się-wyrazowy ciąg, wodpowiednioktórym elementyPIOTR ŁASKAWSKI3Wariacje. Wariacje z powtórzeniamiWariacją bez powtórzeńk-wyrazowązbiorun-elementowegoA (1 ≤k≤n)nazywa siękażdyk-wyrazowyciągkróżnych elementów tego zbioru (kolejność tych elementów ma znaczenie).Gdyk=n,wariację bez powtórzeń nazywa się permutacją.Liczba wszystkichk-wyrazowychwariacji bez powtórzeń zbiorun-elementowegowyraża się wzorem:��������=��������!(���� − ����)!Wariacją z powtórzeniamik-wyrazowązbiorun-elementowegonazywa sięk-wyrazowy ciąg elementów tego zbioru (dowolny element może wystąpić wielokrotnie w ciągu).Należy zauważyć, iż kolejność elementów ma znaczenie.Liczba wszystkichk-wyrazowychwariacji z możliwymi powtórzeniami zbiorun-elementowegojestrówna��������= ������������Kombinacje. Symbol Newtona. Trójkąt Pascala.KombinacjeKombinacjąk-elementowązbiorun-elementowegoAnazywa się każdyk-elementowypodzbiór zbioruA(0 ≤k≤n). Używa się też terminu "kombinacja znelementów pokelementów"lub wręcz "kombinacja znpok".��������������������!=( )=��������! (���� − ����)!Symbol NewtonaSymbol Newtona(nazywany też współczynnikiem dwumianowym, czytanyn nad k,npo klubk z n)jest to funkcja dwóch argumentów całkowitych nieujemnych zdefiniowana, jako:gdzie wykrzyknik oznacza silnię.PIOTR ŁASKAWSKI4Trójkąt PascalaLiczby Stirlinga I i II rodzaju.Liczby Stirlinga - dwa szczególne ciągi liczbowe analizowane przez Jamesa Stirlinga.Liczby Stirlinga I rodzajuOpisują liczbę sposobów na rozmieszczenie n liczb w k cyklach, oznaczane są symbolem:Który czyta się "k cykli n". Spełniają one związek rekurencyjny postaci:przy założeniachLiczby Stirlinga II rodzajuOpisują liczbę sposobów podziału zbioru n elementowego na k niepustych podzbiorów,oznaczane są symbolem:który czyta się "k podzbiorów n"PIOTR ŁASKAWSKI5 [ Pobierz całość w formacie PDF ]

zanotowane.pl

doc.pisz.pl

pdf.pisz.pl

mement.xlx.pl