Matematyka dyskretna(1), Studia Mechanika i Budowa Maszyn


Matematyka Dyskretna

(ramowy program wykładu)

1.Wstęp:

elementarna algebra zbiorów;elementarne własności funkcji i ciągów:terminologia i notacja,;

relacje;zachowania asymptotyczne:notacje Ω,Ξ, o(-),O(-).

2.Logika (1).

elementarne reguły wnioskowania;reguły rachunku zdań;tautologie;równoważność logiczna zdań;model algebry Boola;wyrazenia i zmienne boolowskie;

3.Indukcja i rekurencja.

indukcja matematyczna i jej zastosowania;wzór dwumienny Newtona;procedury indukcyjne;definicje i procedury rekurencyjne;równania rekurencyjne, liniowe równania rekurencyjne i ich rozwiązywanie;

algorytm Euklidesa i analiza jego złożoności obliczeniowej,liczby Fibonacciego;algorytmy rekurencyjne i indukcyjne;

4.Zagadnienia kombinatoryczne.

elemenarne procedury zliczania;podziały ;algorytmy teoriomnogościowe;zasada szufladkowa Dirichleta;permutacje;kombinacje;wariacje;funkcje generujące;algorytmy kombinatoryczne i ich złożoność obliczeniowa;zastosowania do elementarnej teorii prawdopodobienstwa;

5.Zagadnienia teorii grafów.

relacje;grafy i grafy skierowane;zastosowania rachunku macierzy do analizy grafów;

algorytmy na grafach skierowanych;zagadnienia i algorytmy na grafach:przeszukiwania,sortowania,szukanie drzew rozpinających,szukanie optymalnych ścieżek;optymalne przepływy na grafach

6.Zagadnienia teorioliczbowe.

relacje podzielności, arytmetyka modularna;liniowe równania modularne;chińskie twierdzenie o resztach;rząd elementu:logarytm dyskretny; problem faktoryzacjitwierdzenie Eulera i twierdzenie (małe) Fermata;

protokół kryptograficzny RSA;testy pseudopierwszości;test Rabina-Millera;

7. Logika (2)

kwantyfikatory;elementarny rachunek predykatów;rachunek sekwentów;

zbiory nieskończone;

sieci boolowskie;tablice Karnaugha;

8. Uzupełnienia.

wiecej o relacjach;jezyki formalne;klasyczna teoria złożonosci obliczeniowej;problemy NP.,NP.-zupełne.

Literatura

1.K.A.Ross,CH. R. B. Wright, Matematyka Dyskretna, PWN, np 2000.

2.T.H.Cormen,Ch.E.Leiserson,R.L.Rivest;'Wprowadzenie do algorytmow',WNTWarszawa,1997

3.S.W.Jabloński,'Wstęp do Matematyki Dyskretnej',PWN Warszawa,1991

4.E.M.Reingold,J.Nievergelt,N.Deo;'Algorytmy Kombinatoryczne', PWN Warszawa 1985

5.J.Flachmeyer;'Kominatoryka';PWN Warszawa 1987.



Wyszukiwarka

Podobne podstrony:
KIEROWNIK to osoba w organizacji, Studia, MECHANIKA I BUDOWA MASZYN, Podstawy Logistyki, Podstawy za
fiza sciaga, Studia, MECHANIKA I BUDOWA MASZYN, Fizyka
2. Literatuta Cz.1, Studia, MECHANIKA I BUDOWA MASZYN, Techniki Wytwarzania, INFORMACJE OGÓLNE techn
Ple kolokwium opracowane pytania pop 1, Studia, MECHANIKA I BUDOWA MASZYN, Płyny Eksploatacyjne
Narzędzia, Studia, MECHANIKA I BUDOWA MASZYN, Techniki Wytwarzania, INFORMACJE OGÓLNE technika wytwa
Kolos - pytania, Studia, MECHANIKA I BUDOWA MASZYN, Budowa Pojazdów
Opracowanie Baczewski, Studia, MECHANIKA I BUDOWA MASZYN, Płyny Eksploatacyjne
zaliczenie - ergonomia zal, Studia, Mechanika i budowa maszyn PP, Sem V, ERGO, ergo
opracowanie oleje silnikowe, Studia, MECHANIKA I BUDOWA MASZYN, Płyny Eksploatacyjne
opracowanie pytań odpowiedzi - najnowsze, Studia, MECHANIKA I BUDOWA MASZYN, Tribologia i Tribotechn
1. Podstawy, Studia, MECHANIKA I BUDOWA MASZYN, Techniki Wytwarzania, INFORMACJE OGÓLNE technika wyt
Zagadnienia i przykladowe pytania do cwiczen z Bpm, Studia, MECHANIKA I BUDOWA MASZYN, Budowa Pojaz
3-Merkisz, Studia, MECHANIKA I BUDOWA MASZYN, Diagnostyka Samochodów
Płyny eksploatacyjne. Materiały do zajęć laboratoryjnych, Studia, MECHANIKA I BUDOWA MASZYN, Płyny E
PYTANIA EGZAMIN TEW wszystko, Studia, MECHANIKA I BUDOWA MASZYN, Techniki Wytwarzania
fiza sciaga, Studia, MECHANIKA I BUDOWA MASZYN, Fizyka

więcej podobnych podstron