Algoritmi dhe vetitë e tij.
Algoritmi- një udhëzim i kuptueshëm dhe i saktë për interpretuesin për të ekzekutuar sekuencën përfundimtare të komandave që çojnë nga të dhënat fillestare në rezultatin e dëshiruar.
Ekzekutuesi i algoritmit- ky është objekti ose subjekti për të cilin është hartuar algoritmi.
Sistemi i komandës së interpretuesit (SKI) është i gjithë grupi i komandave që interpretuesi mund të ekzekutojë.
Karakteristikat e algoritmit: kuptueshmëria, saktësia, fundshmëria.
Kuptueshmëria: algoritmi përbëhet vetëm nga komandat e përfshira në SKI të interpretuesit.
Saktësia:çdo komandë e algoritmit të kontrollit përcakton veprimin e paqartë të ekzekutuesit.
Përfundimi (ose performanca): ekzekutimi i algoritmit duhet të çojë në një rezultat në një numër të kufizuar hapash.
Mjedisi i interpretuesit: Mjedisi në të cilin interpretuesi funksionon.
Një sekuencë e caktuar veprimesh të interpretuesit vlen gjithmonë për disa të dhënat bazë... Për shembull, për të përgatitur një pjatë sipas një recete, ju nevojiten produktet (të dhënat) përkatëse. Për të zgjidhur një problem matematikor (zgjidhja e një ekuacioni kuadratik), ju nevojiten të dhëna fillestare numerike (koeficientët e ekuacionit).
Të dhënat e plota: një grup të dhënash të nevojshme dhe të mjaftueshme për zgjidhjen e problemit (marrja e rezultatit të dëshiruar).
Metodat e shkrimit të algoritmeve.
Metodat më të zakonshme janë: grafike, verbale dhe në formë programet kompjuterike.
Mënyra grafike supozon përdorimin e simboleve - blloqeve grafike të caktuara.
| Emri i bllokut | Përcaktimi i bllokut | përmbajtja |
| Procesi | Përpunimin e të dhënave | |
| Vendimmarrja | Njësi logjike për të kontrolluar vërtetësinë ose falsitetin e disa kushteve | |
| Transferimi i të dhënave | Hyrja ose dalja e informacionit | |
| Filloni, ndaloni | Fillimi ose përfundimi i programit | |
| Modifikimi | Organizimi i procesit ciklik - kreu i ciklit |
Mbledhja e blloqeve formon të ashtuquajturat grafiku i rrjedhës.
Shënim verbal algoritmet fokusohen kryesisht në interpretuesin njerëzor dhe mundësojnë regjistrime të ndryshme të udhëzimeve, por regjistrimi duhet të jetë mjaft i saktë.
Gjatë shkrimit të algoritmeve në formë programet për kompjuterët përdoren gjuhë programimi - sisteme kodimi me recetë dhe rregulla për përdorimin e tyre. Shkrimi i algoritmeve në formën e programeve karakterizohet nga një shkallë e lartë e formalizimit.
Algoritme për punën me sasitë. Strukturat algoritmike bazë.
Një sasi është një objekt informacioni i veçantë që ka një emër, vlerë dhe lloj.
Ekzekutuesi i algoritmeve për punën me sasitë mund të jetë një person ose një pajisje e veçantë teknike, siç është një kompjuter. Një interpretues i tillë duhet të ketë memorie për ruajtjen e vlerave.
Sasitë janë konstante dhe të ndryshueshme.
Vlera konstante (konstante) nuk e ndryshon vlerën e tij gjatë ekzekutimit të algoritmit. Një konstante mund të shënohet me vlerën e vet (numrat 10, 3.5) ose me një emër simbolik (numër).
E ndryshueshme mund të ndryshojë vlerën gjatë ekzekutimit të algoritmit. Një ndryshore shënohet gjithmonë me një emër simbolik (X, A, R5, etj.).
Lloji i sasisë përcakton grupin e vlerave që një vlerë mund të marrë dhe një grup veprimesh që mund të kryhen në këtë vlerë. Llojet bazë të vlerave: numër i plotë, real, simbolik, logjik.
Shprehje- një rekord që përcakton sekuencën e veprimeve mbi vlerat. Një shprehje mund të përmbajë konstante, variabla, shenja operacioni, funksione. Shembull:
A + B; 2 * X-Y; K + L - mëkat (X)
Një komandë caktimi është një komandë ekzekutuese, si rezultat i së cilës një ndryshore merr një vlerë të re. Formati i komandës:
emri i ndryshores>: = shprehje>
Komanda e caktimit ekzekutohet në rendin e mëposhtëm: fillimisht llogaritet, më pas vlera që rezulton i caktohet një ndryshoreje.
Shembull. Lëreni variablin A të ketë vlerën 6. Çfarë vlere do të marrë ndryshorja A pas ekzekutimit të komandës: A: = 2 * A - 1?
Zgjidhje. Vlerësimi i shprehjes 2 * A - 1 me A = 6 do të japë numrin 11. Pra, vlera e re e ndryshores A do të jetë e barabartë me 11.
Në atë që vijon, do të supozohet se ekzekutuesi i algoritmeve për punën me sasitë është kompjuteri... Çdo algoritëm mund të ndërtohet nga komanda detyrat, hyrje, tërheqje, degëzimi dhe ciklit.
Komanda e hyrjes- një komandë me të cilën vendosen vlerat e variablave përmes pajisjeve hyrëse (për shembull, një tastierë).
Shembull: hyrje A - futja e vlerës së ndryshores A nga tastiera e kompjuterit.
Komanda e daljes: komanda me të cilën shfaqet vlera e një vlere në pajisjen dalëse të kompjuterit (për shembull, në monitor).
Shembull: përfundimi X - vlera e ndryshores X shfaqet në ekran.
Komanda e degës- ndan algoritmin në dy shtigje në varësi të një kushti të caktuar; atëherë ekzekutimi i algoritmit shkon në një vazhdim të përgjithshëm. Degëzimi është i plotë dhe i paplotë. Përshkrimi i degëzimit në bllok diagramet dhe në gjuhën algoritmike:
Këtu, një seri i referohet një ose më shumë komandave vijuese; kv - fundi i degëzimit.
Komanda e ciklit siguron ekzekutimin e përsëritur të një sekuence komandash (trupi i lakut) sipas disa kushteve.
Lak me parakusht- një lak, ekzekutimi i të cilit përsëritet për aq kohë sa kushti i ciklit është i vërtetë:
Lak me parametër- ekzekutimi i përsëritur i trupit të lakut ndërsa parametri numër i plotë kalon nëpër grupin e të gjitha vlerave nga fillestari (In) deri në fundor (Ik):
Shembull. Janë dhënë dy thyesa të thjeshta. Krijo një algoritëm për marrjen e thyesës që është rezultat i pjesëtimit të tyre.
Zgjidhje. Në formë algjebrike, zgjidhja e problemit duket si kjo:
a / b: c / d = a * d / b * c = m / n
Të dhënat fillestare janë katër vlera të plota: a, b, c, d. Rezultati është dy numra të plotë m dhe n.
alg pjesëtimi i thyesave
e paprekur a, b, c, d, m, n
fillimi i hyrjes a, b, c, d
m: = a * d
n: = b * c
dalje "Numëruesi =", m
prodhimi "Emëruesi =", n
koi
Ju lutemi vini re se për të nxjerrë tekst (çdo sekuencë karakteresh), ai duhet të shkruhet në thonjëza në komandë përfundimi.
- Efimova O., Morozov V., Ugrinovich N. Kursi i teknologjisë kompjuterike me bazat e informatikës. Libër mësuesi për klasat e larta. - M .: OOO "Shtëpia Botuese AST"; ABF, 2000
- Libër problemash mbi shkencën kompjuterike. Në 2 vëllime / Ed. I. Semakin, E. Henner. - M .: Laboratori i Njohurive Bazë, 2001
- Ugrinovich N. Informatika dhe teknologjitë e informacionit. Klasa 10-11 - M .: Laboratori i Njohurive Bazë, SHA "Librat shkollorë të Moskës", 2001
Probleme dhe teste me temën "Algoritmet dhe Ekzekutuesit"
- Hartues i Menaxhimit të Performuesit - Algoritmet e klasës 6
Mësime: 4 Detyra: 9 Teste: 1
- 2 Detyrat: 9 Teste: 1
I dashur student!
Njohja e temës "Algoritmet dhe Ekzekutuesit" është e nevojshme para së gjithash për studimin e mëtejshëm të programimit. Gjuha e programimit QBasic u zgjodh si bazë për mësimin e programimit. Ne hoqëm dorë nga ideja për të përfshirë Visual Basic ose ndonjë gjuhë tjetër programimi të orientuar nga objekti në kursin tonë, pasi kjo qasje ende nuk është përdorur gjerësisht në shumicën e shkollave të mesme në Federatën Ruse. Për më tepër, programimi i orientuar nga objekti bazohet në parimet e programimit klasik në Dos.
Kursi ynë është krijuar për një program arsimor të përgjithshëm. Kur përgatiteni për provimet pranuese në teknologjinë e informacionit në universitete, duhet të njiheni me specifikat e studimit të programimit në këtë universitet. Në disa raste, është i nevojshëm një studim i thelluar i një sërë temash, si për shembull "Arrays". Ju duhet t'i kushtoni vëmendje kësaj kur studioni literaturën për programimin, ndoshta duhet të përdorni rekomandimet metodologjike për përgatitjen e provimeve, të cilat aktualisht janë të publikuara në shumicën e institucioneve të arsimit të lartë.
Si përfundim, vërejmë se arritja e "aerobatikës" në programim është e mundur vetëm me praktikë të vazhdueshme dhe zgjidhjen e problemeve specifike të aplikuara.
Fjala "algorithm" vjen nga emri i matematikanit arab të shekullit të 9-të, al-Khwarizmi, i cili formuloi rregullat për kryerjen e veprimeve aritmetike.
Algoritmi- një udhëzim i saktë dhe i kuptueshëm për interpretuesin për të ekzekutuar sekuencën përfundimtare të komandave që çojnë nga të dhënat fillestare në rezultatin fillestar.
Shembuj: rutina e përditshme, procedura e gatimit, udhëzimet, etj.)
Ekzekutuesi i algoritmitËshtë ai që ekzekuton algoritmin (njeri, kafshë, makinë, kompjuter).
Sistemi i komandës së ekzekutuesit- ky është i gjithë grupi i komandave që interpretuesi di të kryejë (kupton). Algoritmi mund të ndërtohet vetëm nga komandat e përfshira në sistemin e komandave të ekzekutuesit.
për shembull, interpretues Roboti mund të ekzekutojë komanda përpara, prapa, majtas, djathtas, pikturë sipër. Ai lëviz rreth një fushe qelize, të kufizuar nga një mur dhe që përmban mure. Roboti nuk mund të kalojë nëpër mur.
Karakteristikat e algoritmit:
1.Efikasiteti (gjymtyrë)- Mundësia e marrjes së rezultatit nga të dhënat fillestare në një numër të kufizuar hapash. (Për shembull, kur kryeni algoritmin e mbledhjes, 2 numra duhet të marrin shumën).
2.Karakteri masiv- aftësia për të aplikuar algoritmin në një numër të madh të dhënash të ndryshme hyrëse. (Për shembull, Ju mund të shtoni çdo 2 numra, duke ditur algoritmin e mbledhjes.)
3.Determinizmi(siguria, saktësia) - çdo ekip duhet të përcaktojë pa mëdyshje veprimin e interpretuesit.
4.Kuptueshmëria- komanda duhet të jetë e shkruar në një gjuhë të kuptueshme nga kompjuteri.
5.Diskretiteti- ndarjen e algoritmit në komanda të veçanta.
Metodat e regjistrimit të algoritmit:
1) Në gjuhën natyrore - regjistrimi në formën e komandave të veçanta në një gjuhë të kuptueshme për një person.
2) Grafik - në gjuhën e diagrameve bllok, duke përdorur forma gjeometrike (ovale, drejtkëndësh, paralelogram, romb).
3) Në një gjuhë algoritmike - një gjuhë për të shkruar algoritme për mësimin e programimit. Ekipet janë regjistruar në Rusisht.
4) Në një gjuhë programimi - një program. Gjuhët e programimit: Basic, Pascal, C, Visual Basic.
B7.Strukturat algoritmike bazë: vijim, degëzim, lak; imazhin në diagramet bllok. Ndarja e detyrave në nën-detyra. Algoritme ndihmëse.
Ndërtime algoritmike. Brenda algoritmeve, mund të dallohen grupe hapash që ndryshojnë në strukturën e tyre të brendshme - ndërtimet algoritmike.
Konstruktet algoritmike bazë janë sekuencë lineare hapash (ose renditje), degëzimi dhe lak.
Thirret një algoritëm në të cilin komandat ekzekutohen në mënyrë sekuenciale njëra pas tjetrës algoritmi linear.
Kështu duket një algoritëm linear në gjuhën e diagrameve bllok:
Shembull: algoritmi për ndezjen e kompjuterit:
- Ndizni fuqinë e kompjuterit (shtypni butonin në mbrojtësin e mbitensionit).
- Ndizni monitorin, printerin.
- Shtypni butonin e energjisë në njësinë e sistemit.
- Prisni derisa sistemi operativ të ngarkohet dhe të shfaqet Desktop.
- Shkoni në punë.
Në këtë algoritëm, të gjitha veprimet duhet të kryhen në mënyrë sekuenciale njëra pas tjetrës: nuk mund të filloni punën nëse rryma ose monitori nuk është i ndezur.
Struktura algoritmike " degëzimi“Është përfshirë gjendje, në varësi të së vërtetës së kushtit, ekzekutohet një ose një sekuencë tjetër komandash (seri).
Një kusht është një deklaratë që mund të jetë e vërtetë ose e rreme. Në kusht, dy numra, dy vargje, dy variabla ose shprehje vargu krahasohen me njëri-tjetrin duke përdorur operacione krahasimi (>,<, =, >=, <=).
Në strukturat algoritmike ciklit përfshin një seri komandash që ekzekutohen disa herë. Kjo sekuencë komandash quhet trupi i ciklit.
Strukturat algoritmike ciklike janë dy llojesh:
- ciklet kundër, në të cilën trupi i lakut ekzekutohet një numër të caktuar herë;
- sythe të kushtëzuara, në të cilin trupi i lakut ekzekutohet për aq kohë sa plotësohet kushti.
Cikli me banak- përdoret kur paraprakisht dihet se sa përsëritje të trupit të ciklit duhet të kryhen.
Koncepti i një algoritmi. Ekzekutuesit e algoritmit. Vetitë e algoritmit
Koncepti i një algoritmi është po aq themelor për shkencën kompjuterike sa koncepti i informacionit. Ka shumë përkufizime të ndryshme të një algoritmi, pasi ky koncept është mjaft i gjerë dhe përdoret në fusha të ndryshme të shkencës, teknologjisë dhe jetës së përditshme.
Algoritmi është një sekuencë e kuptueshme dhe e saktë veprimesh që përshkruan procesin e transformimit të një objekti nga një gjendje fillestare në një gjendje përfundimtare.
Një algoritëm është një përshkrim i saktë i një sekuence veprimesh që synojnë zgjidhjen e një problemi të caktuar, të destinuara për një interpretues specifik.
Interpretues algoritmi mund të jetë ose një person (receta, udhëzime të ndryshme, algoritme për llogaritjet matematikore) ose një pajisje teknike. Makina të ndryshme (kompjutera, robotë industrialë, elektroshtëpiake moderne) janë interpretues formal algoritme. Ekzekutuesit formal nuk i kërkohet të kuptojë thelbin e problemit që zgjidhet, por kërkohet ekzekutimi i saktë i sekuencës së komandave.
Algoritmi mund të shkruhet në mënyra të ndryshme (përshkrim verbal, përshkrim grafik - bllok diagram, program në një nga gjuhët e programimit, etj.). Një program është një algoritëm i shkruar nëgjuhë programimi .
Për të krijuar një algoritëm (program), duhet të dini:
një grup i plotë i të dhënave fillestare të problemit (gjendja fillestare e objektit);
qëllimi i krijimit të algoritmit (gjendja përfundimtare e objektit);
sistemi i komandës së ekzekutuesit (domethënë një grup komandash që ekzekutuesi i kupton dhe mund t'i ekzekutojë).
Algoritmi (programi) që rezulton duhet të ketë grupin e mëposhtëm të vetive:
diskrete (algoritmi është i ndarë në hapa të veçantë - komanda);
paqartësia (çdo komandë përcakton veprimin e vetëm të mundshëm të interpretuesit);
kuptueshmëria (të gjitha komandat e algoritmit përfshihen në sistemin e komandës së ekzekutuesit);
efikasiteti (interpretuesi duhet ta zgjidhë problemin në një numër të caktuar hapash).
Shumica e algoritmeve kanë gjithashtu vetinë karakter masiv (duke përdorur të njëjtin algoritëm, shumë probleme të ngjashme mund të zgjidhen).
Metodat për përshkrimin e algoritmeve
U vu re më lart se i njëjti algoritëm mund të shkruhet në mënyra të ndryshme. Algoritmi mund të shkruhet gjuha natyrore. Si të tillë, ne përdorim receta, udhëzime, etj. Për regjistrimin e algoritmeve të destinuara për interpretues zyrtarë, të veçantë gjuhë programimi... Mund të përshkruhet çdo algoritëm grafikisht në formën e një bllok diagrami... Për këtë, është zhvilluar një sistem i veçantë shënimesh:
|
Emërtimi |
Përshkrim |
Shënime (redakto) |
|
Fillimi dhe mbarimi i algoritmit | ||
|
|
Hyrja dhe dalja e të dhënave. |
Prodhimi i të dhënave nganjëherë referohet ndryshe:
|
|
|
Veprimi |
Në algoritmet llogaritëse, kjo është detyra |
|
|
Pirun |
Fork - një komponent i nevojshëm për të zbatuar degët dhe sythe |
|
|
Fillimi i ciklit me parametër | |
|
|
Procesi tipik |
Në programim, procedura ose nënprograme |
|
|
Kalimet midis blloqeve |
Le të japim një shembull të përshkrimit të një algoritmi për përmbledhjen e dy sasive në formën e një diagrami bllok:
Kjo mënyrë e përshkrimit të algoritmit është më grafika dhe më e kuptueshme për njerëzit. Prandaj, algoritmet e ekzekutuesve formal zakonisht zhvillohen së pari në formën e një diagrami bllok, dhe vetëm atëherë ata krijojnë një program në një ngagjuhë programimi .
Strukturat tipike algoritmike
Programuesi ka aftësinë për të hartuar dhe përdorur struktura algoritmike atipike, megjithatë, kjo nuk është e nevojshme. Çdo algoritëm kompleks arbitrarisht mund të zhvillohet në bazë të tre strukturave tipike: vazhdimësia, degëzimi dhe përsëritja. Në këtë rast, strukturat mund të vendosen në mënyrë sekuenciale njëra pas tjetrës ose të futen në njëra-tjetrën.
Struktura lineare (ndiq)
Struktura më e thjeshtë algoritmike është lineare. Në të, të gjitha veprimet kryhen një herë në rendin në të cilin janë shkruar.
Degëzimi
V degëzimi i plotë ekzistojnë dy mundësi për veprimet e ekzekutuesit, në varësi të vlerës së shprehjes (kushtit) logjik. Nëse kushti është i vërtetë, atëherë do të ekzekutohet vetëm dega e parë, përndryshe do të ekzekutohet vetëm dega e dytë.
Dega e dytë mund të jetë bosh. Kjo strukturë quhet degëzimi ose përshkimi jo i plotë.
Nga disa degë është e mundur të ndërtohet struktura " zgjedhje"(Degëzimi i shumëfishtë), i cili do të zgjedhë jo nga dy, por nga një numër më i madh opsionesh për veprimet e ekzekutuesit, në varësi të disa kushteve. Është thelbësore që vetëm një degë të ekzekutohet - në një strukturë të tillë, rendi i kushteve bëhet i rëndësishëm: nëse plotësohen disa kushte, atëherë vetëm njëra prej tyre do të funksionojë - e para nga lart.
Cikli (përsëritje)
Cikliju lejon të organizoni përsëritje të shumta të së njëjtës sekuencë komandash- quhet trupi i ciklit. Në lloje të ndryshme të algoritmeve looping, numri i përsëritjeve mund të varet nga vlera e një shprehjeje logjike (kushti) ose mund të jetë i koduar në vetë strukturën. Ka cikle: " përpara», « mirupafshim», cikle me një numërues. Në sythe "para" dhe "ndërsa" një shprehje logjike (kusht) mund t'i paraprijë trupit të lakut ( lak parakusht) ose mbyllni ciklin ( lak pas gjendjes).
Ciklet« përpara“- përsëritja e trupit të ciklit derisa të plotësohet kushti:
Ciklet « mirupafshim“- përsëritja e trupit të ciklit ndërsa kushti është plotësuar(e vertete):
Unazat kundër(me parametër)- përsëritja e trupit të lakut një numër të caktuar herë:
Algoritmi ndihmës (nënrutinë, procedurë)
Algoritmi ndihmës është një modul që mund të aksesohet disa herë nga algoritmi kryesor. Përdorimi i algoritmeve ndihmëse mund të zvogëlojë ndjeshëm madhësinë e algoritmit dhe të thjeshtojë zhvillimin e tij.
Metodat për zhvillimin e algoritmeve komplekse
Ekzistojnë dy metoda për zhvillimin e algoritmeve komplekse:
Metoda sekuenciale e detajimit të detyrës("Nga lart-poshtë") është se problemi kompleks origjinal është i ndarë në nën-detyra. Secila nga nënproblemet shqyrtohet dhe zgjidhet veçmas. Nëse ndonjë nga nëndetyrat është e vështirë, ato gjithashtu ndahen në nëndetyra. Procesi vazhdon derisa nëndetyrat të reduktohen në ato elementare. Zgjidhjet e nënproblemeve individuale më pas mblidhen në një algoritëm të vetëm për zgjidhjen e problemit origjinal. Metoda përdoret gjerësisht sepse lejon disa programues të zhvillojnë njëkohësisht një algoritëm të përgjithshëm për zgjidhjen e nëndetyrave lokale. Ky është një parakusht për zhvillimin e shpejtë të produkteve softuerike.
Metoda e montimit("nga poshtë-lart") është krijimi i një grupi modulesh softuerësh që zbatojnë zgjidhjen e detyrave tipike. Kur zgjidh një problem kompleks, programuesi mund të përdorë modulet e zhvilluara si algoritme (procedura) ndihmëse. Ne shume sistemet e programimit Tashmë ekzistojnë grupe të ngjashme modulesh, të cilat thjeshtojnë dhe përshpejtojnë shumë krijimin e një algoritmi kompleks.
Algoritmet dhe proceset e kontrollit
Kontrolli - ndërveprimi i qëllimshëm i objekteve, disa prej të cilave janë kontroll, të tjerët janë të kontrolluar.
Në rastin më të thjeshtë, ekzistojnë dy objekte të tilla:
Nga pikëpamja e shkencës kompjuterike veprimet e kontrollit mund të konsiderohen si informacion kontrolli. Informacioni mund të transmetohet në formën e komandave. Sekuenca e komandave për të kontrolluar objektin, që çon në një qëllim të paracaktuar, quhet algoritmi i kontrollit... Rrjedhimisht, objekti i kontrollit mund të quhet ekzekutuesi i algoritmit të kontrollit. Në shembullin e mësipërm, objekti i kontrollit funksionon "pa parë" se çfarë ndodh me objektin e kontrollit ( kontrolli i qarkut të hapur hapur... Një tjetër skemë kontrolli mund të marrë parasysh informacionin në lidhje me proceset që ndodhin në objektin e kontrollit:
Në këtë rast, algoritmi i kontrollit duhet të jetë mjaft fleksibël për të analizuar këtë informacion dhe për të marrë një vendim për veprimet e tij të mëtejshme në varësi të gjendjes së objektit të kontrollit ( kontrolli i reagimeve). Kjo skemë kontrolli quhet mbyllur.
Më në detaje studiohen proceset e kontrollit. kibernetikë... Kjo shkencë pretendon se proceset më të ndryshme të menaxhimit në shoqëri, natyrë dhe teknologji ndodhin në mënyrë të ngjashme, i binden të njëjtave parime.
Deri në fillim të temës
Ju lutemi pezulloni AdBlock në këtë sajt.
Në këtë mësim do të analizojmë disa nga konceptet teorike që formalizojnë konceptin e programimit. Në të njëjtën kohë, ne do të formulojmë më saktë detyrën kryesore të trajnimit tuaj.
Si fillim ju sugjeroj të luani pak me lodrën e mëposhtme të fëmijëve. Plotësoni pesë detyrat e para, kthehuni prapa dhe vazhdoni të lexoni mësimin.
Fig. 1 Pamja e ekranit të fushës së lojës në kod.org
Shpresoj të keni sukses. Tani, duke përdorur këtë shembull, ne do të përshkruajmë disa koncepte themelore:
- ekzekutues;
- sistemi i komandave të ekzekutuesit;
- algoritmi.
Në lodër ne kontrollojmë një zog të kuq. Detyra e secilës fazë: ta çoni zogun te derri. Zogu mund të kryejë komanda të caktuara, për shembull: lëvizni përpara, kthehuni majtas, kthehuni djathtas, etj.
Një person, makinë ose pajisje që mund të kryejë komanda të caktuara quhet ekzekutues. Në këtë lodër, padyshim, interpretuesi është një zog. Quhet grupi i komandave që interpretuesi kupton dhe di të kryejë sistemi komandues i ekzekutuesit.
Sekuenca e komandave që ekzekutuesi duhet të ekzekutojë për të zgjidhur problemin quhet algoritëm.
Është e nevojshme të përqendroheni në disa pika.
Performuesi mund të ekzekutojë vetëm ato komanda që janë të përfshira në sistemin e tij të komandës.
Kjo do të thotë, për shembull, që ju nuk mund t'i shkruani interpretuesit të zogut: "Shko te derri!" Më saktësisht, mund të shkruani, por asgjë nuk do të ndodhë, tk. ekzekutuesi i komandave të tilla nuk e di.
Ju mund t'i shkruani komandat ekzistuese në çdo mënyrë që mendoni se është e saktë. Detyra juaj si programues është të ndani një detyrë të madhe komplekse në hapa të vegjël të veçantë, secili prej të cilëve do të jetë i qartë për ekzekutuesin. Përça dhe pushto sërish funksionon.
Performuesi bën pikërisht atë që algoritmi e udhëzon të bëjë.
Performuesi i shpendëve është shumë i besueshëm. Nuk vë në dyshim atë që shkruani në program. Nëse, për shembull, harroni të shpalosni zogun, ai do të përplaset në mur. Prandaj, duhet të kujdeseni për gjithçka vetë.
Programet tuaja të ardhshme shpesh nuk do të funksionojnë ashtu siç keni menduar. Gabimet i ndodhin të gjithëve. Është e rëndësishme të kuptoni se ky nuk është një budalla i kompjuterit, por keni bërë një gabim në algoritëm. Mos u bëni si programuesit e këqij që kanë gjithmonë programin për të fajësuar.
Tani, nga një shembull ilustrues, le të kalojmë te realitetet kompjuterike. Ne shkruajmë programe për një kompjuter, që do të thotë se kompjuteri në rastin tonë është një ekzekutues. Sistemi i komandës - funksionet standarde dhe konstruktet e gjuhës C.
Cila është detyra kryesore e mësimdhënies suaj të bazave të programimit? Zotëroni aftësinë e të menduarit algoritmik. Kjo do të thotë, mësoni se si të shkruani zgjidhjen e problemeve të ndryshme në formën e një algoritmi për një interpretues specifik (në rastin tonë, një kompjuter).
Pra, për të përmbledhur:
Program kompjuterik- një algoritëm për zgjidhjen e një problemi, i shkruar në një gjuhë programimi.
Algoritmi - një përshkrim i saktë i rendit të veprimeve që duhet të kryhen nga interpretuesi për të zgjidhur problemin.
Ekzekutues - një person ose një pajisje që mund të kuptojë dhe të ekzekutojë një grup të caktuar komandash.
TEMA 8. BAZAT E ALGORITMIZIMIT DHE PROGRAMIMIT
8.1. Koncepti i algoritmit dhe ekzekutuesi i algoritmeve. Vetitë e algoritmit
"Algoritmi" është një koncept themelor në shkencën kompjuterike. Një kuptim i tij është i nevojshëm për aplikimin efektiv të teknologjisë informatike për zgjidhjen e problemeve praktike. Një algoritëm është një recetë për një ekzekutues (një person ose një automat) për të kryer një sekuencë të përcaktuar saktësisht veprimesh që synojnë arritjen e një qëllimi të caktuar. Një algoritëm është një rregull i formuluar në disa gjuhë që tregon veprime, ekzekutimi vijues i të cilave çon nga të dhënat fillestare në rezultatin e dëshiruar. Kuptimi i fjalës algoritmi shumë e ngjashme me kuptimin e fjalëve recetë, proces, metodë, mënyrë... Sidoqoftë, çdo algoritëm, ndryshe nga një recetë ose metodë, ka domosdoshmërisht vetitë e mëposhtme.
Karakteristikat e algoritmit (duke e dalluar atë nga çdo recetë tjetër): kuptueshmëria(për një interpretues specifik); diskrete(urdhrat janë sekuencialë, me fiksim të saktë të momenteve të fillimit dhe përfundimit të ekzekutimit të komandës); saktësinë(pas ekzekutimit të çdo komande dihet me siguri nëse ekzekutimi i algoritmit ka përfunduar apo cila komandë duhet të ekzekutohet më pas); efikasiteti(pas një numri të caktuar hapash, problemi zgjidhet ose bëhet e qartë se procesi i zgjidhjes nuk mund të vazhdojë): karakter masiv(algoritmi zbatohet në mënyrë uniforme për çdo formulim specifik të problemit për të cilin është zhvilluar).
1. Diskretiteti - ndarja e algoritmit në një numër veprimesh të veçanta të plota - hapa. Ekzekutimi i algoritmit ndahet në një sekuencë veprimesh të përfunduara - hapa. Çdo veprim duhet të plotësohet nga ekzekutuesi i algoritmit përpara se të vazhdojë me ekzekutimin e veprimit tjetër.
2. Saktësia - udhëzime të paqarta. Në çdo hap, transformimi i objekteve të mjedisit të ekzekutuesit të marrë në hapat e mëparshëm të algoritmit përcaktohet në mënyrë unike. Nëse një algoritëm aplikohet në mënyrë të përsëritur në të njëjtin grup të dhënash hyrëse, atëherë ai merr të njëjtin rezultat çdo herë. Regjistrimi i algoritmit duhet të jetë i tillë që në çdo hap të ekzekutimit të tij të dihet se cila komandë duhet të ekzekutohet më pas.
3. Kuptueshmëria - kuptimi dhe ekzekutimi i paqartë i secilit hap të algoritmit nga ekzekutuesi i tij. Algoritmi duhet të shkruhet në një gjuhë të kuptueshme për interpretuesin.
4. Efektiviteti - marrja e detyrueshme e rezultatit në një numër të kufizuar hapash. Çdo hap (dhe algoritmi në tërësi) pas përfundimit të tij jep një mjedis në të cilin të gjitha objektet janë të përcaktuara në mënyrë unike. Nëse kjo është e pamundur për ndonjë arsye, atëherë algoritmi duhet të raportojë se nuk ka zgjidhje për problemin. Algoritmi duhet të plotësohet në një numër të kufizuar hapash. Shkenca kompjuterike funksionon vetëm me objekte të fundme dhe procese të fundme, kështu që çështja e shqyrtimit të algoritmeve të pafundme mbetet jashtë kornizës së teorisë së algoritmeve. 5. Karakteri masiv - aplikimi i algoritmit për zgjidhjen e një klase të tërë problemash të të njëjtit lloj.
Sistemi i komandës së ekzekutuesit është një situatë e përshkruar saktësisht, duke përfshirë formulimin e problemit që do të zgjidhet, një listë të objekteve të përfshira në gjendjen e problemit dhe në zgjidhjen e tij, dhe aftësitë e ekzekutuesit: vetitë e objekteve që ai mund të njohë. dhe veprimet që ai mund të kryejë. Ekzekutimi formal i algoritmit kryhet nga përpiluesi ose interpretuesi, duke kontrolluar semantikën.
8.2. Metodat e regjistrimit të algoritmit
Në praktikë, format e mëposhtme të algoritmeve të shkrimit janë më të zakonshmet:
1) regjistrimi grafik (bllokuskemat);
2) shënimi verbal (pseudokodet);
3) gjuhë programimi.
Forma verbale e algoritmit është një përshkrim në gjuhën natyrore i fazave të njëpasnjëshme të përpunimit të të dhënave. Metoda verbale nuk është e përhapur, pasi përshkrime të tilla nuk janë formalizuar rreptësisht, ato lejojnë paqartësi në interpretimin e recetave individuale. Një algoritëm i shkruar duke përdorur pseudokod është një përshkrim gjysmë i formalizuar në një gjuhë algoritmike të kushtëzuar, duke përfshirë elementët bazë të gjuhës së programimit dhe frazat e gjuhës natyrore, shënimin matematikor të pranuar përgjithësisht dhe të tjera.
Një shënim grafik, i quajtur gjithashtu një diagram algoritmi, është një imazh i një algoritmi në formën e një sekuence blloqesh funksionale të ndërlidhura, secila prej të cilave korrespondon me ekzekutimin e një ose më shumë veprimeve. Shënimi grafik është më kompakt dhe vizual në krahasim me atë verbal. Në skemën e algoritmit, çdo lloj veprimi korrespondon një figurë gjeometrike. Format janë të lidhura me vija tranzicioni që përcaktojnë rendin në të cilin kryhen veprimet.
Forma grafike e regjistrimit, e quajtur edhe një diagram bllok ose një diagram bllok i një algoritmi, është një imazh i një algoritmi në formën e një sekuence blloqesh funksionale të ndërlidhura, secila prej të cilave korrespondon me ekzekutimin e një ose më shumë veprimeve.
Në atë që vijon, ne do të përdorim algoritmi i diagrameve të rrjedhës v. Ato ju lejojnë të paraqisni algoritme në një formë më vizuale, kjo bën të mundur analizimin e punës së tyre, kërkimin e gabimeve në zbatimin e tyre, etj. Grafikët e rrjedhës kanë gjithmonë Filloni dhe fund, të shënuar me elipsa, midis tyre - sekuenca hapat algoritmi i lidhur shigjeta.
Ka hapa pa kushte(përshkruar nga drejtkëndësha, paralelogramë) dhe kushtëzuar(përshkruar nga rombet). Dy shigjeta dalin gjithmonë nga romb - njëra nënkupton rrugën e mëtejshme, nëse plotësohet kushti (zakonisht shënohet me fjalën "po" ose "+"), tjetra - mospërmbushje (fjala "jo" ose "- "). Hyrja nga tastiera ose shfaqja e vlerës së një shprehjeje përshkruhet me një paralelogram. Komanda që kryen përpunimin e veprimeve (komanda e caktimit) shfaqet në një drejtkëndësh.
Nëse zgjidhja e problemit është komplekse dhe mjaft e gjatë, atëherë algoritmi mund të rezultojë të jetë shumë i madh. Kjo mund të shmanget duke zëvendësuar disa sekuencë të plotë hapash të algoritmit me blloqe, të cilat do të jenë algoritme ndihmëse. Blloku zakonisht nuk është elementar, dimensionet e tij zgjidhen në varësi të nevojës, megjithatë, nëse është i përbërë saktë, ai ka të gjitha shenjat e nevojshme të një hapi algoritmik: ka një pikë hyrje (një fillim të përcaktuar qartë) dhe mund të jetë i kushtëzuar. ose pa kushte. Blloqe të ndryshme të algoritmit lidhen me njëri-tjetrin vetëm përmes pikave hyrëse dhe dalëse, kështu që nëse blloku e zgjidh saktë problemin e tij, atëherë struktura e tij e brendshme është e parëndësishme për pjesën tjetër të algoritmit. Një paraqitje e tillë e bllokut është veçanërisht e përshtatshme në fazat e hershme të zgjidhjes së problemeve komplekse, kur detajimi i blloqeve bëhet më vonë dhe, ndoshta, nga zhvillues të tjerë.
Një gjuhë programimi është një gjuhë që përdoret për të shkruar zyrtarisht algoritme. Shumica e gjuhëve të programimit klasifikohen si gjuhë algoritmike. Shkrimi i një algoritmi në një gjuhë algoritmike quhet program.
Gjuha e përdorur për të shkruar zyrtarisht algoritme quhet gjuha algoritmike... Kur përshkruani ndonjë gjuhë (përfshirë natyrore, për shembull, rusisht, anglisht, etj.), Përdoren konceptet e mëposhtme: alfabeti, sintaksa dhe semantike.
Alfabeti gjuha është një grup shenjash më të thjeshta që mund të përdoren në tekstet e kësaj gjuhe. Sekuenca e karaktereve në alfabet quhet fjalë... Rregullat sipas të cilave fjalët formohen nga alfabeti quhen gramatikë. Vetë gjuheështë një grup i të gjitha fjalëve të shkruara në një alfabet të caktuar sipas një gramatike të caktuar.
Sintaksëështë një grup rregullash që përcaktojnë kombinime (ndërtime) të mundshme nga shkronjat e alfabetit. Për të përshkruar sintaksën e një gjuhe, si rregull, përdorni një gjuhë tjetër (metaljuhë) ose diagrame sintaksore.
Semantikaështë një grup rregullash që përcaktojnë kuptimin (kuptimin) e konstrukteve gjuhësore individuale.
Një nga gjuhët më të zakonshme algoritmike është Pascal, e cila është e dobishme si për fillestarët ashtu edhe për programuesit me përvojë. Edukimi i programimit më së shpeshti bazohet në këtë gjuhë.
8.3. Konstruktet algoritmike bazë
Struktura e algoritmit mund të përfaqësohet më qartë duke përdorur një diagram bllok në të cilin përdoren figura (blloqe) gjeometrike, të lidhura me shigjeta që tregojnë sekuencën e veprimeve. Janë miratuar disa standarde për paraqitjet grafike të blloqeve. Për shembull, një komandë për përpunimin e informacionit vendoset në një bllok që duket si një drejtkëndësh, një kontroll i gjendjes vendoset në një romb, një komandë hyrëse ose dalëse vendoset në një paralelogram dhe një ovale tregon fillimin dhe fundin e algoritmit.
Njësia elementare strukturore e algoritmit është një komandë e thjeshtë që përcakton një hap elementar të përpunimit ose shfaqjes së informacionit. Një komandë e thjeshtë në gjuhën skematike përfaqësohet si një bllok funksioni.
 |
