border=0

Struktureelteorem

Nei't de mooglike manieren fan opnimmen algoritmen beskôge wurde, liket de fraach fan 'e technology fan har ûntwikkeling hiel natuerlik te wêzen. Oant midden fan 'e jierren '60 is de teory fan algoritmeûntwikkeling net bestean - it ûntwikkelingsproses waard folslein bepaald troch de erfaring en skill fan' e programmer. Lykwols, doe't de kompleksiteit fan programma groeide, waard it nedich om in metodyk foar har ûntwikkeling te meitsjen, en it ferskynde yn 'e foarm fan strukturearre programmearring. De ideeën fan strukturearre programmearring waarden yn 1965 útdrukt troch E. Dijkstra, mar se waarden net konsolidearre yn in folslein regelsystem. Yn datselde jier formulearren de Italjaanske wiskundige K. Bom en D. Jakopini in teorem op strukturaliteit. Foardat se har essinsje beskôgje, is it needsaaklik om guon konsepten yn te fieren.

Om't it algoritme de opdracht fan ynformaasjeferwurking bepaalt, moat it oan 'e iene kant behannele aksjes, en op' e oare hân, de oarder fan har ferwurking, de kontrôlestream neamd .

De boppeste blokken dy't ferwize nei de databesferwurking binne ferdield yn ienfâldige en bedoeld. De eigenaarheid fan in ienfâldige aksje is dat it in input en in útfier hat, yn tsjinstelling mei de betingste ien, dy't twa outputen hat, ôfhinklik fan oft de kondysje wier is. In ienfâldige aksje betsjuttet net dat it unyk is - it kin guon fanwege aksjes wêze.

It part fan it algoritme organisearre as ienfâldige aksje, d. Mei ien ynfier (útfetting begjint altyd mei deselde aksje) en ien output (dat is, nei it foltôgjen fan in opjûne blok altyd deselde aksje begjint), wurdt in funksjeblok neamd .

Fan dizze definysje folget it benammen dat alle ienfâldige aksje in funksjoneel blok is, wylst de betingsten net binne.

Neffens de bepalingen fan de struktureare programmearring binne der mar trije ferskillende opsjes foar it organisearjen fan de stream fan kontrôle oer de aksjes fan it algoritme. De kontrôlestream kin de neikommende eigenskippen hawwe:

1) elke blok wurdt no ien kear útfierd;

2) elke blok wurdt útfierd.

De kontrôlefliep wêryn't beide fan dizze eigenskippen útfierd wurde hjit linear - yn dat ferskate funksjeblokken wurde sequinteútfierd. De flux yn 'e taal fan flowcharts komt oerien mei de struktuer:

Fansels kinne ferskate blokken ferbûn troch in lineêre kontrôle kinne kombinearre wurde yn ien funksjonele ienheid:

De twadde type fan kontrôle wurdt neamd as ferwiderje - it organisearret de útfier fan ien fan 'e twa funksjonele blokken, ôfhinklik fan de wearde fan' e logyske kondysje dy't kontrolearre wurde. Block diagram fan 'e struktuer:

Yn dit type hold eigendom (1), eigendom (2) net. As de struktuer twa funksjonele blokjes befettet (S 1 en S 2 ), de ôfdieling wurdt folslein neamd ; Unfoldige ferbreding is mooglik - ien fan 'e blokken is lege (normaal S 2 ).

De tredde type fan kontrôle wurdt szyklik neamd - it organisearret meardere repetysjes fan in funksjeblok, sa >

Sûnt breedte-en szyklike kontrole-typen hawwe ien input en in útfier, passe se meastentiids ek de definysje fan in funksjeblok. Op in rekursive manier stelle wy it begryp fan in standert funksjonele blok:

1) alle ienfâldige aksje is in standert funksjonele blok;

2) elk fan 'e beskreaune trije kontrolstrukturen is in standert funksjoneel blok, as alle blokken yn har ynsteld binne standert funksjonele;

3) Der binne gjin oare standertfunksjonele blokjes.

Wy definiearje in oar konsept:

In algoritme wurdt strukturele neamd as it kin fertsjintwurdige wurde troch in standert funksjonele blok.

Mei oare wurden is de struktureel algoritme in kombinaasje fan de trije konstruksjes dy't hjirboppe besprutsen binne (somtiden wurde basearre algoritmyske struktueren neamd). Fansels binne net alle algoritme struktureel. It is lykwols de strukturele algoritme dy't in oantal remarkbere foardielen hawwe yn fergelyk mei net-struktureel:

· Klientens en ienfâld fan 'e algoritme-wittenskip (sûnt it oantal begjinstruktueren wêrmei't it foarme is lyts);

Ferifikaasjele (om ien fan 'e basisstrukturen te hifkjen, is genôch om te kontrolearjen fan' e justigens fan 'e funksjonele blokken dy't opnommen binne);

Modificabiliteit (it bestiet yn 'e ienfâldigheid fan it feroarjen fan de struktuer fan' e algoritme, om't de konstituante blokjes relatyf ûnôfhinklik binne).

Nei't de definysjes yntrodusearre binne, kinne wy ​​it boumoarm fan 'e Bohm - Jakopini formulier formulieren:





Sjoch ek:

Modellen folsleine en ynformeleel

Foarbyld 2.2

Foarbyld 4.15

Algemiene oanpak

Besykje fragen en taken

Gean werom nei Tafel Ynhâld: Teoretyske Stiftingen fan Computer Science

2019 @ bibinar.info