Ktu algorimtų kolio medžiaga


Tiesinis hesavimas. Funkciju augimo asimptotiniai pozymiai. Tiesiniai rusiavimo algoritmai. Ktu + informatika + konspektai.

Informatikos konspektas. Rūšiavimas su įterpimu. Įrodyti algoritmo korektiškumą ir jo sudėtingumą kai duomenys įvedami palankiausiu atveju. Įrodyti algoritmo korektiškumą ir jo sudėtingumą kai duomenys įvedami nepalankiausiu atveju. Algoritmų sudarymo būdai. Kuo jie skiriasi? Kokia idėja rūšiavimo algoritmo suliejimo būdu. Įrodykite rūšiavimo algoritmo suliejimo būdu korektiškumą. Rūšiavimo algoritmo suliejimo būdu sudėtingumo įrodymas. Funkcijų augimo asimptotiniai žymėjimai ir jų apibrėžimai. Rekurentinių sąryšių sprendimo būdai. Suformuluoti pagrindinę teoremą. Dekompozicinių algoritmų sudėtingumo t(n) skaičiavimo formulės struktūra ir sprendimo būdai. Rūšiavimo piramide algoritmo idėja. Kokia duomenų struktūra – „piramidė“? Kaip priklauso piramidės dydis ir aukštis nuorūšiuojamų duomenų kiekio? Rūšiavimo piramide algoritmo idėja. Kaip atliekamas piramidės sutvarkymas (pateikite algoritmą ir sudėtingumą įrodykite). Greito rūšiavimo algoritmo idėja. Kaip atliekama atraminio elemento paieška? Greito rūšiavimo algoritmo idėja. Įrodykite algoritmo sudėtingumą blogiausiu atveju. Optimalūs rūšiavimo algoritmai naudojantys palyginimus. Šių algoritmų įvertinimo blogiausiam atvejui įrodymas. Įrodyti, kadrūšiavimas piramide ir suliejimo būdu yra asimptotiškai optimalūs algoritmai. Tiesiniai rūšiavimo algoritmai. Kodėl jie lenkia asiptotiškai optimalius palyginimo algoritmus. Rūšiavimas skaičiuojant. Jo sudėtingumo įvertinimo įrodymas. Tiesiniai rūšiavimo algoritmai. Kodėl jie lenkia asiptotiškai optimalius palyginimo algoritmus. Rušiavimas skaičiuojant (counting sort). Kišeninis rūšiavimas. Jo sudėtingumo įvertinimo įvertinimas. Heš funkcijos ir kolizijų sprendimas grandinėlių metodu. Koks privalumas prieš heš lentelės su tiesioginiu adresavimu. Suformuluoti uždavinį, pateikti veiksmų algoritmus ir jų sudėtingumo įvertinimus pagrįsti. Paprastas tolygus hešavimas. Suformuluoti teoremas apie paieškos laiko įvertinimą. Įrodyti vieną teoremą. Universalus hešavimas idėja ir pateikti vieną universalaus hešavimo funkcijų klasę. Suformuluoti teoremą apie raktąatitinkančios grandinėlės ilgį. Atviras adresavimas. Suformuluoti uždavinį, pateikti veiksmų algoritmus ir jų sudėtingumo įvertinimus pagrįsti. Kada tikslinganaudoti? Tiesinis, kvadratinis, dvigubas, idealus hešavimai.


Išėjimas: pertvarkymas į< a`1,a`2,... ,a`n>, kad naujos sekos nariai tenkintų sąlygą a`1,≤a`2≤...≤a`n. Algoritmo esmė įterpti

naują elementą į jau surūšiuotą seką (masyvą). Pvz jei reikia rūšiuoti kortas, tai paėmę pirmąją jau turėsime surūšiuotą

aibę. 2-ąją kortą talpinsime arba prieš ankstesniąją arba po jos. Kitoms kortoms ieškosime vietos, o radę kur ji tinka

– įterpsime. Tarkime reikia surūšiuoti masyvą A[1..n], turintį n rūšiuojamų narių. lenght[A] – elem. skaičius masyve.

Ktu algorimtų kolio medžiaga. (2013 m. Kovo 06 d.). http://www.mokslobaze.lt/ktu-algorimtu-kolio-medziaga.html Peržiūrėta 2016 m. Gruodžio 08 d. 08:03