82 algoritmai
5 (100%) 1 vote

82 algoritmai

82.AlgoritmaiAlgoritmai – efektyvios procedūros (EP), aprašančios veiksmų seką ir vienareikšmiškai duodančios tam tikrą rezultatą.

Mokykliniai daugybos “stulpeliu” ir dalybos “kampu” metodai, sudėtingos funkcijos diferencijavimo taisyklės ir t.t. – algoritmai.

Pagrindiniai reikalavimai

1.Algoritmas naudojamas su pradiniais duomenimis ir duoda rezultatus. Be to, algoritmo vykdymo metu pasirodo tarpiniai rezultatai.

Taigi, algoritmas operuoja su objektais -duomenimis – pradiniais, tarpiniais ir galutiniais

Algoritmų teorijoje nenaudojamas žodinis objektų apibrėžimas, vietoje to fiksuojami:

• konkretūs baigtiniai pradinių objektų rinkiniai ,

• baigtinis kitų objektų sudarymo būdų iš elementariųjų objektų rinkinys.

Elementariųjų objektų rinkinys sudaro

baigtinį pradinių simbolių alfabetą.

Tipinis kitų objektų sudarymo būdas – indukcija.

Paprasčiausias indukcinis apibrėžimas – klasikinis identifikatoriaus apibrėžimas, naudotas jau ALGOLe: identifikatorius yra raidė arba identifikatorius, kuriam iš dešinės pridėta raidė arba skaičius.

::=

::= ½

::= 0½1½2½3½4½5 ½6 ½7 ½8 ½9

2.Duomenys talpinami atmintyje.

3.Algoritmas susideda iš elementarių žingsnių arba veiksmų, skirtingų žingsnių aibė baigtinė.

4.Algoritmo žingsnių seka determinuota.

5.Natūralu iš algoritmo reikalauti rezultatyvumo.

Reikia skirti:

• algoritmo aprašą (instrukcijas/programą),

• algoritmo realizacijos mechanizmą (kompiuterį),

• algoritmo vykdymo procesą (veiksmų seką, gaunamą pritaikant algoritmą konkretiems duomenims).

3.Algoritmų modeliai

Algoritmų teorijoje:

• parenkamas baigtinis pradinių objektų rinkinys, tie objektai laikomi elementariais,

• parenkamas baigtinis naujų objektų sudarymo būdų rinkinys.

Algoritminiai modeliai, pretenduojantys į sąvokos “algoritmas” formalizavimą, turi būti universalūs.

Universalumas:

• įrodoma, kad vieną modelį galima pakeisti kitu,

• sukurta invariantiška modelių atžvilgiu sąvokų sistema, įgalinanti aptarti algoritmų savybes nepriklausomai nuo parinktos formalizacijos.

Yra trys pagrindiniai universalių algoritminių modelių tipai:

• rekursyviosios funkcijos – istoriškai pirmoji algoritmo sąvokos formalizacija,

• algoritmo vaizdavimas determinuotu įtaisu, gebančiu atlikti labai primityvias operacijas,

• bet kokių alfabetų žodžių perdirbimas; Posto sistemos, normaliniai Markovo algoritmai.

4.Tiuringo tezė

• Viskas, kas gali būti padaryta su skaičiavimo mašina, gali būti atitinkamai aprašyta

• Bet kuri procedūra, kurią galima tiksliai aprašyti, gali būti suprogramuota skaičiavimo mašinai. Alanas Matisonas Tiuringas

A.M.Turing, 1912.06.23 – 1954.06.08

Turing A.M. On computable numbers, with an application to the entsheidungsproblem. Proc. London Math. Soc., Ser 2, 42, 1936)

Nagrinėtini tokie klausimai:

• kokie procesai gali būti aprašyti?

• ar galima viena kalba aprašyti visus galimus aprašyti procesus?

• ar egzistuoja kokiu nors būdu visiškai apibrėžti procesai, kurių negalima aprašyti?

• ar galima tvirtinti, kad egzistuoja kažkokie procesai, kuriuose yra tam tikras emocinio pobūdžio ryšys ir juos galima tik intuityviai apibūdinti, o negalima aprašyti baigtiniu žodžių kiekiu?