Ky bllok ka një hyrje dhe një rrugëdalje... Nga komandat e thjeshta dhe kushtet e kontrollit, formohen komanda të përbëra që kanë një strukturë më komplekse dhe gjithashtu një hyrje dhe një dalje. |
 |
Le të shqyrtojmë strukturat kryesore të algoritmit. |
 |
Ekipi degëzimiështë një komandë e përbërë e algoritmit, në të cilën, në varësi të kushtit P, njëri prej tyre S1, ose tjeter S2 veprim. Algoritmet e degëzimit (algoritmet e degëzimit) përbëhen nga komandat ndjekëse dhe komandat e degëzimit. Një shembull i një algoritmi degëzimi do të ishte gjetja e numrit më të madh nga dy numrat e futur nga tastiera. |
 |
Komanda e degës mund të jetë e plotë ose e paplotë. Forma jo e plotë e komandës së degës përdoret kur është e nevojshme të kryhet një veprim S vetëm nëse plotësohet kushti P... Nëse kushti P nuk respektohet, komanda e degës del pa u marrë masa. Një shembull i një komande degëzimi jo të plotë do të ishte përgjysmimi i vetëm një numri çift. |
 |
Ekipi përsëritjetështë një komandë e përbërë e algoritmit, në të cilën, në varësi të kushtit Rështë i mundur ekzekutimi i shumëfishtë i veprimit S... Algoritmet ciklike (algoritmet e përsëritjes) përbëhen nga komandat ndjekëse dhe komandat e përsëritjes. Figura tregon një komandë përsëritjeje me një parakusht. Quhet kështu sepse së pari kontrollohet gjendja dhe vetëm atëherë kryhet veprimi. Për më tepër, veprimi kryhet për aq kohë sa plotësohet kushti. Një shembull i një algoritmi ciklik mund të jetë si më poshtë. Ndërsa numrat pozitivë futen nga tastiera, algoritmi gjen shumën e tyre. |
 |
