Algoritmai. Algoritmų sudėtingumas

Darbo tema
&as_epq=algoritmų sudėtingumas&as_oq=&as_eq=&as_nlo=&as_nhi=&lr=&cr=&as_qdr=all&as_sitesearch=&as_oc. Skaičiavimo sudėtingumas.

Aprašymas
Algoritmo sąvoka. Algoritmų sudėtingumo analizės pradmenys. Rūšiavimo algoritmų sudėtingumas. Kaip išmatuoti uždavinio vykdymo laiką? O-žymėjimas. Polinomiškai ir eksponentiškai augančios funkcijos. Grafų algoritmų sudėtingumo tyrimas. Algoritmų sudėtingumo klasės, p, np, "np-complete". Teorema. Np-pilnosios klasės uždavinių pavyzdžiai.

Ištrauka
A. Algoritmu vadinama gerai apibrėžta skaičiavimo procedūra, kuri paima tam tikrą reikšmę įėjime (įėjimo duomenis) ir grąžina tos įėjimo reikšmės pilnai apibrėžtą reikšmę išėjime.
Sąvoka algoritmas matematikoje dažnai priimama kaip pirminė, neapibrėžiama paprastesnėmis sąvokomis. Mes apibrėžėme, bet savo apibrėžime naudojome sąvoką skaičiavimo procedūra . Jei naudojame šią sąvoką apibrėždami algoritmą , tai tada pati skaičiavimo procedūros sąvoka lieka kaip pirminė. Žodžiu, bent vienos naujos pirminės sąvokos šitoje vietoje reikia.
Sąvoka skaičiavimo procedūra čia buvo pavartota plačiąja prasme. Turime galvoje ne vien veiksmus su skaičiais. Skaičiavimo procedūrą gal labiau tiktų aiškinti, kaip tam tikra veiksmu su simboliais seką. Įėjimo duomenys ir rezultatai skaičiavimo procedūrai gali būti bet kokie konstruktyvieji objektai (tokie objektai, kurie pasirinkti pirminiais arba kuriuos galima sukonstruoti gerai apibrėžtoje procedūroje), pvz. , alfabeto simboliai, šių simbolių kombinacijos (pvz. Eilutės), matricos, grafai.
Sąvoka konstruktyvusis objektas atstovauja tam tikrą požiūrį į matematiką - konstruktyviąją matematiką. Konstruktyviojoje matematikoje objekto egzistavimas siejamas su galimybe tą objektą sukonstruoti. Konstruktyviausiojo objekto ir konstruktyviausiojo proceso sąvokos algoritmų teorijai patogiame požiūryje į matematiką yrkonstruktyvaus proceso esmė - gerai apibrėžtų veiksmų su nedalomais objektais vykdymas. Konstravimo procese iš pirminių objektų gaunami objektai ir vadinami konstruktyviaisiais.
Pvz. Teksto konstravime dalyvauja elementarūs objektai - simboliai ir elementarūs veiksmai: įrašyti simbolį , ištrinti simbolį , perskaityti simbolį , palyginti du simbolius .
Algoritmas konstruktyviojoje matematikoje užima tokią vietą, kaip kad funkcija tradicinėje matematikoje.
žodis algoritmas yra kilęs iš a. Matematiko al-chorezmo pavardės (skaitant tą pavardę lotyniškai). Algoritmu viduramžių europoje buvo vadinama dešimtainė pozicinė skaičiavimo sistema, o toks vardas prigijo dėl to, kad ta sistema į europą atėjo su al-chorezmo darbais.
Algoritminis procesas - toks procesas, kuriame palaipsniui (diskrečiaisiais žingsnialgoritmui duodamas įėjimo duomenų rinkinys, algoritmas dirba su juo, ir jis gali po tam tikro žingsnių skaičiaus sustoti, arba niekada nesustoti.

Kategorija Matematika Matematikos konspektai

Tipas Konspektai

Įkeltas 2011 m.

Reitingas