Algoritmo ar efektyvios procedūros sąvoka sutinkama, kai tik turime reikalų su keliomis elgseną reglamentuojančiomis instrukcijomis;

tai įvyksta, kai spręsdami kokį nors uždavinį aptinkame, kad kuri nors procedūra,

jei ją teisingai atliksime,

visada baigsis,

duodama tam tikrą atsakymą.

Jeigu yra duotas instrukcijų rinkinys, kyla tokie klausimai:

– ar mums tiksliai pranešta, ką daryti?

– ar galėsime elgtis pagal instrukcijas?

Algoritmas – efektyvi procedūra – aibė nuosekliai laike atliekamų instrukcijų/taisyklių, tiksliai reglamentuojančių mūsų/kieno nors elgesį.

Interpretuojančio subjekto intelekto lygis:

• per žemas – gali instrukcijų nesuprasti;

• per aukštas ar instrukcijos jam nepriimtinos – gali jas savaip interpretuoti;

Patogu būtų turėti:

• kalbą, kuria aprašoma elgesio taisyklų aibė,

• vieną – vienintelę mašiną, kuri interpretuotų tos kalbos nurodymus ir žingsnis po žingsnio atliktų tiksliai nurodytus procesus.

Pagrindinė tos mašinos idėja – kokybinis mašinos sudėtingumo didinimas pakeičiamas paprastu kiekybiniu atminties didinimu.Tiuringo mašina – tai mašina su baigtiniu būsenų skaičiumi, sujungta su ypatingu įtaisu – juosta, ant kurios ji gali užrašyti, o po to perskaityti simbolių sekas.

Tiuringas aptiko, kad šios mašinos gali atlikti labai sudėtingus skaičiavimus ir iškėlė teiginį, dažnai vadinamą Tiuringo teze:

bet kuris procesas, kurį natūraliai būtų galima pavadinti efektyvia procedūra, gali būti realizuotas Tiuringo mašina.

5.Tiuringo mašinos

Tiuringo mašina – tai baigtinis automatas, sujungtas su išorine atmintimi – juosta, kuri suskirstyta į ląsteles.

Galvutė atlieka tris funkcijas:

• skaito ląstelės turinį,

• įrašo į ląstelę,

• pasislenka prie
gretimos ląstelės.

Baigtinis automatas aprašomas:

– įėjimo simbolių alfabetu (s0, … , sm),

– išėjimo simbolių alfabetu (r0, … ,rn),

– vidinių būsenų aibe (q0, … , qp),

– funkcijomis

Q(t+1) = G(Q(t),S(t)),

R(t+1) = F(Q(t),S(t)).

Tiuringo mašina aprašoma trimis lygtimis:

Q(t+1) = G(Q(t),S(t)),

R(t+1) = F(Q(t),S(t)),

D(t+1) = D(Q(t),S(t)),

o naujoji funkcija D nurodo galvutės judėjimo kryptį .

Baigtinis automatas – aprašomas tokiu penketu:sena skaitomas nauja įrašomas judėjimo

būsena simbolis būsena simbolis kryptis

qi sj G(qi, sj) F(qi, sj) D(qi, sj)

arba

qi sj qij sij dij

Kokią nors Tiuringo mašiną, pavyzdžiui, galima aprašyti taip:q0 0 q0 0 D arba 0 0 0 0 1

q0 1 q1 0 D 0 1 1 0 1

q0 P S 0 – 0 P S 0 –

čia raide S pažymėta sustojimo būsena, raide P – simbolių eilutės pabaiga.

Tiuringo mašinose skaičiavimus galima atlikti nurodžius:

• pradinę mašinos (baigtinio automato) būseną,

• juostoje įrašytą informaciją,

• ląstelę, ties kuria yra skaitanti galvutė.

5.1. TM pavyzdžiai

1.Lygiškumo indikatorius

Duota vienetų ir nulių eilutė, pabaigos simbolis P; vietoje jo reikia įrašyti 1, jei vienetų skaičius nelyginis, arba 0, jei vienetų skaičius lyginis.

qi sj qij sij dij

0 0 0 0 D

0 1 1 0 D

0 P S 0 – lyginis vienetų skaičius

1 0 1 0 D

1 1 0 0 D

1 P S 1 – nelyginis vienetų skaičius

qi sj qij sij dij

