Algoritmid (0)

Eesti Maaülikool - Matemaatika - Analüütiline geomeetria

1 Hindamata

Lõik failist

1.    Algoritm . Algoritmi omadused. Keerukus . Ajalise keerukuse asümptoodiline hinnang. Erinevad keerukusklassid.
Algoritm on mingi meetod probleemi lahendamiseks, mida saab realiseerida arvutiprogrammi abil. Algoritm peab olema
määratud  nii  täpselt,  et  seda  suudaks  täita  isegi  arvuti.  Täidetavaid   samme   ei  tohi  olla  liiga  palju.  Algoritm  peab
lahendama ülesande õigesti erinevate sisendandmete korral.
Algoritmi 5 olulist omadust:
1.    Lõplikkus. Algoritmi töö peab lõppema peale lõpliku arvu sammude läbimist.
2.     Määratletus . Algoritmi iga samm peab olema rangelt ja ühemõtteliselt määratud iga juhu jaoks.
3.     Sisend . Algoritmil on sisendandmed, mille hulk võib olla null.
4.    Väljund. Algoritmil on vastus(ed), millel on täpselt määratud seos sisendandmetega.
5.    Efektiivsus  (tulemuslikkus).  Algoritm  peab  olema  nii  lihtne,  et  on  lõpliku  ajavahemiku  jooksul   pliiatsi   ja
paberi abil täidetav.
Algoritmi  keerukus  on  hinnang  sellele,  kuidas  algoritmi  poolt  esitatavad  nõudmised  ajale  muutuvad  näiteks  siis,  kui
probleemi  mõõt  kasvab.  Keerukus  mõjutab  jõudlust,  kuid  mitte  vastupidi.  Ajaline  keerukus  –  hinnatakse  programmi
tööaega. Mahuline keerukus – hinnatakse programmi tööks kasutatava mälu mahtu.
Ajalise keerukuse asümptoodiline hinnang (asümptoodiline hinnang efektiivsusele). Funktsiooni kasvukiiruse hinnang,
kui  palju  kasvab  algoritmi   tööaeg   andmemahu  suurenemisel.  Reeglina  antakse  hinnang  halvima  juhu  jaoks  ja  tegelik
tööaeg peaks olema parem. Hinnangud hakkavad kehtima alles andmehulga (N-i) suurte väärtuste korral. Algoritmi tööaja
hindamiseks peab pöörama tähelepanu struktuurile.
Keerukusklassid:
1.    O(1) – konstantne keerukus (andmehulgast ei sõltu tööaeg, programmi lauseid täidetakse üks kord, tavaliselt
lahendamiseks valem).
2.    O(log n) – logaritmiline keerukus (tööaeg kasvab väga aeglaselt andmete kasvuga, lahendamine järkjärgulisel
vähendamisel, tavaliselt logaritmi aluseks 2, kahendotsimine – otsitav piirkond aheneb igal sammul 2x).
3.    O(N) – lineaarne keerukus (elementide töötlemine, andmehulga kasvades 2x kasvab ka tööaeg 2x, lineaarne
otsimine).
4.    O(n*log n) – linearitmiline keerukus (kui õnnestub saavutada O(N2) asemel, siis on hästi. Kiirsorteerimine &

Lae alla, et näha rohkem ▪ ▪ ▪

50 punkti Autor soovib selle materjali allalaadimise eest saada 50 punkti.

~ 8 lehte Lehekülgede arv dokumendis

2015-10-01 Kuupäev, millal dokument üles laeti

26 laadimist Kokku alla laetud

0 arvamust Teiste kasutajate poolt lisatud kommentaarid

EddieKnight Õppematerjali autor

järg algoritm keerukus massiiv graaf alampuu juur loend operaator

Sarnased õppematerjalid

pdf

Algoritmid ja andmestruktuurid eksamiks kordamine

1. Algoritm. Algoritmi keerukus. Ajalise keerukuse asümptootiline hinnang. Erinevad keerukusklassid: kirjeldus, näited. 1.1 Algoritm • Mingi meetod probleemi lahendamiseks, mida saab realiseerida arvutiprogrogrammi abil. • Algoritm on õige, kui kõigi sisendite korral, mis vastavalt algoritmi kirjeldusele on lubatud, lõpetab ta töö ja annab tulemuse, mis rahuldab ülesande tingimusi. Öeldakse, et algoritm lahendab arvutusülesande. • Selline programm, mis annab probleemile õige vastuse piiratud aja jooksul. • Kindlalt piiritletud sisendi korral vastab ta järgmistele kriteeriumitele: o lõpetab töö piiratud aja jooksul; o kasutab piiratud hulka mälu; o annab probleemile õige vastuse. • Parameetrid, mille järgi hinnata algoritmide headust: o vastava mälu hulk; o töötamise kiirus ehk vajatava aja hulk.

Informaatika

docx

Algoritmid ICD0001 - kordamisküsimused

kiirmeetod Radix sort, O(n) O(n) Stabiilne. positsioonimeetod Merge sort, O(n logn) O(n logn) On enamasti ühildusmeetod stabiilne. Paisktabel, hash O(1) O(1) table Heap sort, O(n logn) O(n logn) kuhjameetod 1. Algoritmi omadused. Algoritmide asümptootiline analüüs: relatsioonid "suur- O", "väike-o", teeta, "suur-oomega" ja "väike-oomega"; nende definitsioonid ning põhiomadused. Mida miski täpselt tähendab. Algoritm on täpne (üheselt mõistetav) juhis antud ülesande lahendamiseks. Algoritm koosneb lõplikust arvust sammudest, millest igaüks on täidetav lõpliku aja jooksul lõplikke ressursse kasutades. Algoritmi rakendatakse teatavale lähteandmete komplektile (sisend)

Algoritmid ja andmestruktuurid

pdf

Algoritmid ja andmestruktuurid: puud, kuhjad

1.2 Järjestamise kuhjameetod Järjestikalgoritm Luua tühi kuhi; lisada järjendi kirjed järjekorras sinna. 1 Kahendkuhjad 25 1.2 Järjestamise kuhjameetod Keerukus Kui n tähistab kirjete arvu, siis järjendi pealt kuhja tekitamise keerukus on järjestikalgoritmi puhul halvimal juhul (n log n), keskmisel ja parimal juhul (n); "jaga ja valitse" algoritmi puhul alati (n). 1 Kahendkuhjad 26 1.2 Järjestamise kuhjameetod "Jaga ja valitse" algoritm massiivi puhul · Eeltöö -- kompaktse kahendpuu struktuuri loomine -- on triviaal- ne. Etteantud massiivi võib algusest peale käsitleda nii, nagu ta väl- jendaks kompaktset kahendpuud. Positsioonid massiivis määravad alluva-ülemuse suhted ära.

Matemaatika

pdf

Algoritmid ja andmestruktuurid: transfers

Output of non-deterministic algorithm may be different for different runs with the same input data Mittedetermineeritud algoritmi tulemus samade lähteandmete korral võib erinevatel lahenduskordadel olla erinev. Tõene Partial algorithm terminates for any set of input data. Osaline algoritm peatub mistahes sisendandmete korral. Väär Average time complexity of binary search is O(log n). Kahendotsimise keskmine ajaline keerukus on O(log n). Tõene Worst case time complexity of merge sort is O(n). Ühildusmeetodi (merge sort) halvima juhu ajaline keerukus on O(n). Väär (it is O(n log n)) Sorting method is quick if it has average time complexity O(n lon n). Järjestamismeetod on kiire, kui selle keskmine ajaline keerukus on O(n log n). Tõene Jah, üldjuhul ei saa kiiremini

Algoritmid ja andmestruktuurid

doc

Teoreetilibe informaatika kordamisküsimused

Regulaarsed avaldised on võrdsed, kui tähistavad üht ja sama hulka. Regulaarsed hulgad tühihulk, {e} ja {a} on paremlineaarsed keeled. Kui keeled L1, L2 on paremlineaarsed, on paremlineaarsed ka nende ühend, vahe ja täiend. Tõestuseks koostan vastavad grammatikad .. ehk siis näitan kaudset tuletatavust. Järeldus: Regulaarne hulk on genereeritav paremlineaarse grammatikaga 10. Lõplikud automaadid. Mittedeterministlike automaatide teisendamine deterministlikeks. Automaat on algoritm, mis lahendab sõna keeles aktsepteerimise või mitteaktsepteerimise ülesannet. Lõplik automaat on viisik: M = (,Q,delta,Q0,F) sisendtähestik Q olekusümbolite lõplik tähestik delta üleminekuf.-n (Q P(Q) .. lähtuvalt produktsioonidest) Q0 lähteolekud (alamhulgaks olekutele) F lõppolekud (alamhulgaks olekutele) Mittedeterministlick |delta(a,q)| <> 1 Deterministlick |delta(a,q)| = 1

Teoreetiline informaatika

docx

Graafid ja matemaatiline loogika eksamimaterjal

.., 1n), (21, ..., 2n), ..., (m1, ..., mn) ja väär kõigil ülejäänud väärtustustel o TDNK-le viimine: Koostame valemi põhjal tõeväärtustabeli Vaatame vaid neid ridu, mil valem on tõene Koostame konjuktsioonid ridadele vastavatest elementide tõeväärtustest (nt kui X=t, Y=t ja Z=v, siis saame X&Y&¬Z) Ühendame saadud konjuktsioonid ühiseks disjunktsiooniks o TDNK-le viimise algoritm: Elimineerida implikatsioonid ja ekvivalentsid Viia eitused vahetult lausemuutujate ette (st konjunktsioonide ja disjunktsioonide sisse) Korrutada disjunktsioonid läbi (distributiivsuse seaduse abil) Kaotada samaselt väärad konjunktsioonid ja sama liikme mitmekordsed esinemised konjunktsioonides Lisada konjunktsioonidele puuduvad muutujad