Në një komandë përsëritjeje me një kusht pas, veprimi kryhet së pari S dhe vetëm atëherë është kushti P... Për më tepër, veprimi përsëritet derisa të plotësohet kushti. Një shembull i një komande përsëritjeje me një kusht pas do të ishte zvogëlimi i një numri pozitiv derisa ai të jetë jo negativ. Sapo numri bëhet negativ, komanda e përsëritjes përfundon punën e saj. |
Çdo ndërtim i treguar mund të zbatohet pa ndryshime në strukturë në çdo gjuhë programimi, për shembull, në Pascal dhe BASIC. Prandaj, është e nevojshme të hartoni saktë një algoritëm duke përdorur një diagram bllok, dhe vetëm atëherë, duke ditur se si shkruhen komandat në një gjuhë programimi specifike, shkruani programin në një kompjuter dhe merrni rezultatin duke e ekzekutuar atë për ekzekutim.
8.4. Algoritmi Linear
Le të japim një shembull të shkrimit të një algoritmi në formën e një bllok diagrami, pseudokodesh dhe në Pascal. Testimi manual dhe përzgjedhja e sistemit të testimit kryhen në të njëjtën mënyrë si në detyrën e mëparshme.
8.5. Algoritmi i forkimit
Këtu është një shembull i shkrimit të një algoritmi degëzimi për gjetjen e më të madhit nga dy numrat.
8.6. Algoritmi ciklik
Konsideroni një algoritëm për gjetjen e shumës së numrave të parë tekë natyrorë deri në n... Regjistrimin e algoritmit e paraqesim në tre mënyra: në formën e një bllok-diagrami, një gjuhe algoritmike shkollore dhe në gjuhën e programimit Pascal.
Diagrami bllok përbëhet nga strukturat e mëposhtme bazë: dy komanda të përbëra (një komandë ndjekjeje dhe një komandë përsëritje me një parakusht), pastaj një komandë e thjeshtë. Të gjitha komandat janë të lidhura në seri. Konstruktet janë të dizajnuara në një mënyrë standarde, kështu që ato janë të lehta për t'u njohur dhe përkthyer në gjuhën e programimit. Çdo strukturë ka një hyrje dhe një dalje.
Shigjetat me pika në tabelë tregojnë sekuencën e zinxhirit teknologjik. Pas shkrimit të algoritmit në formën e një diagrami bllok, çdo ekip përkthehet në gjuhën algoritmike të shkollës dhe vetëm më pas në gjuhën e programimit.
Le të shkruajmë një algoritëm për llogaritjen e shumës së n numrave të parë natyrorë. Për ta bërë këtë, ne do të përdorim një lak me një parametër, pasi dihet paraprakisht se sa herë do të ekzekutohet komanda për të gjetur shumën. Në të gjitha hallkat e zinxhirit, ne do të ndryshojmë ciklin "bye" në ciklin "për" dhe do të japim një shembull të përkthimit të algoritmit nga gjuha e grafikut të rrjedhës në gjuhën algoritmike të shkollës dhe në gjuhën e programimit Pascal.
Merrni parasysh gjetjen e numrit të numrave natyrorë, shuma e të cilëve nuk është më shumë se një e dhënë. Për ta bërë këtë, ne do të përdorim komandën përsëritje me një kusht pas.
Pyetje për vetëkontroll
- Koncepti i një algoritmi. Vetitë e algoritmit. Një shembull i një algoritmi. Koncepti i "ndryshueshme".
- Operatori i caktimit. Shembuj.
- Stilet e programimit (logjik, funksional).
- Kuptimi i një nënprogrami, moduli dhe objekti
- Çfarë është një variabël? Rregullat e emërtimit të ndryshoreve në Pascal. Shembuj.
- Operatori i caktimit. Shkrimi i shprehjeve në Pascal. Shembuj. Shpjegoni se si funksionon operatori x: = x + 1;
- Operatorët hyrës dhe dalës në Pascal. Shembuj. Prodhimi i formatuar.
- Operatori i kushtëzuar ( nëse). Shembull. Krahasoni me operatorin rast.
- Operatori i përzgjedhjes. Shembull. Krahasoni me operatorin nëse.
- Shprehje logjike. Operacionet ose, dhe dhe jo... Shembuj. Tabela e së vërtetës.
- Llojet numerike të variablave në Pascal. Lloji i rregullave të konvertimit. Shembuj.
- Lloji i të dhënave Boolean. Një shembull i përdorimit në program. Lloji i të dhënave të karakterit. Shembull. Funksione chr dhe ord, succ dhe pred.
- Vargjeve. Përkufizimi. Indekset e vargjeve. Deklaratat e vargjeve. Qasja në elementet e grupit. Vargjet njëdimensionale dhe dydimensionale. Shembuj. Ngjashmëritë dhe ndryshimet midis vargjeve dhe vargjeve.
- Procedurat. Përkufizimi. Pse nevojiten procedurat? Shembuj. Rregullat për përshkrimin e procedurave. Krahasoni procedurat dhe funksionet.