0 0 0 0 D

0 1 1 1 D

0 P S 0 – lyginis vienetų skaičius

1 0 1 0 D

1 1 0 1 D

1 P S 1 – nelyginis vienetų skaičius

Išsaugoma pradinė informacija

2.Išraiškų su skliaustais tikrinimas

( ( ( ( ) ( ) ) ( ) ) ) – teisinga išraiška,

( ( ) ) ), ) ) – neteisingos išraiškos.

Tikrinimo procedūra:

– einant iš kairės į dešinę randamas pirmas “)”, einant į

kairę randamas jam porinis “(“ ir abu skliaustai braukiami;

– procesas kartojamas, kol išbraukiamos visos poros.

Jei lieka neišbrauktų neporinių skliaustų – išraiška neteisinga, jei nelieka – teisinga.

5.2.Tiuringo mašinų diagramos

Būsenos atvaizduojamos apskritimais; būsena qi užrašoma po apskritimu. Galvutės judesio kryptis nurodoma apskritimo viduje (pvz., K – kairėn, D – dešinėn).

Rodyklė atvaizduoja penkiukę (qi,sj,qij,sij,dij).Rodyklės pabaigoje užrašomas skaitomas simbolis sj, viduryje – įrašomas simbolis sij (jei sutampa su sj – galima praleisti).

Dažnai pasitaikančios penkiukės (qi,sj,qi,sj,dij) praleidžiamos (nesikeičia nei būsena, nei simbolis).

4. Daugybos įtaisas

Darbo algoritmas

5. Kartoja 3 p., kol randa B

6. Kartoja 1 p., kol randa kairįjį A ir sustoja.

Juosta po daugybos

Užduotis. Suprojektuoti Tiuringo mašiną, apskaičiuojančią skaičiaus n kvadratą.Skaičius atvaizduotas taip:

5.Dvejetainių skaičių sumatorius

Užduotis. Duota Tiuringo mašina:

Mašina pradeda darbą tuščioje juostoje. Koks bus jos darbo rezultatas?

6. Tiuringo mašinos atminties valdymas

Yra žodžių Ui aibė, kiekvienas žodis turi požymį Ni.

Žodžiai ir jų požymiai atvaizduoti dvejetaine forma, išdėstyti juostoje poromis NiUi ir atskirti simboliais X.

Simboliai Y žymi aibės pradžią ir pabaigą.

Visi požymiai vienodo ilgio.


6.1. Paieška

1 – simboliai 1/0, esantys į kairę nuo galvutės iki kairiojo Y, pakeičiami simboliais A/B;

2 – požymio N skiltys iš kairės pusės po vieną keičiamos į A/B:

3,4 – galvutė pereina į dešinę iki pirmo skaitmens 1/0 (tai bus tikrinamojo požymio skiltis), pakeičia į A/B ir patikrina sutapimą:

Į 6 būseną patenkama, jeigu skiltys nesutapo, pereinama dešinėn iki pirmojo X ir grįžtama į 1 būsenąĮ 5 būseną patenkama, jeigu skiltys sutapo ir grįžtama iki kairiojo Y kitos požymio N skilties išrinkimui:

.

Kai 2 būsenoje aptinkamas X, tai reiškia, kad visos N skiltys patikrintos, sutapo ir pirmas skaitmeninis žodis į dešinę nuo A/B yra ieškomasis žodis;

Tiuringo mašinos juosta suradus požymį atrodo taip:

Šiuo metu Jūs matote 30% šio straipsnio.
Matomi 1286 žodžiai iš 4285 žodžių.
Peržiūrėkite iki 100 straipsnių per 24 val. Pasirinkite apmokėjimo būdą:
El. bankininkyste - 1,45 Eur.
Įveskite savo el. paštą (juo išsiųsime atrakinimo kodą) ir spauskite Tęsti.
SMS žinute - 2,90 Eur.
Siųskite sms numeriu 1337 su tekstu INFO MEDIA ir įveskite gautą atrakinimo kodą.
Turite atrakinimo kodą?
Po mokėjimo iškart gausite atrakinimo kodą, kurį įveskite į laukelį žemiau:
Kodas suteikia galimybę atrakinti iki 100 straispnių svetainėje ir galioja 24 val.