Pra, variante të ndryshme të kompjuterëve konsiderohen nga makinat më të thjeshta Turing në një mjedis kompjuterik homogjen. Të gjitha ato mund të përdoren për të zgjidhur ato probleme për të cilat ekziston një algoritëm. Në bazë të këtyre modeleve ndërtohen modele llogaritëse më të specializuara, përkatësisht: programet aritmetike jo të degëzuara, llogaritjet bit, llogaritjet binar të vektorëve dhe pemët e vendimit.
Algoritmet kanë karakteristikat e mëposhtme:
a) kompleksiteti;
b) mundimshmëria;
c) besueshmëria etj.
Ka shumë kritere për vlerësimin e kompleksitetit të algoritmeve. Më shpesh ne do të jemi të interesuar rendi i rritjes kërkohet për të zgjidhur problemin e kohës dhe kapacitetit të kujtesës me një rritje të numrit të të dhënave hyrëse. Lidhni me secilën detyrë specifike një numër të caktuar, të quajtur atë madhësia. Për shembull, madhësia e një problemi të shumëzimit të matricës mund të jetë madhësia më e madhe e matricave - faktorëve; madhësia e problemit në grafik mund të jetë numri i skajeve të grafikut të dhënë, e kështu me radhë.
Koha e marrë nga algoritmi në funksion të madhësisë së detyrës quhet kompleksiteti kohor këtë algoritëm. Sjellja e këtij kompleksiteti në kufi me rritjen e madhësisë së problemit quhet kompleksiteti asimptotik kohor. Të kompleksiteti kapacitiv dhe kompleksiteti kapacitiv asimptotik.
Një motiv i rëndësishëm për shqyrtimin e modeleve formale llogaritëse është dëshira për të zbuluar kompleksitetin llogaritës të problemeve të ndryshme në mënyrë që të përftohen kufijtë më të ulët në kohën e llogaritjes. Për të treguar se nuk ka asnjë algoritëm që kryen një detyrë të caktuar në më pak se një kohë të caktuar, kërkon një përkufizim të saktë dhe ndonjëherë shumë të specializuar të asaj që është një algoritëm. Makinat Turing janë një shembull i një përkufizimi të tillë.
4.1.1. Makinat e kornizës dhe kornizës*
Konsideroni dy makina:
1. Makinat me akses të rastësishëm në memorie (makina e adresave ekuivalente - RAM) modelojnë një kompjuter me një grumbullues, në të cilin udhëzimet e programit nuk mund të ndryshojnë vetë.
2. Modeli i programit të ruajtur është një makinë me akses të rastësishëm në memorie dhe mundësi modifikimi të instruksioneve (PAM*).
Fig.2.9 Struktura e makinave PAM (PAM*)
Për RAM, programi nuk është i shkruar në memorie, kështu që programi nuk ndryshon vetë. Një program është një sekuencë komandash të etiketuara. Ka instruksione aritmetike, instruksione I/O, instruksione adresimi indirekte dhe instruksione degëzimi. Të gjitha llogaritjet kryhen në regjistrin r 0 (mbledhës), i cili, si çdo regjistër tjetër i memories, mund të ruajë një numër të plotë arbitrar. Çdo komandë përbëhet nga dy pjesë - një kod optik dhe një adresë. Instruksionet PAM janë një nëngrup i udhëzimeve të gjuhës së asamblesë; kjo nëngrup mund të zgjerohet sipas dëshirës, por rendi i kompleksitetit të problemeve nuk do të ndryshojë.
Operandi mund të jetë një nga llojet e mëposhtme:
1. =i nënkupton vetë numrin e plotë i dhe quhet literal;
2. i- përmbajtja e regjistrit i (i duhet të jetë jo negative)
3. *i do të thotë adresim indirekt, domethënë vlera e operandit është përmbajtja e regjistrit j, ku j- një numër i plotë që është në një regjistër Unë; nëse j<0, makina ndalon.
Mund të përcaktojë vlerën e programit R me ndihmën e dy objekteve: një hartë c nga grupi i numrave të plotë jo negativë në bashkësinë e numrave të plotë dhe një "numërues komandash", i cili përcakton komandën e ekzekutuar të radhës. Funksioni c është harta e kujtesës, domethënë c (i) - numër i plotë i përfshirë në numrin e regjistrit Unë (përmbajtjen regjistroheni Unë).
ne fillim c(i)=0 per te gjithe i 0 , numëruesi i programit vendoset në instruksionin e parë në P, dhe shiriti i daljes është bosh. Pasi bëri k-skuadra e thte nga R numëruesi kalon automatikisht në (k+1)-të (d.m.th., në komandën tjetër), nëse k- komanda nuk ishte JUMP, HALT, JGTZ dhe të ngjashme.
RAM*-programi qëndron në regjistrat e memories. Çdo instruksion PAM* zë dy regjistra memorie të njëpasnjëshme: regjistri i parë përmban kodin optik, i dyti - adresën. Seti i instruksioneve për PAM* është i njëjtë me grupin përkatës për PAM, përveç adresimit indirekt, i cili përjashtohet: PAM* mund të simulojë adresimin indirekt duke ndryshuar instruksionet gjatë ekzekutimit të programit.
Algoritmi- një grup udhëzimesh që përshkruajnë rendin e veprimeve të interpretuesit për të arritur një rezultat.
Efikasiteti i përkohshëmështë tregues i shpejtësisë së algoritmit
e vlerësuar nga numri i operacioneve bazë që duhet të kryejë algoritmi gjatë përpunimit të të dhënave hyrëse të madhësisë n
Rendi i rritjes së kohës së ekzekutimit të algoritmit në varësi të n është i rëndësishëm
Efikasiteti hapësinor tregon se sa RAM shtesë nevojitet që algoritmi të funksionojë. Efikasiteti vlerësohet në rastet më të këqija, më të mira dhe mesatare.
Llojet e analizave: matematikore dhe empirike
Matja e kohës së ekzekutimit të një algoritmi
1. Direkt (analizë empirike)
2. Përcaktimi i numrit të operacioneve bazë që duhet të kryejë algoritmi gjatë përpunimit të të dhënave hyrëse të madhësisë n (analizë matematikore)
Urdhri i rritjes
Me madhësi të vogla të hyrjes, është e pamundur të vërehet ndryshimi në kohën e ekzekutimit midis një algoritmi efikas dhe joefikas. Për vlera të mëdha të n, llogaritet rendi i rritjes së funksionit.
Efikasiteti i algoritmit në raste të ndryshme
Ekziston një numër i madh algoritmesh, koha e ekzekutimit të të cilave varet jo vetëm nga madhësia e të dhënave hyrëse, por edhe nga veçoritë specifike të të dhënave hyrëse (një shembull është kërkimi).
Efikasiteti matet për:
Shembull: numri mesatar i krahasimeve në një kërkim:
Kështu që:
Kur zhvilloni algoritme, është shumë e rëndësishme të jeni në gjendje të vlerësoni burimet e nevojshme për kryerjen e llogaritjeve; rezultati i vlerësimit është një funksion i kompleksitetit (inputi i punës). Burimi i vlerësuar është më shpesh koha e CPU (kompleksiteti llogaritës) dhe memoria (kompleksiteti i memories së algoritmit). Vlerësimi ju lejon të parashikoni kohën e ekzekutimit dhe të krahasoni performancën e algoritmeve.
Efikasiteti i Algoritmitështë një veti e një algoritmi që lidhet me burimet llogaritëse të përdorura nga algoritmi. Algoritmi duhet të analizohet për të përcaktuar burimet e nevojshme për algoritmin. Efikasiteti i algoritmit mund të shihet si analog me performancën e prodhimit të proceseve të përsëritura ose të vazhdueshme.
Për të arritur efikasitetin maksimal, ne duam të reduktojmë përdorimin e burimeve. Megjithatë, burimet e ndryshme (si koha dhe memoria) nuk mund të krahasohen drejtpërdrejt, kështu që cili nga dy algoritmet konsiderohet më efikas shpesh varet nga cili faktor është më i rëndësishëm, si p.sh. kërkesa për shpejtësi të lartë, përdorim minimal të memories ose një masë tjetër. të efikasitetit.
Vini re se ky artikull JO në lidhje me optimizimin e algoritmit, i cili diskutohet në programet e optimizimit të artikujve, përpiluesi optimizues, optimizimi i ciklit, optimizuesi i kodit të objektit, etj. Termi "optimizim" në vetvete është mashtrues, pasi gjithçka që mund të bëhet bie nën përkufizimin e "përmirësimit".YouTube enciklopedik
1 / 5
✪CS50. Shënim asimptotik
✪ 1. Algoritmet dhe strukturat e të dhënave. Hyrje | Technostream
✪ Efikasiteti algoritmik
✪ Algoritmi Knuth-Morris-Pratt
✪ 2. Algoritmet dhe strukturat e të dhënave. Listat, rafte, radhë, dhjetor | Technostream
Titra
Me siguri keni dëgjuar njerëz që flasin për algoritme të shpejta ose efikase për kryerjen e një detyre të caktuar, por çfarë saktësisht kuptoni me të shpejtë dhe efikas në rastin e algoritmeve? Ata nuk po flasin vërtet për matjet e kohës reale në sekonda apo minuta. Sepse hardueri dhe softueri kompjuterik janë shumë të larmishëm. Programi im mund të funksionojë më ngadalë se i yti sepse jam duke e ekzekutuar në një kompjuter më të vjetër, ose sepse jam duke luajtur një lojë rrjeti në të njëjtën kohë, e cila më ha gjithë kujtesën. Ose e drejtova programin tim përmes softuerëve të tjerë që ndërveprojnë me harduerin në një nivel të ulët në mënyrën e vet. Është si të krahasosh të ngrohtë me të butë. Vetëm për shkak se kompjuteri im më i ngadalshëm kërkon më shumë kohë për të gjetur një përgjigje, nuk do të thotë se algoritmi juaj është më efikas. Meqenëse nuk mund të krahasojmë drejtpërdrejt kohën e ekzekutimit të programeve në sekonda ose minuta, si mund të krahasojmë dy algoritme të ndryshme pa u varur nga hardueri ose softueri? Për të unifikuar mënyrën e matjes së efikasitetit algoritmik, matematikanët dhe shkencëtarët kompjuterikë kanë gjetur një zgjidhje në matjen e kompleksitetit asimptotik të një programi dhe të ashtuquajturin shënim "Big O" për ta përshkruar atë. Përkufizimi formal është: Një funksion f(x) ka rend g(x) nëse ka një vlerë të tillë "x", "x₀" dhe një konstante "C" për të cilën f(x) është më e vogël ose e barabartë me këtë konstante. shumëzuar me g (x) për çdo "x" më të madh se "x₀". Megjithatë, mos u frikësoni nga përkufizimi zyrtar. Çfarë do të thotë në të vërtetë kjo në terma më pak teorikë? Epo, për ta thënë thjesht, është një mënyrë për të analizuar se sa shpejt rritet koha asimptotike e ekzekutimit të një programi. Kjo do të thotë, ndërsa madhësia e hyrjes rritet drejt pafundësisë. Le të themi se renditim një grup prej 1000 elementësh dhe një grup prej 10. Si do të rritet koha e ekzekutimit të programit? Për shembull, imagjinoni të numëroni numrin e karaktereve në një varg në mënyrën më të thjeshtë, duke kaluar nëpër të gjithë vargun shkronjë për shkronjë dhe duke shtuar një në numërues çdo herë. Thuhet se algoritmi funksionon në kohë lineare në numrin e karaktereve (n) në varg. Ose shkurtimisht, duhet O(n). Pse eshte ajo? Epo, me këtë qasje, koha që duhet për të kaluar nëpër të gjithë vargun është proporcionale me numrin e karaktereve në të. Numërimi i numrit të karaktereve në një varg me 20 karaktere do të zgjasë dy herë më shumë se numërimi në një varg me 10 karaktere, sepse duhet të shikoni të gjithë karakteret dhe shikimi i secilit karakter kërkon të njëjtën kohë. Ndërsa numri i karaktereve rritet, koha e ekzekutimit do të rritet së bashku me gjatësinë e të dhënave burimore. Tani, le të themi se vendosni që koha lineare, O(n), nuk është mjaft e shpejtë. Ndoshta po ruani vargje të mëdha dhe nuk mund të përballoni kohën shtesë për të kaluar nëpër të gjithë personazhet, duke i numëruar një nga një. Dhe ju vendosni të provoni diçka ndryshe. Po sikur numri i karaktereve për vargun tashmë të ruhet në një variabël, të themi "len". Ai ruhet në program më herët, edhe para se të ruani karakterin e parë të vargut tuaj. Atëherë gjithçka që duhet të bëni për të gjetur gjatësinë e një vargu është të lexoni vlerën e asaj ndryshore. Ju nuk do të duhet të shikoni fare vargun, dhe leximi i vlerës së "len" supozohet të jetë një operacion që kërkon kohë asimptotike konstante, ose O(1). Pse eshte ajo? Kujtoni se çfarë do të thotë kompleksiteti asimptotik. Si ndryshon koha e ekzekutimit ndërsa madhësia e hyrjes rritet? Le të themi se merrni numrin e karaktereve në një varg më të gjatë. Në përgjithësi, nuk ka rëndësi fare se sa është e gjatë. Të paktën një milion personazhe. Me këtë qasje, gjithçka që duhet të bëni për të gjetur gjatësinë e një vargu është të lexoni vlerën e ndryshores "len" që keni marrë tashmë. Madhësia e hyrjes, në rastin tonë vargu që duam të gjejmë gjatësinë, nuk do të ndikojë fare në shpejtësinë e ekzekutimit të programit. Kjo pjesë e programit tuaj do të funksionojë po aq shpejt në një linjë me një karakter sa në një linjë me një mijë karaktere. Dhe kjo është arsyeja pse programi do të konsiderohet se funksionon në kohë konstante në lidhje me madhësinë e të dhënave hyrëse. Sigurisht, ka edhe disavantazhe. Po humbisni memorie shtesë në kompjuterin tuaj për të ruajtur variablin, si dhe kohë shtesë për të plotësuar vlerën e saj. Por ende ka kuptim. Koha për të marrë numrin e karaktereve në një varg nuk varet aspak nga gjatësia e vargut. Pra, funksionon në O(1) ose në kohë konstante. Sigurisht, kjo nuk do të thotë domosdoshmërisht që kodi juaj merr vetëm një hap. Megjithatë, nuk ka rëndësi sa hapa ka, përderisa numri i tyre nuk ndryshon kur ndryshon madhësia e hyrjes. Do të jetë asimptotikisht konstante, të cilën e shënojmë si O(1). Siç mund ta keni marrë me mend, ka shumë "O të mëdha" të ndryshme për matjen e kohës së ekzekutimit të algoritmeve. Algoritmet O(n²) janë asimptotikisht më të ngadaltë se algoritmet O(n). Kjo do të thotë se me rritjen e numrit të elementeve, n, algoritmet O(n²) përfundimisht do të zgjasin më shumë se algoritmet O(n). Kjo nuk do të thotë që algoritmet O(n) janë gjithmonë më të shpejtë se algoritmet O(n²), edhe në të njëjtin mjedis në të njëjtin harduer. Mund të ndodhë që për hyrje të vogla, algoritmi O(n²) në fakt do të funksionojë më shpejt, por me kalimin e kohës, ndërsa madhësia e të dhënave hyrëse rritet drejt pafundësisë, koha e ekzekutimit të algoritmit O(n²) përfundimisht do të eklipsojë kohën e ekzekutimit. të algoritmit O(n). Si dhe çdo funksion matematikor kuadratik përfundimisht do të kapërcejë çdo funksion linear. Dhe nuk ka rëndësi se sa i madh është handikapi i vlerës së funksionit linear që në fillim. Nëse punoni me sasi të mëdha të dhënash, atëherë algoritmet që funksionojnë në O(n²) përfundimisht do të ngadalësojnë programin tuaj, por me të dhëna të vogla hyrëse, ka shumë të ngjarë që as ta vini re këtë. Një lloj tjetër kompleksiteti asimptotik është koha logaritmike, O(log n). Një shembull i një algoritmi që funksionon kaq shpejt është algoritmi klasik i kërkimit binar për gjetjen e një elementi në një grup të paravendosur. Nëse nuk e dini se si bëhet një kërkim binar, unë do t'ju shpjegoj shpejt gjithçka në një moment. Le të themi se po kërkoni numrin 3 në një grup numrash të plotë. Marrim elementin qendror të grupit dhe pyesim: "A është elementi që më nevojitet më i madh, më i vogël se, apo i barabartë me këtë?" Nëse është e barabartë, shkëlqyeshëm. Ne gjetëm elementin e duhur, kjo është e gjitha. Nëse më shumë, atëherë është e qartë se elementi ynë duhet të jetë në grup diku në të djathtë, dhe atëherë mund të shikoni vetëm në anën e djathtë. Nëse më pak, atëherë është e qartë se elementi është diku në të majtë. Më pas e përsërisim këtë proces me vargje gjithnjë e më të shkurtra derisa të gjejmë elementin e dëshiruar. Ky algoritëm i fuqishëm përgjysmon madhësinë e grupit pas çdo operacioni. Kjo do të thotë, për të gjetur një element në një grup të renditur me gjatësi 8, nuk nevojiten më shumë se (log₂8) ose tre operacione të tilla për të kontrolluar elementin qendror dhe për të zgjedhur gjysmën e dëshiruar. Në të njëjtën kohë, një grup me gjatësi 16 do të kërkonte (log₂16) ose katër operacione. Dhe ky është vetëm një operacion shtesë kur dyfishohet gjatësia e grupit. Dyfishimi i madhësisë rrit kohën e ekzekutimit me vetëm një pjesë të kodit. Edhe një herë, ne kontrollojmë elementin qendror dhe ndajmë grupin. Pra, kjo quhet kohë logaritmike, O(log n). Por prisni, thoni ju, a nuk varet se ku në grup ndodhet elementi që kërkoni? Po nëse elementi i parë që kontrollojmë është ai? Atëherë duhet vetëm një operacion, pavarësisht sa i madh është grupi. Kjo është arsyeja pse në shkencën kompjuterike ekzistojnë ende koncepte të tjera për kompleksitetin asimptotik, të cilat pasqyrojnë performancën në rastin më të mirë dhe më të keq. Ose, më saktësisht, kufijtë e sipërm dhe të poshtëm të kohës së ekzekutimit të algoritmit. Në rastin më të mirë për një kërkim binar, elementi ynë është pikërisht këtu në qendër. E gjejmë në kohë konstante, pavarësisht nga madhësia e pjesës tjetër të grupit. Për ta bërë këtë, përdorni simbolin Ω. Kjo do të thotë, thuhet se algoritmi funksionon në Ω(1). Në rastin më të mirë, ai e gjen elementin shumë shpejt. Nuk ka rëndësi se sa i madh është grupi. Por në rastin më të keq, ju duhet të kryeni (log n) kontrolle dhe ndarje të grupeve për të gjetur elementin e dëshiruar. Kufiri i sipërm për rastin më të keq shënohet me "big O", siç e dini tashmë. Kështu rezulton O(log n), por Ω(1). Për krahasim, një kërkim linear, në të cilin ne shikojmë çdo element në grup për të gjetur atë të duhurin, në rastin më të mirë Ω (1). Domethënë, sërish elementi i parë rezulton të jetë ai që kërkojmë. Prandaj, nuk ka rëndësi se sa i madh është grupi ynë. Në rastin më të keq, elementi që po kërkoni është në fund. Dhe ju duhet të kaloni nëpër të gjithë n elementët e grupit për ta gjetur atë. Kështu, nëse kërkojmë 3. Domethënë, koha e ekzekutimit të tij është O(n), pasi është proporcionale me numrin e elementeve të grupit. Përdoret gjithashtu simboli Θ. Përdoret për të përshkruar algoritme që kanë të njëjtat kohë më të mira dhe më të këqija. Ashtu si në rastin e algoritmit të kërkimit të gjatësisë së vargut për të cilin folëm më herët. Ai ku e ruajmë gjatësinë në një variabël paraprakisht, dhe më vonë thjesht e lexojmë atë në kohë konstante. Pavarësisht se çfarë numri ruajmë në këtë variabël, ne do ta shikojmë atë. Në rastin më të mirë, ne shikojmë vlerën dhe marrim gjatësinë e vargut. Kjo është Ω(1) ose kohë konstante për rastin më të mirë. Në rastin më të keq, ne shikojmë vlerën dhe marrim gjatësinë e vargut. Kjo është O(1) ose kohë konstante për rastin më të keq. Kështu, rastet më të mira dhe më të këqija janë të njëjta. Dhe mund të themi se algoritmi ekzekutohet në kohën Θ(1). Për ta përmbledhur, ne kemi mënyra të mira për të arsyetuar për efikasitetin e kodit pa kuptuar se sa kohë reale do të duhet për t'u ekzekutuar. Kjo kohë varet nga një numër i madh faktorësh të jashtëm, si hardueri dhe softueri, si dhe nga specifikat e vetë kodit. Ne gjithashtu mund të arsyetojmë qartë se çfarë do të ndodhë kur të rritet madhësia e të dhënave hyrëse. Nëse kemi një algoritëm O(n²), ose edhe më keq një algoritëm O(2ⁿ), pra një nga llojet me rritje më të shpejtë, atëherë ngadalësimi është me të vërtetë i vështirë për t'u humbur kur kemi të bëjmë me sasi në rritje të të dhënave. Ky është kompleksiteti asimptotik. Faleminderit per vemendjen.
Sfondi
Rëndësia e efikasitetit me një theks në kohën e ekzekutimit u theksua nga Ada Lovelace në 1843 në lidhje me motorin mekanik analitik të Charles Babbage:
“Pothuajse në të gjitha llogaritjet, një gamë e gjerë konfigurimesh është e mundur për përfundimin me sukses të procesit dhe konventa të ndryshme duhet të ndikojnë në zgjedhjen për të kryer llogaritjet. Gjëja kryesore është të zgjidhni një konfigurim që do të rezultojë në minimizimin e kohës së nevojshme për të përfunduar llogaritjen.
Kompjuterët elektronikë të hershëm ishin shumë të kufizuar si në shpejtësi ashtu edhe në memorie. Në disa raste, është kuptuar se ekziston një shkëmbim kohë/memorie në të cilën detyra ose duhet të përdorë një sasi të madhe memorie për të arritur shpejtësi të lartë, ose të përdorë një algoritëm më të ngadaltë që përdor një sasi të vogël memorie pune. Në këtë rast, u përdor algoritmi më i shpejtë, për të cilin kishte mjaftueshëm memorie të disponueshme.
Kompjuterët modernë janë shumë më të shpejtë se ata kompjuterë të hershëm dhe kanë shumë më tepër memorie (gigabajt në vend të kilobajt). Megjithatë, Donald Knuth thekson se efikasiteti mbetet një faktor i rëndësishëm:
"Në disiplinat e themeluara inxhinierike, një përmirësim prej 12% është lehtësisht i arritshëm, nuk është konsideruar kurrë jashtë zakonit dhe besoj se e njëjta gjë duhet të jetë e vërtetë në programim."
Rishikimi
Një algoritëm konsiderohet efikas nëse burimi që konsumon (ose kostoja e burimit) është në ose nën një nivel të pranueshëm. Përafërsisht, "i pranueshëm" këtu do të thotë "algoritmi do të funksionojë për një kohë të arsyeshme në një kompjuter të disponueshëm". Meqenëse ka pasur një rritje të konsiderueshme në fuqinë llogaritëse dhe memorien e disponueshme të kompjuterëve që nga vitet 1950, "niveli i pranueshëm" ekzistues nuk ishte i pranueshëm as 10 vjet më parë.
Prodhuesit e kompjuterëve lëshojnë periodikisht modele të reja, shpesh më të fuqishme. Kostoja e softuerit mund të jetë mjaft e lartë, kështu që në disa raste është më e lehtë dhe më e lirë të keni performancë më të mirë duke blerë një kompjuter më të shpejtë që është në përputhje me kompjuterin tuaj ekzistues.
Ka shumë mënyra për të matur burimet e përdorura nga një algoritëm. Dy matjet më të përdorura janë shpejtësia dhe memoria e përdorur. Matjet e tjera mund të përfshijnë shpejtësinë e transferimit, përdorimin e përkohshëm të diskut, përdorimin afatgjatë të diskut, konsumin e energjisë, koston totale të pronësisë, kohën e përgjigjes ndaj sinjaleve të jashtme, etj. Shumë nga këto matje varen nga madhësia e hyrjes së algoritmit (d.m.th., sasia e të dhënave që duhet të përpunohen). Matjet mund të varen edhe nga mënyra se si paraqiten të dhënat (për shembull, disa algoritme klasifikimi nuk funksionojnë mirë në të dhënat tashmë të renditura ose kur të dhënat renditen në rend të kundërt).
Në praktikë, ka faktorë të tjerë që ndikojnë në efikasitetin e një algoritmi, të tilla si saktësia dhe/ose qëndrueshmëria e kërkuar. Siç shpjegohet më poshtë, mënyra se si zbatohet një algoritëm mund të ketë gjithashtu një efekt të rëndësishëm në performancën aktuale, megjithëse shumë aspekte të zbatimit janë çështje optimizimi.
Analiza teorike
Në analizën teorike të algoritmeve, është praktikë e zakonshme të vlerësohet kompleksiteti i një algoritmi në sjelljen e tij asimptotike, domethënë, të pasqyrohet kompleksiteti i algoritmit në funksion të madhësisë së hyrjes. n përdoret shënimi "O" big. Ky vlerësim është përgjithësisht mjaft i saktë për të mëdhatë n, por mund të çojë në përfundime të pasakta në vlera të vogla n(Kështu, renditja me flluskë, e cila konsiderohet e ngadaltë, mund të jetë më e shpejtë se "shfaqja e shpejtë" nëse duhet të renditen vetëm disa elementë.)
Disa shembuj të shënimit të madh "O":
| Emërtimi | Emri | Shembuj |
|---|---|---|
| O(1) (\stil ekrani O(1)\,) | të përhershme | Përcaktimi nëse një numër është çift apo tek. Përdorimi i një tabele kërkimi me madhësi konstante. Përdorimi i një funksioni hash të përshtatshëm për të zgjedhur një element. |
| O (log n) (\displaystyle O(\log n)\,) | logaritmike | Gjetja e një elementi në një grup të renditur duke përdorur një kërkim binar ose një pemë të balancuar, ashtu si operacionet në një grumbull binomial. |
| O(n)(\style ekrani O(n)\,) | lineare | Gjetja e një elementi në një listë të parregulluar ose pemë të pabalancuar (rasti më i keq). Shtimi i dy n-numrat bit duke përdorur transportin nga skaji në fund. |
| O (n log n) (\displaystyle O(n\log n)\,) | kuazilinear, logaritmikisht linear | Llogaritja e transformimit të shpejtë të Furierit, renditja e grumbullit, renditja e shpejtë (rastet më të mira dhe mesatare), renditja e bashkimit |
| O(n 2) (\style ekrani O(n^(2))\,) | katrore | Shumëzimi i dy n-numrat shifrorë me një algoritëm të thjeshtë, renditja me flluska (rasti më i keq), renditja me guaskë, renditja e shpejtë (rasti më i keq), renditja me përzgjedhje, renditja me futje |
| O (c n) , c > 1 (\displaystyle O(c^(n)),\;c>1) | eksponenciale | Gjetja e një zgjidhjeje (të saktë) për problemin e shitësit udhëtues duke përdorur programimin dinamik. Përcaktimi nëse dy deklarata Boolean janë ekuivalente duke përdorur forcën brutale shteruese |
Testet e verifikimit: Matja e performancës
Për versionet e reja të softuerit, ose për të ofruar krahasim me sistemet konkurruese, ndonjëherë përdoren standarde për të krahasuar performancën relative të algoritmeve. Nëse, për shembull, lëshohet një algoritëm i ri klasifikimi, ai mund të krahasohet me paraardhësit për të siguruar që algoritmi të jetë të paktën po aq efikas në të dhënat e njohura sa të tjerët. Standardet mund të përdoren nga përdoruesit për të krahasuar produkte nga prodhues të ndryshëm për të vlerësuar se cili produkt do t'i përshtatet më mirë kërkesave të tyre për sa i përket funksionalitetit dhe performancës.
Disa standarde ofrojnë një mënyrë për të krahasuar gjuhë të ndryshme përpiluesish dhe interpretuesish, si p.sh. Koleksioni i standardeve kompjuterike të Roy Longbottom, dhe Loja e standardeve të gjuhës kompjuterike krahason performancën e zbatimeve të detyrave tipike në disa gjuhë programimi.
Çështjet e zbatimit
Çështjet e zbatimit mund të ndikojnë gjithashtu në performancën aktuale. Kjo përfshin zgjedhjen e gjuhës së programimit dhe mënyrën e kodimit të algoritmit, zgjedhjen e përkthyesit për gjuhën e zgjedhur ose opsionet e përpiluesit të përdorur, madje edhe sistemin operativ të përdorur. Në disa raste, një gjuhë e zbatuar si përkthyes mund të jetë dukshëm më e ngadaltë se një gjuhë e zbatuar si përpilues.
Ka faktorë të tjerë që mund të ndikojnë në përdorimin e kohës ose të kujtesës që janë jashtë kontrollit të programuesit. Kjo përfshin shtrirjen e të dhënave, granulariteti i të dhënave, grumbullimi i mbeturinave, paralelizmi i nivelit të udhëzimeve dhe thirrjet nënrutinë.
Disa procesorë kanë aftësinë për të kryer operacione vektoriale, gjë që lejon një operacion të përpunojë operandë të shumtë. Mund të jetë ose jo e lehtë të përdoren veçori të tilla në nivel programimi ose kompilimi. Algoritmet e dizajnuara për llogaritjen serike mund të kenë nevojë të ridizajnohen plotësisht për të përdorur llogaritjen paralele.
Një problem tjetër mund të lindë me përputhshmërinë e procesorëve, në të cilët udhëzimet mund të zbatohen ndryshe, kështu që udhëzimet në disa modele mund të jenë relativisht më të ngadalta në modele të tjera. Ky mund të jetë një problem për një përpilues optimizues.
Matja e përdorimit të burimeve
Matjet zakonisht shprehen si funksion i madhësisë së hyrjes. n.
Dy matjet më të rëndësishme janë:
- Koha: sa kohë i merr algoritmi CPU-së.
- Kujtesa: sa memorie pune (zakonisht RAM) i nevojitet algoritmit. Këtu ka dy aspekte: sasia e memories për kodin dhe sasia e memories për të dhënat me të cilat funksionon kodi.
Për kompjuterët me bateri (p.sh. laptopë) ose për llogaritjet shumë të gjata/të mëdha (p.sh. superkompjuterët), një lloj tjetër matjeje është me interes:
- Konsumi i drejtpërdrejtë i energjisë: Energjia e nevojshme për funksionimin e kompjuterit.
- Konsumi indirekt i energjisë: energjia e nevojshme për ftohje, ndriçim etj.
Në disa raste, nevojiten matje të tjera, më pak të zakonshme:
- Madhësia e transferimit: Gjerësia e brezit mund të jetë një faktor kufizues. Kompresimi mund të përdoret për të reduktuar sasinë e të dhënave të transferuara. Shfaqja e një fotografie ose imazhi (si logoja e Google) mund të rezultojë në transferimin e dhjetëra mijëra bajteve (48K në këtë rast). Krahasoni këtë me dërgimin e gjashtë bajt në fjalën "Google".
- Kujtesa e jashtme: Kujtesa e kërkuar në një disk ose pajisje tjetër ruajtëse të jashtme. Kjo memorie mund të përdoret për ruajtje të përkohshme ose për përdorim në të ardhmen.
- Koha e përgjigjes: Ky cilësim është veçanërisht i rëndësishëm për aplikacionet në kohë reale ku kompjuteri duhet t'i përgjigjet shpejt ngjarjeve të jashtme.
- Kostoja totale e pronësisë: Parametri është i rëndësishëm kur synohet të ekzekutojë një algoritëm të vetëm.
Koha
Teoria
Ky lloj testesh varet shumë edhe nga zgjedhja e gjuhës programuese, kompajlerit dhe opsioneve të tij, kështu që algoritmet e krahasuara duhet të zbatohen në të njëjtat kushte.
Kujtesa
Ky seksion merret me përdorimin e memories kryesore (shpesh RAM) të kërkuar nga algoritmi. Sa i përket analizës kohore të mësipërme, analiza e algoritmit zakonisht përdoret për të analizuar kompleksiteti hapësinor i algoritmit për të vlerësuar memorien e kërkuar të kohës së ekzekutimit në funksion të madhësisë së hyrjes. Rezultati zakonisht shprehet në termat "O" i madh.
Ekzistojnë katër aspekte të përdorimit të kujtesës:
- Sasia e memories që kërkohet për të ruajtur kodin e algoritmit.
- Sasia e memories që kërkohet për të dhënat hyrëse.
- Sasia e memories që kërkohet për çdo dalje (disa algoritme, të tilla si llojet, shpesh e riorganizojnë hyrjen dhe nuk kërkojnë memorie shtesë për daljen).
- Sasia e memories që i nevojitet procesit llogaritës gjatë llogaritjes (kjo përfshin variabla të emërtuar dhe çdo hapësirë të grumbullit të nevojshëm për të thirrur nënprograme, të cilat mund të jenë të rëndësishme kur përdorni rekursion).
Kompjuterët elektronikë të hershëm dhe kompjuterët shtëpiak kishin relativisht pak memorie pune. Pra, në 1949 EDSAC kishte një memorie pune maksimale prej 1024 fjalësh 17-bit, dhe në vitin 1980 Sinclair ZX80 u prodhua me 1024 bajt memorie pune.
Kompjuterët modernë mund të kenë sasi relativisht të mëdha memorie (ndoshta gigabajt), kështu që duhet më pak për të kompresuar memorien e përdorur nga një algoritëm në një sasi të caktuar memorie sesa dikur. Megjithatë, ekzistenca e tre kategorive të ndryshme të kujtesës është thelbësore:
- Cache (shpesh statike RAM) - funksionon me shpejtësi të krahasueshme me CPU
- Kujtesa kryesore fizike (shpesh RAM dinamik) - pak më e ngadaltë se CPU
- Kujtesa virtuale (shpesh në disk) - jep iluzionin e memories së madhe, por është mijëra herë më e ngadaltë se RAM.
Një algoritëm memoria e kërkuar e të cilit përshtatet në cache-in e kompjuterit funksionon shumë më shpejt se një algoritëm që përshtatet në memorien kryesore, e cila, nga ana tjetër, do të jetë shumë më e shpejtë se një algoritëm që përdor hapësirën virtuale. Çështjet e ndërlikuara është fakti se disa sisteme kanë deri në tre nivele cache. Sisteme të ndryshme kanë sasi të ndryshme të këtyre llojeve të memories, kështu që efekti i kujtesës në një algoritëm mund të ndryshojë ndjeshëm nga një sistem në tjetrin.
Në ditët e para të llogaritjes elektronike, nëse një algoritëm dhe të dhënat e tij nuk përshtateshin në memorien kryesore, ai nuk mund të përdorej. Këto ditë, përdorimi i memories virtuale siguron memorie të madhe, por me koston e performancës. Nëse algoritmi dhe të dhënat e tij përshtaten në cache, mund të arrihet shpejtësi shumë e lartë, kështu që minimizimi i memories së kërkuar ndihmon në minimizimin e kohës. Një algoritëm që nuk përshtatet plotësisht në cache, por ofron lokaliteti i lidhjes mund të ecë relativisht shpejt.
AT burgim jepet një paraqitje konsistente, logjikisht koherente e rezultateve të marra dhe lidhja e tyre me qëllimin e përgjithshëm (hipotezën) dhe objektivat e kërkimit, bëhen përfundime të përgjithësuara, formulohen pikëpamjet dhe sugjerimet e autorit për përmirësimin e problemit në studim. Vëllimi i tekstit të përfundimit në punën përfundimtare kualifikuese nuk është i rregulluar rreptësisht - zakonisht është 1.5 - 3 faqe.
AT lista e burimeve të përdorura Ato dokumente, materiale, periodikë, literaturë që janë përdorur në studim tregohen pa dështuar. Mos e bëni listën shumë të madhe; Gjithashtu është e papranueshme përfshirja e teksteve që nuk kanë lidhje me problemin në studim.
Përpilimi i një liste të burimeve dhe literaturës së përdorur është një nga fazat më të rëndësishme të punës mbi studimin, pasi pasqyron qasjen e pavarur, krijuese të autorit të saj ndaj përzgjedhjes së literaturës shkencore dhe studimit të problemit të zgjedhur dhe i lejon dikujt që të gjykoni shkallën e seriozitetit dhe vlefshmërisë së studimit.
Nëse është e nevojshme, lista bibliografike mund të përfshijë, për shembull, seksione të tilla si:
1. Dokumentet e organeve shtetërore dhe organizatave publike;
2. Dokumentet e arkivave;
3. Referencat dhe publikimet statistikore;
4. Publikime edukative dhe edukative;
5. Monografi dhe artikuj shkencorë;
7. Revista periodike;
Lista e botimeve periodike dhe edukative, literaturës, disertacioneve dhe abstrakteve është formuar sipas alfabetit nga emrat e autorëve dhe titujt e librave/artikujve.
Numri i burimeve në listën bibliografike të veprës përfundimtare kualifikuese nuk mund të jetë më pak se 25-30 artikuj.
Është lëshuar në përputhje me GOST 2003 ose GOST R 7.0.5-2008 "Referencë bibliografike".
Shembuj të përshkrimeve bibliografike të burimeve të cituara
1. Turuta E.F. Komponentët aktivë SMD: shënimi, karakteristikat, zëvendësimi. - Shën Petersburg: Shkenca dhe teknologjia, 2006. - 544 f.
2. Ulrich V.A. Mikrokontrolluesit PIC16X7XX. - Shën Petersburg: Shkenca dhe teknologjia, 2002. - 320 f.
Libri ka një redaktor
1. Remizevich T.V. Mikrokontrolluesit për aplikacione të integruara: nga kalimet e përgjithshme në familjet HC05 dhe HC08 të Motorola. / ed. Kiryukhina I.S. - M.: DODEKA, 2000. - 272 f.
Një lloj i caktuar pune (libër shkollor, libër referimi, enciklopedi, etj.)
1. Finkelstein M.I. Bazat e radarit: Proc. për universitetet. - M.: Radio dhe komunikim, 1983. - 536 f.
2. Guk M. Hardware IBM PC: Enciklopedia. - Shën Petersburg: Shtëpia Botuese "Peter", 1999. - 816 f.
1. Iglovsky I.G. Reletë elektrike me rrymë të ulët: një Manual / I.G. Iglovsky, G.V. Vladimirov. - M.: KUBK-a, 1996. - 560 f.
2. Romanycheva E.T. Inxhinieri dhe grafika kompjuterike / E.T. Romanycheva, T.Yu. Sokolova, G.F. Shandurin. – M.: DMK Press, 2001. – 592 f.
Nëse një libër ka katër autorë dhe botimi ka një redaktues, të gjithë ata renditen pas një prerje përpara (/). Nëse libri ka më shumë se katër autorë, tre të parët renditen pas titullit të ndjekur nga një pjerrësi (/) dhe shtohen fjalët "dhe të tjerët".
3. Sistemet radioinxhinierike: Proc. për universitetet në speciale "Radio Inxhinieri" / Yu.P. Grishin, V.P. Ipatov, Yu.M. Kazarinov dhe të tjerët; Ed. Yu.M. Kazarinov. - M .: Më e lartë. shkollë, 1990. - 496 f.
Nëse botimi nuk ka një redaktues, atëherë blloku “; Ed. Yu.M. Kazarinova.", mungon.
Libri është përkthyer nga një gjuhë tjetër dhe nuk ka autor
1. Burimet e Microsoft Windows Server 4.0. Libri 1: përkth. nga anglishtja. - Shën Petersburg: BHV - Shën Petersburg, 1997. - 408 f.
Artikuj nga revista
1. Odnobokov V.V. Argumentimi i metodës kryesore të shpërndarjes optimale të burimeve Nauchno-tekhnicheskie vedomosti. - Shën Petersburg: Shtëpia Botuese e Universitetit Shtetëror Politeknik të Shën Petersburgut, 2003. - vëll. 4. - Fq.55-62.
Artikuj nga koleksioni
1. Glazyrin B. E. Automatizimi i operacioneve individuale në Word 2000 // Office 2000: 5 libra. në 1 - M., 2002. - T. 3, Ch. 14. - S. 281-298.
Përshkrimi i artikullit jepet në titull nëse libri është shkruar nga katër ose më shumë autorë. Nëse artikulli është shkruar nga katër autorë, atëherë të gjithë janë renditur pas një të pjerrët (/).
1. A. N. Bogolyubov, A. L. Delitsyn dhe M. D. Malykh, "Mbi rezonancat reale në një valëzues me mbushje johomogjene", Vestn. Moska universiteti Ser. 3, Fizikë. Astronomi. - 2001. - Nr. 5. - S. 23–25.
Standardet
1. Skemat e algoritmeve, programeve, të dhënave dhe sistemeve. Simbolet dhe rregullat e zbatimit: GOST 19.701–90 (ISO 5807–85). – Prezantuar 1992–01–01. - M .: Gosstandart i BRSS: Shtëpia Botuese e Standardeve, 1991. - 26 f.
2. Pajisje elektronike shtëpiake. Parametrat e hyrjes dhe daljes dhe llojet e lidhjeve. Kërkesat teknike: GOST R 51771–2001. – Prezantuar 2002–01–01. - M.: Gosstandart i Rusisë: Shtëpia Botuese e Standardeve, 2001. - 27 f.
Dokumentet e Patentave
1. Pajisja transmetuese: Pat. 2187888 Ros. Federata / Chugaeva V.I.; aplikanti dhe mbajtësi i patentës Voronezh. kërkimin shkencor lidhje in-t. - Nr.2000131736/09; dhjetor 18.12.00; publikim. 20.08.02, Bul. Nr 23 (pjesa II). - 3 s.
Burimet elektronike të aksesit në distancë
1. Yu. A. Kochetov. Teoria e vendimmarrjes / Universiteti Shtetëror i Novosibirsk. – Mënyra e hyrjes: http://math.nsc.ru/LBRT/k5/or.html
2. M. Perov. Organizimi i punës me lista të ngjashme me pemët // Mir PK - Electron. revistë. - Shtëpia Botuese "Sistemet e Hapura", 2008. - Nr. 1. - Mënyra e hyrjes në ditar: http://www.osp.ru
3. Hulumtuar në Rusi: shumë lëndë. shkencore revistë / Moskë. fizikës dhe teknologjisë in-t. – Elektroni. revistë - Dolgoprudny: MIPT, 1998. - Mënyra e hyrjes në ditar: http://zhurnal.mipt.rssi.ru. - Jo shtet. regjistrimi 0329900013.
Burimet elektronike të aksesit lokal
1. Internet hap pas hapi. – Elektroni. Dan. dhe progr. - Shën Petersburg. : PiterKom, 1997. - 1 elektron. zgjedh. disk (CD-ROM) + adj. (127 f.)
2. Fjalor i madh shpjegues i gjuhëve angleze dhe ruse: 2 në 1. - Electron. Dan. dhe progr. - Maccelesfield (MB): Europa House, 1999. - 1 elektron. zgjedh. disk (CD-ROM).
3. Visio Professional: Biblioteka e Inxhinierëve të Dizajnit 5.0. – Elektroni. Dan. dhe progr. - 1997. - 1 elektron. zgjedh. disk (CD-ROM).
Lista përfshin 2 artikuj në Rusisht (të detyrueshme ) + 2 të përkthyera në anglisht. (opsionale), shkruar me pjesëmarrjen e aplikantit.
Aplikacionet
Anekset përfshihen vetëm nëse ka materiale shtesë dhe mbështetëse që rrëmojnë tekstin e pjesës kryesore të WRC dhe janë referuar në vetë veprën.
Aplikimet mund të përfshijnë materialet e mëposhtme:
- akti i futjes së rezultateve të kërkimit në prodhim ose në procesin arsimor;
– aplikimi për një patentë ose model të shërbimeve;
– raport për hulumtimin e paraqitur në konkursin e punimeve të studentëve;
- paraqitjet e pajisjeve, paketat e softuerëve të aplikacioneve, informacione rreth raporteve në konferenca mbi temën e WRC, etj.
– protokollet e kërkimit etj.
3.3 Përgatitja dhe ekzekutimi i versionit përfundimtar të WRC
Kërkesat e projektimit
Teksti i WRC duhet të printohet duke përdorur një kompjuter dhe një printer në njërën anë të letrës së bardhë A4 në përputhje me GOST 9327-60.
Teksti kryesor i veprës shtypet në intervale 1,5 (27-30 rreshta për faqe) dhe në 1 interval (lidhje dhe fusnota) në Times New Roman, madhësia 14 (teksti kryesor), 12 - teksti në lidhje, fusnota dhe tabela. Madhësia e kufirit të majtë është 30 mm, diferenca e djathtë është 10 mm, kufijtë e sipërm dhe të poshtëm janë 20 mm secila. Teksti i veprës është rreshtuar në gjerësi.
Cilësia e tekstit të printuar dhe dizajni i ilustrimeve dhe tabelave duhet të plotësojnë kërkesat për riprodhimin e qartë të tyre. WRC duhet të ketë vija, shkronja, numra dhe shenja të qarta.
Shtypjet e gabuara, gabimet dhe pasaktësitë e tjera të gjetura në tekst mund të korrigjohen duke fshirë ose lyer me bojë të bardhë, e ndjekur nga aplikimi i tekstit të korrigjuar (grafika) me makinë ose të shkruar me dorë. Nuk lejohen ngjitëse, dëmtime të fletëve të WRC, njolla.
Mbiemrat, emrat e institucioneve dhe emrat e tjerë të përveçëm në tekstin e WRC jepen në gjuhën origjinale. Lejohet të transliterohen emrat e duhur dhe të jepen emrat e institucioneve të përkthyera në Rusisht me shtimin (në përmendjen e parë) të emrit origjinal. Emrat duhet të shkruhen në rendin e mëposhtëm: mbiemri, emri, patronimi ose - mbiemri, inicialet të ndara me hapësira, nuk lejohet kalimi i inicialeve veçmas nga mbiemri në rreshtin tjetër.
Shkurtesa e fjalëve dhe frazave ruse në tekstin e WRC kryhet në përputhje me GOST 7.12-93, shkurtimi i fjalëve në gjuhët e huaja evropiane - në përputhje me GOST 7.11-2004. Shkurtesat e fjalëve dhe frazave të mëposhtme nuk lejohen: "pasi", "i ashtuquajturi", "kështu", "kështu", "për shembull". Nëse WRC ka miratuar një sistem të veçantë shkurtesash për fjalët dhe emrat, atëherë lista e shkurtesave të pranuara duhet të jepet në elementin strukturor të WRC "Përkufizime, emërtime dhe shkurtime". Në tekstin e WRC, përveç shkurtesave alfabetike të pranuara përgjithësisht, lejohet përdorimi i shkurtesave alfabetike të prezantuara nga autorët e tyre, të cilat shkurtojnë çdo koncept nga fushat përkatëse të njohurive. Në këtë rast, përmendja e parë e shkurtesave të tilla tregohet në kllapa pas emrit të plotë, në të ardhmen ato përdoren në tekst pa dekodim.
Numërimi i seksioneve, nënseksioneve, paragrafëve, nënparagrafëve
Emrat e elementeve strukturore "PERMBAJTJA", "PERKUFIZIMET, SIMBOLE DHE SHKURTESA", "HYRJE", "KONKLUZION", "LISTA E BURIMEVE TË PËRDORUR" janë titujt e elementeve strukturorë të WRC.
Titujt e elementeve strukturorë të WRC shkruhen në mes të rreshtit me shkronja të mëdha pa pikë, të pa nënvizuara, për shembull:
PREZANTIMI
Çdo element strukturor i WRC duhet të printohet nga një fletë (faqe) e re, duke përfshirë seksionet e pjesës kryesore.
Seksionet, nënseksionet, paragrafët dhe nënparagrafët duhet të numërohen me numra arabë dhe të shkruhen me një pikë paragrafi. Seksionet duhet të numërohen në mënyrë sekuenciale në të gjithë tekstin, me përjashtim të shtojcave. Shembull - 1, 2, 3, etj. Për shembull:
3 Studimi i efektivitetit të zgjidhjeve të marra
Nënseksionet numërohen brenda një seksioni. Numri i nënseksionit përfshin numrat e seksionit dhe nënseksionit të ndarë me një pikë. Për shembull, 1.1, 1.2, 1.3, etj.
Artikujt duhet të numërohen në mënyrë të njëpasnjëshme brenda çdo nënseksioni. Numri i artikullit përfshin numrin e seksionit dhe numrin serial të nënseksionit dhe artikullit, të ndarë me një pikë. Për shembull, 1.1.1, 1.1.2, etj.
Numri i nënparagrafit përfshin numrin e seksionit, nënseksionit, paragrafit dhe numrin serial të nënparagrafit, të ndarë me një pikë. Për shembull, 1.1.1.1, 1.1.1.2, etj. Nëse një seksion përbëhet nga një nënseksion, atëherë nënseksioni nuk është i numëruar. Nëse nënseksioni përbëhet nga një paragraf, atëherë paragrafi nuk është i numëruar. Nëse një paragraf përbëhet nga një nënparagraf, atëherë nënparagrafi nuk numërohet. Mos vendosni një pikë pas numrit të seksionit, nënseksionit, paragrafit dhe nënparagrafit në tekst.
Shembull direkt i PËRMBAJTJES
HYRJE5
1 Rishikim i detyrave dhe punimeve për temën kërkimore 7
2 Hartimi i modeleve të informacionit dhe zhvillimi i algoritmeve10
2.1 Zgjedhja e metodave dhe mjeteve të projektimit10
2.2 Dizajni i sistemit logjik11
2.3 Projektimi i sistemit fizik13
2.4 Dizajnimi i paraqitjes së ndërfaqes së përdoruesit15
2.5 Algoritmet e punës18
3 Teknologjia e zbatimit të softuerit të modeleve dhe algoritmeve të zhvilluara25
4.1 Zgjedhja e mjeteve të zbatimit25
4.2 Implementimi softuerik i ndërfaqes së përdoruesit të sistemit29
4.3 Garantimi i sigurisë operacionale dhe informative të sistemit të zhvilluar33
4.4 Arsyetimi dhe llogaritja ekonomike e kostove të zhvillimit të sistemit39
4 Studimi i efektivitetit të zgjidhjeve të marra43
4.1 Studimi i efektivitetit të zgjidhjeve të projektimit43
4.2 Studimi i efektivitetit të zgjidhjeve teknologjike48
4.3 Studimi i efektivitetit të algoritmeve të zhvilluara51
KONKLUZION55
REFERENCAT57
SHTOJCA59
P.1 Materiali grafik për shënimin shpjegues59
A.2 Listimi i nënprogramit për filtrimin dhe grupimin e të dhënave 61
P.3 Akti i Zbatimit të Zhvillimit 65
Seksionet dhe nënseksionet duhet të kenë tituj. Titujt duhet të pasqyrojnë qartë dhe në mënyrë të përmbledhur përmbajtjen e seksioneve, nënseksioneve.
Titujt e seksioneve, nënseksioneve duhet të shtypen me një paragraf të ndarë nga një shkronjë e madhe pa pikë në fund, pa nënvizuar. Nëse titulli përbëhet nga dy fjali, ato ndahen me një pikë. Nuk lejohet ndarja e fjalëve në tituj. Titulli i nënseksionit nuk duhet të jetë rreshti i fundit në faqe.
Çdo artikull në numërim duhet të paraprihet nga një vizë ndarëse. Nëse është e nevojshme, një referencë në tekstin e WRC për një nga elementët e numërimit, në vend të vizës, shkronjat e vogla vendosen në rendin e alfabetit rus, duke filluar me shkronjën a (me përjashtim të ё, z , й, o, h, ъ, ы, ь). Për detaje të mëtejshme të numërimit, është e nevojshme të përdoren numrat arabë, pas së cilës vendoset një kllapa dhe hyrja bëhet nga një pikë paragrafi.
Për shembull,
Faqezim
Faqet e WRC duhet të numërohen me numra arabë, duke ndjekur numërimin e vazhdueshëm në të gjithë tekstin. Numri i faqes vendoset në qendër të pjesës së poshtme të fletës pa pikë.
Faqja e titullit, detyra për WRC dhe përmbajtja përfshihen në numërimin e përgjithshëm të faqeve të WRC, numrat e faqeve nuk vendosen në to.
Ilustrimet dhe tabelat e vendosura në tekstin e WRC në fletë të veçanta përfshihen në numërimin e përgjithshëm të faqeve. Ilustrimet dhe tabelat në një fletë A3 (297×420) numërohen si një faqe.
Numërimi i faqeve të WRC dhe anekseve të përfshira në WRC duhet të jetë i vazhdueshëm.
Formulat
Formulat shtypen duke përdorur redaktuesin e formulës Microsoft Equation (pjesë e MS Office). Në këtë rast, "formula" nënkupton çdo sekuencë me të paktën dy karaktere që nuk është një fjalë (emër, shkurtim) në rusisht ose në ndonjë gjuhë tjetër.
Formulat numërohen në mënyrë strikte në mënyrë strikte (në rendin e shënimit shpjegues në tekst), në kllapa, me numra arabë, duke filluar nga 1. Numrat e formulave janë vendosur në mënyrë rigoroze në skajin e djathtë. Në këtë rast, numërohen vetëm ato formula që janë referuar në tekst. Formulat që nuk janë referuar në tekstin e artikullit nuk janë të numëruara.
Teksti i formulës është rreshtuar në anën e majtë në një distancë prej 1.25 centimetra nga skaji i majtë i tekstit (nga vija e kuqe), pavarësisht nëse kjo formulë është e numëruar apo jo:
Nëse formula nuk përshtatet në rresht, atëherë ajo transferohet në rreshtin tjetër pas shenjës "=" ose pas shenjave matematikore "+", "-", etj. Në këtë rast, rreshtimi i rreshtit të dytë të formula mbetet e njëjtë - 1.25 centimetra nga skaji i majtë i artikullit të tekstit, siç tregohet në shembullin me formulën (2):
| (2) |
Linjat bosh lihen midis tekstit dhe formulës vijuese, në formulat me shumë rreshta dhe midis formulës dhe tekstit vijues.
Një shpjegim i kuptimeve të simboleve dhe koeficientëve numerikë duhet të jepet drejtpërdrejt poshtë formulës, në të njëjtën sekuencë në të cilën ato janë dhënë në formulë. Vlera e çdo simboli dhe koeficienti numerik duhet të jepet në një vijë të re. Rreshti i parë i shpjegimit fillon me fjalën "ku", pa dy pika pas saj. Për shembull:
Reduktimi absolut i kostove të punës (DT):
DT \u003d T0 - T1,
ku T0 – kostot e punës për përpunimin e informacionit sipas rastit bazë;
T1 - kostot e punës për përpunimin e informacionit mbi opsionin e propozuar.
Për të shtypur variabla (shkronja), duhet të përdorni fontin Times, italic, jo bold (të vendosur në cilësimet e Ekuacionit të Microsoft): për shembull, t, V, s, U. Për të shtypur numrat, përdorni fontin Times, jo italic ( !), jo me shkronja të zeza (të vendosura në cilësimet e Ekuacionit të Microsoft): për shembull, 1, 2, 15. Madhësia e shkronjave për variablat dhe numrat është 14 pikë. Madhësitë e elementeve të tjerë të formulës (të vendosura në cilësimet e MicrosoftEquation):
Indeksi i madh - 8 pikë;
Indeksi i vogël - 6 pikë;
Simboli i madh (shenjat e shumës, integrale) - 18 pikë;
Simboli i vogël - 12 pikë.
Për të përcaktuar vektorët, matricat, është e pranueshme të përdoren elementë të tjerë të dizajnit stilistik të shkronjave, për shembull, shkronja jo të pjerrëta, të theksuara, font Arial, etj.
Për funksionet standarde (trigonometrike, logaritmike, etj.), si dhe për karakteret speciale (sup, inf, etj.), duhet të përdorni fontin Times, jo bold, jo italic (që korrespondon me cilësimet standarde të Ekuacionit të Microsoft), për shembull,
Ilustrime
Ilustrimet (vizatimet, grafikët, diagramet, diagramet) të vendosura në WRC duhet të jenë në përputhje me kërkesat e standardeve shtetërore të Sistemit të Unifikuar për Dokumentacionin e Projektimit. 9.9.2 Të gjitha ilustrimet në tekstin e WRC (grafikë, vizatime, diagrame, diagrame, etj.) vendosen menjëherë pas referencës së parë për to (ose në faqen tjetër) dhe shënohen me fjalën "Figura".
Teksti i shënimit shpjegues mund të përmbajë një sërë ilustrimeve, të cilat mund të jenë diagrame algoritmesh, struktura të qendrave kompjuterike, paraqitje të dokumenteve të prodhimit të përpunuara nga programi, grafika, etj. Të gjitha vizatimet janë hartuar në letër vizatimi (format A4) në fletë të veçanta. Titrat e figurave duhet të jenë gjithashtu me font standard.
Ilustrimet, me përjashtim të ilustrimeve të shtojcave, duhet të numërohen me numra arabë përmes numërimit. Lejohet numërimi i ilustrimeve brenda seksionit. Në këtë rast, numri i ilustrimit përbëhet nga numri i seksionit dhe numri i ilustrimit, të ndarë me një pikë. Për shembull - Figura 1.1. Kur i referohemi ilustrimeve, duhet të shkruhet "... në përputhje me Figurën 2" për numërimin e vazhdueshëm dhe "... në përputhje me Figurën 1.2" për numërimin brenda një seksioni.
Ilustrimet, nëse është e nevojshme, mund të kenë një emër dhe të dhëna shpjeguese (teksti i figurës). Fjala "Figura" dhe emri vendosen pas të dhënave shpjeguese dhe renditen si më poshtë: Figura 1 - Detajet e pajisjes.
Figura 1 - Titulli i figurës është i përqendruar, i printuar me një madhësi fonti jo të trashë prej 12 pikësh dhe, nëse është e nevojshme, mund të jetë
vazhdoi në rreshtin tjetër
Pas titullit të figurës, lihet një rresht bosh dhe teksti i artikullit vazhdon të shtypet.
tabelat
Çdo tabelë duhet të ketë një titull të numëruar dhe tematik (mundësisht).
Titulli i numërimit nevojitet për të thjeshtuar lidhjen e tabelës me tekstin; kur i referohemi testit, mjafton të tregohet: tab. 1. Tabelat numërohen në mënyrë sekuenciale sipas radhës së renditjes në tekstin e shënimit shpjegues, me numra arabë. Fjala "Tabela" (me shkronjë të madhe) dhe numri i saj shtypen me shkronja të pjerrëta dhe rreshtohen në të djathtë. Një rresht bosh lihet midis fjalës "Tabela" dhe paragrafit paraardhës. Nuk ka asnjë pikë pas numrit të tabelës.
Jo shumë kohë më parë, më ofruan të mësoja një kurs në bazat e teorisë së algoritmeve në një lice në Moskë. Sigurisht, u pajtova me kënaqësi. Të hënën, ishte ligjërata e parë në të cilën u përpoqa t'u shpjegoja djemve metodat për vlerësimin e kompleksitetit të algoritmeve. Mendoj se edhe disa lexues të Habrit mund ta kenë këtë informacion të dobishëm, ose të paktën interesant.
Ka disa mënyra për të matur kompleksitetin e një algoritmi. Programuesit zakonisht përqendrohen në shpejtësinë e algoritmit, por treguesit e tjerë nuk janë më pak të rëndësishëm - kërkesat për kujtesën, hapësirën e lirë të diskut. Përdorimi i një algoritmi të shpejtë nuk do të çojë në rezultatet e pritura nëse kërkon më shumë memorie sesa kompjuteri.
kujtesa apo koha
Shumë algoritme ofrojnë një zgjedhje midis madhësisë së kujtesës dhe shpejtësisë. Një problem mund të zgjidhet shpejt, duke përdorur një sasi të madhe memorie, ose më ngadalë, duke përdorur më pak hapësirë.Një shembull tipik në këtë rast është algoritmi për gjetjen e rrugës më të shkurtër. Duke paraqitur një hartë të qytetit si një rrjet, ju mund të shkruani një algoritëm për të përcaktuar distancën më të shkurtër midis çdo dy pikash në këtë rrjet. Në vend që t'i llogarisim këto distanca sa herë që na duhen, ne mund të nxjerrim distancat më të shkurtra midis të gjitha pikave dhe t'i ruajmë rezultatet në një tabelë. Kur duhet të gjejmë distancën më të shkurtër midis dy pikave të dhëna, thjesht mund të marrim distancën e përfunduar nga tabela.
Rezultati do të merret menjëherë, por do të kërkojë një sasi të madhe memorie. Një hartë e një qyteti të madh mund të përmbajë dhjetëra mijëra pika. Pastaj tabela e përshkruar më sipër duhet të përmbajë më shumë se 10 miliardë qeliza. ato. për të rritur shpejtësinë e algoritmit, është e nevojshme të përdorni 10 GB memorie shtesë.
Nga kjo varësi vjen ideja e kompleksitetit hapësirë-kohë. Me këtë qasje, algoritmi vlerësohet si për nga shpejtësia e ekzekutimit ashtu edhe për sa i përket memories së konsumuar.
Ne do të fokusohemi në kompleksitetin kohor, por, megjithatë, do të përcaktojmë patjetër sasinë e memories së konsumuar.
Rendit rezultatin
Kur krahasoni algoritme të ndryshme, është e rëndësishme të dini se si varet kompleksiteti i tyre nga sasia e të dhënave hyrëse. Për shembull, kur renditni me një metodë, përpunimi i një mijë numrave zgjat 1 s, dhe përpunimi i një milion numrave zgjat 10 sekonda, kur përdorni një algoritëm tjetër, mund të duhen 2 s. dhe 5 s. përkatësisht. Në kushte të tilla, është e pamundur të thuhet pa mëdyshje se cili algoritëm është më i mirë.Në përgjithësi, kompleksiteti i një algoritmi mund të vlerësohet sipas madhësisë. Algoritmi ka kompleksitet O(f(n)) nëse, me rritjen e dimensionit të të dhënave hyrëse N, koha e ekzekutimit të algoritmit rritet me të njëjtën shpejtësi si funksioni f(N). Merrni parasysh kodin që, duke pasur parasysh një matricë A, gjen elementin maksimal në çdo rresht.
për i:=1 deri në N bëj
fillojnë
max:=A;
për j:=1 deri në N bëj
fillojnë
nëse A>max atëherë
max:=A
fundi;
shkrimln(max);
fundi;
Në këtë algoritëm, ndryshorja i ndryshon nga 1 në N. Sa herë që ndryshon i, ndryshorja j gjithashtu ndryshon nga 1 në N. Gjatë secilit prej përsëritjeve N të ciklit të jashtëm, cikli i brendshëm gjithashtu ekzekutohet N herë. Numri i përgjithshëm i përsëritjeve të lakut të brendshëm është N*N. Kjo përcakton kompleksitetin e algoritmit O(N^2).
Gjatë vlerësimit të rendit të kompleksitetit të një algoritmi, është e nevojshme të përdoret vetëm pjesa që rritet më shpejt. Supozoni se cikli i punës përshkruhet me shprehjen N^3+N. Në këtë rast, kompleksiteti i tij do të jetë i barabartë me O(N^3). Marrja në konsideratë e pjesës me rritje të shpejtë të funksionit na lejon të vlerësojmë sjelljen e algoritmit kur rritet N. Për shembull, me N=100, diferenca midis N^3+N=1000100 dhe N=1000000 është vetëm 100, që është 0.01 %.
Kur llogaritni O, mund të injoroni faktorët konstant në shprehje. Një algoritëm me një hap pune prej 3N^3 konsiderohet si O(N^3). Kjo e bën më të dukshme varësinë e relacionit O(N) nga ndryshimi i madhësisë së detyrës.
Përkufizimi i vështirësisë
Pjesët më komplekse të një programi janë zakonisht unazat dhe thirrjet procedurale. Në shembullin e mëparshëm, i gjithë algoritmi është bërë me dy sythe.Nëse një procedurë thërret një tjetër, atëherë kompleksiteti i kësaj të fundit duhet të vlerësohet më me kujdes. Nëse një numër i caktuar udhëzimesh ekzekutohen në të (për shembull, printimi), atëherë kjo praktikisht nuk ka asnjë efekt në vlerësimin e kompleksitetit. Nëse procedura e thirrur merr hapa O(N), atëherë funksioni mund të komplikojë ndjeshëm algoritmin. Nëse procedura thirret brenda lakut, atëherë ndikimi mund të jetë shumë më i madh.
Si shembull, merrni parasysh dy procedura: I ngadalshëm me kompleksitet O(N^3) dhe i shpejtë me kompleksitet O(N^2).
procedura e ngadaltë;
var
i,j,k: numër i plotë;
fillojnë
për i:=1 deri në N bëj
për j:=1 deri në N bëj
për k:=1 deri në N bëj
(disa veprim)
fundi;
procedurë e shpejtë;
var
i,j: numër i plotë;
fillojnë
për i:=1 deri në N bëj
për j:=1 deri në N bëj
i ngadalshëm;
fundi;
procedura Të dyja;
fillojnë
të shpejtë;
fundi;
Nëse procedura Slow thirret në unazat e brendshme të procedurës Fast, atëherë shumëfishohen kompleksitetet e procedurave. Në këtë rast, kompleksiteti i algoritmit është O(N^2)*O(N^3)=O(N^5).
Nëse programi kryesor i thërret procedurat me radhë, atëherë kompleksiteti i tyre mblidhet: O(N^2)+O(N^3)=O(N^3). Fragmenti i mëposhtëm ka pikërisht këtë kompleksitet:
procedura e ngadaltë;
var
i,j,k: numër i plotë;
fillojnë
për i:=1 deri në N bëj
për j:=1 deri në N bëj
për k:=1 deri në N bëj
(disa veprim)
fundi;
procedurë e shpejtë;
var
i,j: numër i plotë;
fillojnë
për i:=1 deri në N bëj
për j:=1 deri në N bëj
(disa veprim)
fundi;
procedura Të dyja;
fillojnë
të shpejtë;
i ngadalshëm;
fundi;
Kompleksiteti i algoritmeve rekursive
rekursion i thjeshtë
Kujtoni se procedurat rekursive janë procedura që e quajnë veten. Kompleksiteti i tyre është i vështirë për t'u përcaktuar. Kompleksiteti i këtyre algoritmeve varet jo vetëm nga kompleksiteti i sytheve të brendshme, por edhe nga numri i përsëritjeve të rekursionit. Një procedurë rekursive mund të duket mjaft e thjeshtë, por mund të komplikojë seriozisht një program duke e thirrur veten disa herë.Konsideroni një zbatim rekurziv të llogaritjes faktoriale:
funksioni Faktorial(n: Fjalë): numër i plotë;
fillojnë
nëse n > 1 atëherë
Faktorial:=n*Faktorial(n-1)
tjetër
faktorial:=1;
fundi;
Kjo procedurë kryhet N herë, kështu që kompleksiteti llogaritës i këtij algoritmi është O(N).
Rekursion i shumëfishtë
Një algoritëm rekurziv që e quan veten disa herë quhet rekursion i shumëfishtë. Procedura të tilla janë shumë më të vështira për t'u analizuar, dhe ato gjithashtu mund ta bëjnë algoritmin shumë më kompleks.Konsideroni këtë procedurë:
procedura DoubleRecursive (N: numër i plotë);
fillojnë
nëse N>0 atëherë
fillojnë
DoubleRekursive (N-1);
DoubleRekursive (N-1);
fundi;
fundi;
Meqenëse procedura thirret dy herë, do të supozohej se koha e ekzekutimit të saj do të ishte O(2N)=O(N). Por në realitet situata është shumë më e ndërlikuar. Nëse e shqyrtoni me kujdes këtë algoritëm, bëhet e qartë se kompleksiteti i tij është O(2^(N+1)-1)=O(2^N). Duhet mbajtur mend gjithmonë se analiza e kompleksitetit të algoritmeve rekursive është një detyrë shumë jo e parëndësishme.
Kompleksiteti i vëllimit të algoritmeve rekursive
Për të gjithë algoritmet rekurzive, koncepti i kompleksitetit vëllimor është shumë i rëndësishëm. Çdo thirrje në procedurë kërkon një sasi të vogël memorie, por kjo sasi mund të rritet ndjeshëm gjatë thirrjeve rekursive. Për këtë arsye, është gjithmonë e nevojshme të kryhet të paktën një analizë sipërfaqësore e kompleksitetit vëllimor të procedurave rekursive.Rasti mesatar dhe më i keq
Vlerësimi i kompleksitetit të një algoritmi sipas rendit është një kufi i sipërm i kompleksitetit të algoritmeve. Nëse programi ka një renditje të madhe kompleksiteti, kjo nuk do të thotë aspak se algoritmi do të funksionojë për një kohë vërtet të gjatë. Në disa grupe të dhënash, algoritmi kërkon shumë më pak kohë për t'u përfunduar sesa do të sugjeronte kompleksiteti i tyre. Për shembull, merrni parasysh kodin që kërkon një element të caktuar në vektorin A.funksioni Locate(të dhënat: numër i plotë): numër i plotë;
var
i: numër i plotë;
fl: boolean;
fillojnë
fl:=false; i:=1;
ndërsa (jo fl) dhe (i<=N) do
fillojnë
nëse A[i]=të dhënat atëherë
fl:=vërtetë
tjetër
i:=i+1;
fundi;
nëse jo fl atëherë
i:=0;
Vendndodhja:=I;
fundi;
Nëse elementi i dëshiruar është në fund të listës, atëherë programi do të duhet të kryejë N hapa. Në këtë rast, kompleksiteti i algoritmit do të jetë O(N). Në këtë rast më të keq, koha e funksionimit të algoritmit do të jetë maksimale.
Nga ana tjetër, elementi që kërkoni mund të jetë në pozitën e parë në listë. Algoritmi duhet të bëjë vetëm një hap. Një rast i tillë quhet më i miri dhe kompleksiteti i tij mund të vlerësohet si O(1).
Të dyja këto raste nuk kanë gjasa. Ne jemi më të interesuar për variantin e pritur. Nëse elementet e listës fillimisht përzihen rastësisht, atëherë elementi i dëshiruar mund të shfaqet kudo në listë. Mesatarisht, do të duhen N/2 krahasime për të gjetur elementin e kërkuar. Pra, kompleksiteti i këtij algoritmi është mesatarisht O(N/2)=O(N).
Në këtë rast, kompleksiteti mesatar dhe i pritshëm janë të njëjta, por për shumë algoritme rasti më i keq është shumë i ndryshëm nga ai që pritet. Për shembull, algoritmi i renditjes së shpejtë në rastin më të keq ka kompleksitet O(N^2), ndërsa sjellja e pritur është O(N*log(N)), që është shumë më e shpejtë.
Funksionet e përbashkëta të vlerësimit të kompleksitetit
Tani do të listojmë disa nga funksionet që përdoren më shpesh për të llogaritur kompleksitetin. Funksionet janë renditur sipas renditjes së kompleksitetit në rritje. Sa më i lartë të jetë funksioni në këtë listë, aq më shpejt do të ekzekutohet algoritmi me këtë vlerësim.1. C është një konstante
2.log(log(N))
3 regjistër (N)
4. N^C, 0
6.N*log(N)
7. N^C, C>1
8. C^N, C>1
9. N!
Nëse duam të vlerësojmë kompleksitetin e një algoritmi, ekuacioni i kompleksitetit të të cilit përmban disa nga këto funksione, atëherë ekuacioni mund të reduktohet në funksionin më poshtë në tabelë. Për shembull, O(log(N)+N!)=O(N!).
Nëse algoritmi thirret rrallë dhe për sasi të vogla të dhënash, atëherë kompleksiteti i O (N ^ 2) mund të konsiderohet i pranueshëm, por nëse algoritmi funksionon në kohë reale, atëherë performanca O (N) nuk është gjithmonë e mjaftueshme.
Zakonisht algoritmet me kompleksitet N*log(N) punojnë me shpejtësi të mirë. Algoritmet me kompleksitet N^C mund të përdoren vetëm për vlera të vogla të C. Kompleksiteti llogaritës i algoritmeve rendi i të cilëve përcaktohet nga funksionet C^N dhe N! është shumë i madh, kështu që algoritme të tilla mund të përdoren vetëm për të përpunuar një sasi të vogël të dhënash.
Më në fund, këtu është një tabelë që tregon se për sa kohë një kompjuter që kryen një milion operacione në sekondë do të ekzekutojë disa algoritme të ngadalta.