Algebra I

docx

Diskreetse matemaatika elemendid

1 , F 2 , . . . , F n on tõesed, on ka F 1 & F 2 & . . . & F n tõene, mistõttu valem G on samuti tõene. Teoreemid järeldumise ja samaväärsuse taandamisest ühe valemi omaduse kontrollimisele o Samaväärus F ↔ G o Järeldumine F → G 7 6. Literaal, täielik elementaarkonjunktsioon, täielik disjunktiivne normaalkuju, nende tõesuspiirkondade kirjeldused. TDNK olemasolu ja ühesus. TDNK-le teisendamise algoritm, tema etappidel kasutatavad samaväärsused. [1] Literaal o DEF: Literaaliks nimetatakse lausemuutujat või selle eitust, literaale loetakse positiivseks või negatiivseks vastavalt selelle, kas ta on puhas lausemuutuja või koos eitusega. N: A, B, ¬C Täielik elementaalkonjuktsioon o DEF: Muutujate X1, X2…, Xn täielikuks elementaarkonjunktsiooniks nimetatakse literaalide konjunktsiooni L1&L2&,..., &Ln Täielik disjunktiivne normaalkuju

Diskreetne matemaatika

docx

ITT0030 Diskreetne matemaatika II - eksamikonspekt

Statistiline tõenäosus. Bernoulli suurte arvude seadus. [20]. Sõltuvad ja sõltumatud sündmused. Sündmuste summa ja korrutis. [21]. Täistõenäosuse valem. Bayesi reegel. [22]. Bernoulli valem (k katse õnnestumine katsete üldarvu n korral). [23]. Kord- ja algarvud. Algarvude jaotus, algarvulisuse kontroll, Eratosthenese sõel. [24]. Naturaalarvude kanooniline kuju. Suurim ühistegur ja vähim ühiskordne. [25]. Fermat teoreem. Pseudoalgarvud ja Carmichaeli arvud. [26]. Eukleidese algoritm. [27]. Lineaarsed diofantilised võrrandid. [28]. Täisarvude kongruentsid. Kongruentsi omadusi. [29]. Moodularitmeetika. [30]. Algarvulisuse Fermat` test. Miller-Rabini test. [31]. Graafid ja graafide omadused. Ahelad ja tsüklid graafis. [32]. Euleri graafid. Hamiltoni tsüklid. [33]. Puud. Puude omadused. [34]. Graafi vähima kaaluga aluspuud. [35]. Märgendatud puud. Puude esitamine arvuti mälus. [36]. Prüferi kood. Märgendatud puude loendamine. Cayley teoreem. [37]

Diskreetne matemaatika ii

Rohkem sarnaseid