Osnovne strukture programiranja (vrste algoritama). Koncept algoritma. Programiranje Algoritmi programiranja

Da biste pisali aplikacije različitih nivoa složenosti, prvo morate steći znanje o tome kako se to radi. I poželjno je krenuti od same osnove algoritamizacije i programiranja. To je ono o čemu ćemo pričati u članku.

Ovo je naziv složene tehničke nauke, čiji je zadatak da sistematizuje metode stvaranja, obrade, prenošenja, skladištenja i reprodukcije podataka pomoću nje, a uključuje i principe rada i metode upravljanja koji pomažu u postizanju cilja. Sam izraz "računarska nauka" je francuskog porijekla i hibrid je riječi "informacija" i "automatizacija". Nastala je zbog razvoja i širenja novih tehnologija za prikupljanje, obradu i prijenos podataka, koje su bile povezane s njihovim fiksiranjem na mašinskim medijima. Ovo je porijeklo kompjuterske nauke. Osnove algoritamizacije i programiranja jedna su od najvažnijih oblasti ove nauke.

Šta ona radi?

Informatika se suočava sa sljedećim zadacima:

1. Hardverska i softverska podrška računarske tehnologije.
2. Sredstva za osiguranje međusobne interakcije čovjeka i kompjuterskih komponenti.

Termin "interfejs" se često koristi za označavanje tehničkog dijela. Ovdje imamo besplatan program. Osnove algoritmizacije i programiranja uvijek se koriste kada se stvaraju proizvodi masovne distribucije koji bi "trebali" osvojiti široku publiku. Uostalom, zbog popularnosti, razvijena aplikacija bi trebala raditi i izgledati optimalno.

Prezentacija algoritama

Mogu se napisati na značajan broj načina. Najpopularnije su sljedeće:

1. Opis verbalne formule. Podrazumijeva postavljanje teksta i specifičnih formula koje će objasniti karakteristike interakcije u svim pojedinačnim slučajevima.
2. Blok dijagram. Podrazumijeva se prisustvo grafičkih simbola koji omogućavaju razumijevanje karakteristika interakcije programa unutar samog sebe i sa drugim aplikacijama ili hardverskom komponentom računara. Svaki od njih može biti odgovoran za zasebnu funkciju, proceduru ili formulu.
3. Podrazumijeva kreiranje posebnih metoda opisa za konkretne slučajeve, koje pokazuju karakteristike i redoslijed zadataka.
4. Operatorske šeme. To podrazumijeva kreiranje prototipa – on će pokazati interakciju na osnovu putanja kroz koje će proći pojedinačni operandi.

Pseudocode. Nacrt okosnice programa.

Pisanje algoritma

Kako započeti kreiranje prototipa programa, funkcije ili procedure? Da biste to učinili, dovoljno je koristiti sljedeće opće preporuke:

1. Svaki algoritam treba da ima svoje ime, koje objašnjava njegovo značenje.
2. Obavezno vodite računa o prisutnosti početka i kraja.
3. Ulazni i izlazni podaci moraju biti opisani.
4. Treba specificirati naredbe uz pomoć kojih će se izvršavati određene radnje nad određenim informacijama.

Metode snimanja

Može postojati čak pet prikaza algoritma. Ali postoje samo dva načina za pisanje:

1. Formalno verbalno. Karakterizira ga činjenica da je opis napravljen uglavnom pomoću formula i riječi. Sadržaj, kao i redoslijed izvršavanja koraka algoritma u ovom slučaju, snimljen je prirodnim stručnim jezikom u proizvoljnom obliku.
2. Graphic. Najčešći. Za to se koriste blok simboli ili šeme algoritama. Veza između njih prikazana je pomoću posebnih linija.

Razvijamo strukturu programa

Postoje tri glavne vrste:

1. Linearno. Sa ovom strukturom, sve se radnje izvode uzastopno po prioritetu i samo jednom. Shema izgleda kao niz blokova, raspoređenih odozgo prema dolje, ovisno o redoslijedu kojim se izvode. Rezultirajući primarni i srednji podaci ne mogu utjecati na smjer računskog procesa.
2. Grananje. Našao je široku primjenu u praksi, u rješavanju složenih problema. Dakle, ako je potrebno uzeti u obzir početne uslove ili međurezultate, onda se potrebni proračuni izvode u skladu s njima, a smjer proračunskog procesa može se mijenjati ovisno o dobivenom rezultatu.

Ciklična. Kako bi vam olakšali rad s mnogim zadacima, ima smisla ponoviti neke dijelove programskog koda više puta. Kako se ne bi propisivalo koliko puta i šta treba uraditi, koristi se ciklična struktura. Obezbeđuje niz naredbi koje će se ponavljati dok se ne ispuni dati uslov. Upotreba petlji vam omogućava da značajno smanjite složenost pisanja programa.

Programiranje

Bitno je na kojem će se programu kreirati. Treba napomenuti da su mnogi od njih "skrojeni" za specifične uslove rada (na primjer, u pretraživaču). Općenito, programski jezici se dijele u dvije grupe:

1. Funkcionalni.
2. Operater:

Nije proceduralna;

proceduralni.

Možete li pogoditi koji se najčešće koriste? Operatorsko-proceduralno - to je odgovor. Mogu biti mašinski orijentisani ili nezavisni. Prvi uključuju asemblere, autokodove, simboličko kodiranje. Nezavisni se dijele na osnovu njihove orijentacije:

• proceduralni;
• problematično;
• objekt.

Svaki od njih ima svoj obim. Ali za pisanje programa (korisne aplikacije ili igre) najčešće se koriste objektno orijentirani jezici. Naravno, možete koristiti i druge, ali činjenica je da su oni najrazvijeniji za kreiranje finalnih proizvoda široke potrošnje. Da, i ako još nemate tačnu viziju odakle da počnete, predlažem da obratite pažnju na osnove algoritamizacije i objektno orijentisanog programiranja. Sada je ovo vrlo popularno područje u kojem možete pronaći mnogo edukativnog materijala. Općenito, osnove algoritamizacije i programskih jezika sada su potrebne zbog činjenice da nedostaje kvalificiranih programera, a njihov značaj će samo rasti u budućnosti.

Zaključak

Prilikom rada s algoritmima (a potom i s programima) treba težiti promišljanju svih detalja do najsitnijih. Nakon toga, identifikacija svakog nerazvijenog dijela koda samo će dovesti do dodatnog rada, povećanja troškova razvoja i vremena zadatka. Pažljivo planiranje i razrada svih nijansi značajno će uštedjeti vrijeme, trud i novac. Pa, sada mogu reći da nakon čitanja ovog članka imate ideju o osnovama algoritamizacije i programiranja. Ostaje samo primijeniti ovo znanje. Ako postoji želja da se detaljnije prouči tema, mogu savjetovati knjigu "Osnove algoritmizacije i programiranja" (Semakin, Shestakov) 2012.

Koncept algoritma je jedan od osnovnih koncepata kompjuterske nauke. Razmotrite osnovne koncepte povezane s konceptom algoritma.

Kada je u pitanju algoritam, uvek se podrazumeva postojanje nekog izvršioca kome je algoritam namenjen.

Izvršitelj - osoba ili automat (na primjer, kompjuter) koji može izvršiti određeni konačan skup radnji.

recept - nalog za izvođenje radnji iz navedenog konačnog skupa.

Sistem recepta - skup dozvoljenih naloga.

Program - konačni redoslijed uputstava sa naznakom redoslijeda njihove implementacije.

U slučaju kada je izvršilac računar, poziva se recept tim , a sistem naručivanja se zove kompjuterski komandni sistem . Različiti računari, u zavisnosti od svog uređaja, mogu imati različite komandne sisteme.

Programiranje - sastavljanje niza naredbi, koje su neophodne za rješavanje problema.

Izradi programa prethodi izrada algoritma.

Algoritam - ovo je tačna i razumljiva instrukcija izvođaču da izvrši konačan niz radnji u cilju postizanja određenog cilja ili rješavanja postavljenog zadatka.

Svaki algoritam ima sljedeća svojstva:

• 1. diskretnost. Izvršenje algoritma podijeljeno je na niz elementarnih radnji - koraka. Svaku radnju izvršilac mora dovršiti prije nego što može preći na sljedeću radnju. Za izvođenje svake pojedinačne radnje, izvođaču se u zapisu algoritma propisuje posebna instrukcija koja se zove komanda.
• 2. Tačnost ili determinizam. Zapis algoritma treba da bude takav da, nakon izvršenja sledeće komande, izvođač tačno zna koja naredba treba da se izvrši sledeća.
• 3. Jasnoća. Svaki algoritam je izgrađen sa određenim izvršiocem na umu, koji mora biti u stanju da izvrši svaku naredbu algoritma u strogom skladu sa njegovom svrhom.
• 4. Efikasnost. Sa tačnim izvršavanjem svih propisa algoritma, proces se mora završiti u konačnom broju koraka, a istovremeno se mora dobiti neki odgovor na zadatak. Jedno od mogućih rješenja može biti utvrđivanje činjenice da problem nema rješenja
• 5. Masovni karakter. koristeći isti algoritam, možete riješiti istu vrstu problema i to više puta. Svojstvo masovnog karaktera značajno povećava praktičnu vrijednost algoritama.

Velika vrijednost algoritama leži u činjenici da izvođač možda ne ulazi u značenje onoga što radi, a da pri tome dobije više znanja nego od izvođača.

Najjednostavnije operacije na koje se razlaže proces rješavanja problema mogu se realizovati automatskim uređajem posebno dizajniranim da izvršava pojedinačne komande algoritma u određenom nizu. Ako je moguće dobiti algoritam za rješavanje problema, postaje moguće napraviti mašinu koja bi automatizirala njegovo rješavanje.

Svaki algoritam pretpostavlja prisustvo nekih početnih podataka. Na primjer, za medicinski recept (algoritam) početni podaci su lijekovi, a rezultat je bočica s gotovim lijekom. Za algoritam sabiranja, ulazni podaci su par pojmova, a rezultat je njihov zbir. Za svaki algoritam postoji klasa objekata koji su prihvatljivi kao ulazni podaci. Ponekad su početni podaci materijalni objekti, a ponekad brojevi.

Algoritam je pravilo, stoga mora biti formulisan na nekom jeziku. Ulazni podaci i željeni rezultati također moraju biti opisani na nekom jeziku, moguće drugačijem od jezika na kojem je algoritam opisan.

Dakle, svaki algoritam je povezan sa dva jezika: u jednom se formuliše sam, rečenice drugog su važeće varijante početnih podataka za njega.

Razvoj algoritma za rješavanje problema naziva se algoritmizacija. U procesu algoritamizacije zadatak se svodi na konstruisanje niza koraka raspoređenih određenim redosledom.

Ne postoji jasna razlika između algoritama i programa. Program se obično naziva algoritam za rješavanje problema, dizajniran da ga izvrši kompjuter i napisan korištenjem rečenica korištenog programskog jezika.

Algoritamska struktura je standardni način povezivanja pojedinačnih koraka algoritma za izvođenje tipičnog niza radnji.

U teoriji algoritama je dokazano da se svaki algoritam može predstaviti kao kombinacija tri algoritamske strukture: sekvence, vilice i ciklusa.

To je sekvencijalno izvršavanje radnji (slika 12).

Rice. 12.

Koristi se u slučaju kada je, u zavisnosti od istinitosti nekog logičkog uslova, potrebno izvršiti jednu ili drugu radnju (slika 13).

Rice. 13.

Radnje 1 i 2 mogu zauzvrat uključivati ​​druge algoritamske strukture.

Ciklus . Koristi se kada neku radnju treba izvršiti nekoliko puta. Postoje dvije vrste ciklusa.

Koristi se kada se neke operacije moraju ponavljati sve dok određeni uslov ne postane lažan (slika 14).

Rice. 14. Ciklus Prije.

Pod početnim dodjeljivanjem podrazumijevamo operacije dodjele početnih vrijednosti varijablama koje se koriste u petlji. Redoslijed radnji koje se ponavljaju naziva se tijelom ciklusa.

Koristi se kada se neke operacije moraju ponavljati dok se određeni uslov ne ispuni (slika 15).

Rice. 15. Ciklus ćao.

Predmet upoznaje studente sa osnovnim strukturama podataka i algoritmima čije je poznavanje neophodno za efikasno rešavanje različitih programskih problema. Autori kursa se bave traženjem i obukom studenata i školaraca nadarenih za oblast računarstva i programiranja. Pod njihovim vodstvom, studentski timovi su više puta postali prvaci Rusije u programiranju, svjetski i evropski prvaci.

O kursu

Predmet je posvećen proučavanju osnovnih algoritama i struktura podataka čije je poznavanje neophodno za efikasno rešavanje različitih programskih problema. Razmatraju se različiti algoritmi za sortiranje, linearne strukture podataka kao što su redovi i liste, algoritmi i strukture podataka za efikasno pretraživanje i skladištenje informacija – balansirana stabla pretrage i hešovi, kao i algoritmi za pretraživanje podstringa.

Svrha predmeta je sticanje osnovnih znanja o osnovnim algoritmima i strukturama podataka koji se koriste za pohranjivanje i pronalaženje informacija.Kurs koristi automatski sistem za testiranje programa koji omogućava objektivnu procjenu ispravnosti programskih zadataka.

Po završetku kursa studenti će steći veštine analize i implementacije osnovnih programskih algoritama i struktura podataka, kao i projektovanja i razvoja alata za implementaciju primenjenih informacionih tehnologija.

Polaganje predmeta „Algoritmi programiranja i strukture podataka“ značajno će povećati produktivnost i konkurentnost studenata u razvoju softvera.

Format

Kurs obuhvata video predavanja, ankete zasnovane na materijalima za predavanja i praktične zadatke programiranja koji uključuju samoimplementaciju algoritama i struktura podataka koji se izučavaju na kursu na jednom od predloženih savremenih programskih jezika. Kurs traje deset sedmica. Prosečno nedeljno opterećenje po učeniku je 14 sati. Ukupna složenost predmeta je četiri kreditne jedinice.

Informativni resursi

Za završetak kursa i ispunjavanje svih predloženih zadataka dovoljan je video materijal za predavanja. Međutim, za produbljivanje znanja o predmetu koji se proučava, možete koristiti sljedeće dodatne izvore:

1. Kormen T., Leyzerson Ch., Rivest R., Stein K. Algoritmi: konstrukcija i analiza. - M.: Williams, 2012.
2. Aho A., Hopcroft D., Ulman D. Strukture podataka i algoritmi. - M. : Williams, 2007.
3. Online beleške sa predavanja o diskretnoj matematici, algoritmima i strukturama podataka održane na Katedri za računarske tehnologije Univerziteta ITMO.

Zahtjevi

Da biste uspješno savladali kurs, potrebno je poznavati osnove diskretne matematike, sposobnost pisanja programa srednje veličine u objektno orijentiranom programskom jeziku.

Za kurs je potreban bilo koji javni kompajler jednog od sljedećih programskih jezika:

• Java: verzija 8 (link za preuzimanje na Oracle stranici)
• C, C++: MinGW verzija 5.1 (za Linux možete koristiti GCC slične verzije), kao i Microsoft Visual Studio C++ 2013 (možete preuzeti Visual Studio Express).
• C#: Microsoft Visual Studio C# 2013 (možete preuzeti Visual Studio Express).
• Python: verzija 3.5 (link za preuzimanje na python.org)
• Scala: verzija 2.11 (link za preuzimanje sa scala-lang.org)
• Kotlin: verzija 1.0 (linkovi na uputstva za instalaciju kompajlera, dodatke u IntelliJ IDEA i Eclipse).

Program kursa

Kurs pokriva sljedeće teme:

1. Procjena vremena rada algoritama
2. Algoritmi za sortiranje na osnovu poređenja (sortiranje spajanjem, brzo sortiranje, donja granica za vrijeme algoritama sortiranja)
3. Algoritmi za linearno sortiranje (razvrstavanje brojanjem, numeričko sortiranje, džepno sortiranje)
4. Elementarne strukture podataka (stog, red, povezane liste)
5. Algoritmi bazirani na binarnoj hrpi (razvrstavanje hrpe, prioritetni red)
6. Uvod u algoritme pretraživanja (binarna pretraga u sortiranom nizu, binarno stablo pretraživanja)
7. Balansirana stabla pretraživanja (pregled uravnoteženih stabala, AVL stabla, Splay stabla)
8. Haširanje (heš tabele sa zatvorenim i otvorenim adresiranjem)
9. Uvod u pretragu podniza (najjednostavniji algoritam za pretraživanje podniza, Rabin-Karp algoritam)
10. Pretraga podniza (Knuth-Morris-Pratt algoritam, Z-funkcija, Boyer-Moore algoritam)

Svaka tema uključuje učenje u trajanju od jedne sedmice. Svake sedmice se izdaju programski zadaci koji uključuju samostalnu implementaciju algoritama i struktura podataka koji se proučavaju na predmetu.

Kurs ima dvije vrste rokova (rokovi za završetak aktivnosti ocjenjivanja):
– meki rok, u kojem je potrebno završiti sve aktivnosti evaluacije tekuće sedmice prije njenog završetka;
– tvrdi rok, u kojem se izdvajaju dodatne dvije sedmice za provođenje aktivnosti evaluacije nakon mekog roka, nakon čega se zatvara pristup relevantnim aktivnostima.

Ishodi učenja

• Sposobnost analize i implementacije osnovnih programskih algoritama i struktura podataka
• Vještine projektovanja i razvoja sredstava za implementaciju primijenjenih informacionih tehnologija
• Vještine razvoja algoritama za provođenje eksperimentalnih istraživanja u oblasti informatike

Formirane kompetencije

• 09.03.02 Informacioni sistemi i tehnologije
  1. Sposobnost projektovanja osnovnih i primenjenih informacionih tehnologija (PC-11)
  2. Sposobnost razvoja sredstava za implementaciju informacionih tehnologija (algoritamski) (PC-12)
  3. Spremnost da učestvuje u formulisanju i sprovođenju eksperimentalnih studija (PC-23)

1. Koncept algoritma

Algoritam - ovo je tačna i razumljiva instrukcija izvođaču da izvrši niz radnji usmjerenih na rješavanje zadatka. ime " algoritam" dolazi od latinskog oblika imena srednjoazijskog matematičara al-Khwarizmija - Algorithmi.

Izvođač algoritma- ovo je neki apstraktni ili stvarni (tehnički, biološki ili biotehnički) sistem koji je sposoban da izvrši radnje propisane algoritmom. Izvođača karakteriziraju: okruženje, elementarne radnje, sistem komandi, kvarovi. srijeda(ili okolina) je "stanište" izvođača . Svaki izvršilac može izvršiti samo naredbe sa neke strogo definisane liste - komandni sistemi izvođač. Za svaku naredbu moraju biti specificirani uvjeti primjenjivosti (u kojim stanjima okruženja se naredba može izvršiti) i moraju se opisati rezultati izvršenja naredbe. Nakon pozivanja komande, izvršilac izvršava odgovarajuću elementarna akcija. Neuspjesi greške izvršitelja se javljaju ako se naredba pozove kada je stanje okruženja za nju nevažeće.

U računarstvu, univerzalni izvršilac algoritama je računar.

2. Svojstva algoritama

Može se razlikovati sljedeće osnovna svojstva algoritama:

1) Jasnoća za izvođača - tj. Izvršilac algoritma mora znati kako da ga izvrši.

2) diskretnost(diskontinuitet, razdvajanje) - tj. algoritam treba da predstavlja proces rješavanja problema kao sekvencijalno izvršavanje jednostavnih ili prethodno definiranih koraka.

3) Sigurnost- tj. svako pravilo algoritma treba da bude jasno, nedvosmisleno i da ne ostavlja prostora za odstupanja.

4) Efikasnost(ili ud). Ovo svojstvo je da algoritam mora dovesti do rješenja problema u konačnom broju koraka.

5) masovni karakter- znači da je algoritam za rješavanje problema razvijen u opštem obliku, tj. trebalo bi da bude primenljivo na određenu klasu problema koji se razlikuju samo u početnim podacima. U ovom slučaju, početni podaci se mogu odabrati iz određene oblasti, koja se zove opseg algoritma.

3. Oblici predstavljanja algoritama

Najčešći oblike predstavljanja algoritama su: verbalni, grafički, pseudokod i softver.

1) Oblik riječi zapis je opis uzastopnih faza obrade podataka na prirodnom jeziku (na primjer, na ruskom).

Primjer. Zapišite algoritam za pronalaženje najvećeg zajedničkog djelitelja (GCD) dva prirodna broja.

Algoritam: 1) postaviti dva broja; 2) ako su brojevi jednaki, uzmite bilo koji od njih kao odgovor i prestanite, u suprotnom nastavite sa algoritamom; 3) odrediti veći od brojeva; 4) veći od brojeva zameniti razlikom između većeg i manjeg broja; 5) ponovite algoritam iz koraka 2.

Opisani algoritam je primjenjiv na sve prirodne brojeve i trebao bi dovesti do rješenja problema u konačnom broju koraka.

Verbalna metoda nije u širokoj upotrebi, jer su takvi opisi:

a) nisu striktno formalizovani;

b) pate od opširnosti zapisa;

c) dozvoljava dvosmisleno tumačenje pojedinačnih propisa.

2) Grafički način predstavljanje algoritama je kompaktnije i vizuelnije u odnosu na verbalno. U grafičkom izvođenju, algoritam je prikazan kao niz međusobno povezanih funkcionalnih blokova, od kojih svaki odgovara izvršenju jedne od akcija. Takav grafički prikaz naziva se dijagram algoritma ili blok dijagram . U dijagramu toka, svaka vrsta radnje odgovara geometrijskoj figuri koja se zove simbol bloka. Povezivanje simbola bloka prelazne linije koji određuju redosled kojim se radnje izvode.

Više o ovome u nastavku...

3) Pseudocode je sistem notacije i pravila dizajniran za jednoobrazan zapis algoritama. Zauzima srednju poziciju između prirodnih i formalnih jezika.

S jedne strane, blizak je običnom prirodnom jeziku, tako da se algoritmi mogu pisati i čitati na njemu kao običan tekst. S druge strane, pseudokod koristi službene riječi i matematički simbolizam, koji približava notaciju algoritma općeprihvaćenoj matematičkoj notaciji. Funkcionalne riječi su podebljane u štampanom tekstu, a podvučene u rukom pisanom tekstu kako bi se mogle razlikovati od ostatka teksta.

Primjer. 1) postaviti dva broja x i y; 2) AKO x=y ONDA GCD=x i KRAJ; 3) AKO x>y, ONDA x=x-y, ELSE y=y-x; 4) Idite na tačku 2.

4) Programski obrazac je tekst programa napisan na različitim programskim jezicima.

Ispod su grafički simboli na blok dijagramima.

U dijagramima, SERIES označava jednog ili više operatora; CONDITION je logički izraz (LP) (ako je njegova vrijednost TRUE, prijelaz se odvija duž grane DA, u suprotnom - duž NE). Na dijagramu ciklusa sa parametrom koriste se sljedeće oznake: PC - parametar ciklusa, NC - početna vrijednost parametra ciklusa, KZ - konačna vrijednost parametra ciklusa, Š - korak promjene parametra ciklusa.

Početak i kraj algoritma na blok dijagramima označeni su ovalom, ulazne i izlazne varijable su zapisane u paralelogramu.

). Razvoj programa pomoću ovakvog programskog sistema sastoji se od dve faze: 1) kreiranja elemenata grafičkog interfejsa programa u vizuelnom režimu; 2) razvoj programskog koda. Ovaj pristup uvelike olakšava kreiranje programa, budući da je ručni razvoj grafičkog interfejsa (na proceduralnim jezicima) složen i dugotrajan proces.

Prvi korak ka razumijevanju važnosti proučavanja i poznavanja algoritama je definiranje tačno šta se podrazumijeva pod algoritmom. Algoritam u programiranju je jasan i precizan redosled radnji, napisan u programskom jeziku. Prema popularnoj knjizi Algoritmi: konstrukcija i analiza (Kormen, Leyzerson, Rivest, Stein) "algoritam (algoritam) je bilo koja dobro definirana računska procedura, čiji se ulaz (ulaz) hrani nekim vrijednost ili skup vrijednosti, a rezultat toga je izlazna vrijednost ili skup vrijednosti". Drugim riječima, algoritmi su poput mapa puta za postizanje dobro definiranog cilja. Kod za izračunavanje termina Fibonačijevog niza je implementacija specifičnog algoritma. Čak i jednostavna funkcija zbrajanja dva broja je algoritam, iako jednostavan.

Da biste kreirali algoritam (program), morate znati:

kompletan skup početnih podataka zadatka (početno stanje objekta);

svrha kreiranja algoritma (konačno stanje objekta);

sistem komandi izvršioca (tj. skup komandi koje izvršitelj razume i može da izvrši).

Rezultirajući algoritam (program) mora imati sljedeći skup svojstava:

diskretnost(algoritam je podijeljen u zasebne korake - komande);

jedinstvenost(svaka komanda određuje jedinu moguću radnju izvođača);

razumljivost(sve komande algoritma su uključene u komandni sistem izvršioca);

efektivnost(izvođač mora riješiti problem u konačnom broju koraka).

Većina algoritama također ima svojstvo masovni karakter(koristeći isti algoritam, možete riješiti mnoge probleme istog tipa).

Neki algoritmi, na primjer, za izračunavanje Fibonačijevog niza su intuitivni i pripadaju urođenim vještinama logičkog mišljenja i rješavanja problema. Međutim, većina nas će također imati koristi od učenja složenih algoritama kako bismo ih mogli koristiti kao gradivne blokove u budućnosti za efikasnije rješavanje logičkih problema. Zapravo, neko bi mogao biti iznenađen kada sazna koliko složenih algoritama ljudi koriste kada provjeravaju e-poštu ili slušaju muziku. Ovaj članak predstavlja neke osnovne ideje analize algoritama s praktičnim primjerima koji ilustruju važnost učenja algoritama.

Programski jezik je skup pravila za pisanje algoritamskih struktura i podataka.

Analiza vremena izvršenja algoritma

Jedan od najvažnijih aspekata algoritma je njegova brzina. Često je lako smisliti algoritam koji rješava problem, ali ako je algoritam prespor, onda se vraća na reviziju. Budući da tačna brzina algoritma ovisi o tome gdje se algoritam izvodi, kao io detaljima implementacije, kompjuterski naučnici obično govore o vremenu izvršenja u odnosu na ulazne podatke. Na primjer, ako se ulaz sastoji od N cijelih brojeva, tada algoritam može imati vrijeme rada proporcionalno N 2 , koje je predstavljeno kao O(N 2 ). To znači da ako pokrenete implementaciju algoritma na računaru sa ulazom veličine N, biće potrebno C*N 2 sekunde, gde je C neka konstanta koja se ne menja sa veličinom ulaza.

Međutim, vrijeme izvršenja mnogih složenih algoritama ovisi ne samo o veličini ulaznih podataka, već i o mnogim drugim faktorima. Na primjer, algoritam za sortiranje skupa cijelih brojeva može raditi mnogo brže ako je skup već sortiran. Uobičajeno je da se govori o najgorem učinku i o prosečnom učinku slučaja. Vrijeme izvršenja u najgorem slučaju je maksimalno vrijeme koje algoritam može pokrenuti na "najgorem" od svih mogućih ulaza. Prosječni slučaj izvršenja je prosječno vrijeme rada algoritma na svim mogućim ulazima. Od ova dva tipa vremena izvršavanja, najgori slučaj je najlakši za razmišljanje i stoga se češće koristi kao mjerilo za dati algoritam. Proces određivanja vremena rada algoritma u najgorem i prosečnom slučaju može biti prilično komplikovan, jer obično nije moguće pokrenuti algoritam za sve moguće ulaze.

Gore je napomenuto da se isti algoritam može napisati na različite načine. Možete napisati algoritam prirodni jezik. U ovom obliku koristimo recepte, upute itd. Za pisanje algoritama namijenjenih formalnim izvršiocima, specijal programski jezici. Bilo koji algoritam se može opisati grafički u obliku blok dijagrama. Za to je razvijen poseban sistem notacije:

Dajemo primjer opisa algoritma za zbrajanje dvije veličine u obliku blok dijagrama:

Ovakav način opisivanja algoritma je najjasniji i najrazumljiviji za osobu. Stoga se formalni izvršni algoritmi obično prvo razvijaju u obliku blok dijagrama, a tek onda se kreira program na jednom od .

Sortiranje

Sortiranje je dobar primjer algoritma koji programeri često koriste. Najlakši način da sortirate grupu elemenata je da započnete uklanjanjem najmanjeg elementa iz grupe i stavite ga na prvo mjesto. Zatim se uklanja drugi najveći element i postavlja drugi, i tako dalje. Nažalost, vrijeme rada ovog algoritma je O(N 2), što znači da će biti potrebno vrijeme proporcionalno broju elemenata na kvadratu. Kada bismo morali da sortiramo milijarde elemenata, onda bi ovaj algoritam zahtevao 10 18 operacija. Ako pretpostavimo da tipični desktop računari rade oko 10 9 operacija u sekundi, biće potrebne godine da se završi sortiranje ove milijarde stavki.

Na sreću, postoji niz boljih algoritama, kao što su brzo sortiranje (quicksort), sortiranje u hrpi (heapsort) i sortiranje spajanjem (mergesort). Ovi algoritmi imaju vrijeme rada O(N * Log(N)). Dakle, broj operacija potrebnih za sortiranje milijardi artikala sveden je na razumne granice da čak i najjeftiniji desktop računar može sortirati. Umjesto milijardi operacija na kvadrat (10 18), ovi algoritmi zahtijevaju samo 10 milijardi operacija (10 10), tj. 100 miliona puta brže.

Najkraći put

Algoritmi za pronalaženje najkraćeg puta od jedne do druge tačke istražuju se godinama. Primjera primijenjene primjene ovih algoritama ima dosta, međutim, radi jednostavnosti prezentacije, pridržavat ćemo se sljedeće tvrdnje: potrebno je pronaći najkraći put od tačke A do tačke B u gradu sa nekoliko ulica i raskrsnica. Postoji mnogo različitih algoritama za rješavanje ovog problema, svi sa svojim prednostima i nedostacima. Prije nego što se udubimo u njih, pogledajmo vrijeme izvršenja jednostavnog brutalnog algoritma. Ako algoritam uzme u obzir svaki mogući put od A do B (koji ne formira cikluse), malo je vjerovatno da će završiti u našem životu, čak i ako su A i B u malom gradu. Vrijeme rada ovog algoritma je eksponencijalno, što se označava kao O(C N) za neki C. Čak i za male vrijednosti C, C N postaje astronomski broj kada N poprimi umjereno veliku vrijednost.

Jedan od najbržih algoritama za rješavanje ovog problema ima vrijeme rada O(E+V*Log(V)), gdje je E broj segmenata puta, a V broj raskrsnica. Algoritmu će trebati oko 2 sekunde da pronađe najkraću stazu u gradu od 10.000 raskrsnica i 20.000 segmenata puta (obično postoje oko 2 segmenta puta po raskrsnici). Ovaj algoritam je poznat kao Dijkstraov algoritam i prilično je složen i zahtijeva korištenje strukture podataka prioritetnog reda. Međutim, u nekim slučajevima je čak i ovo vrijeme izvršavanja presporo (uzmite na primjer pronalaženje najkraćeg puta od New Yorka do San Francisca - u SAD-u postoje milioni raskrsnica), u takvim slučajevima programeri pokušavaju poboljšati vrijeme izvršavanja uz pomoć takozvane heuristike. Heuristika je aproksimacija nečega što je relevantno za problem. U problemu najkraće putanje, na primjer, može biti korisno znati koliko je tačka udaljena od odredišta. Znajući ovo, moguće je razviti brži algoritam (na primjer, A* algoritam pretraživanja u nekim slučajevima radi mnogo brže od Dijkstrinog algoritma). Ovaj pristup ne poboljšava uvijek vrijeme izvršenja algoritma u najgorem slučaju, ali u većini stvarnih aplikacija algoritam počinje da radi brže.

Približni algoritmi

Ponekad je čak i najnapredniji algoritam sa najnaprednijom heuristikom prespor na najbržem računaru. U takvim slučajevima potrebno je smanjiti točnost konačnog rezultata. Umjesto da pokušavate dobiti najkraći put, možete se ograničiti na put koji je, na primjer, 10% veći od najkraćeg puta.

U stvari, postoji dosta važnih problema za koje trenutno poznati algoritmi daju optimalni rezultat presporo. Najpoznatija grupa ovih problema naziva se NP (nedeterministički polinom). Ako se problem naziva NP-kompletan ili NP-tvrd, to znači da niko ne zna dovoljno dobar način da dobije optimalno rješenje. Također, ako se razvije efikasan algoritam za rješavanje jednog NP-teškog problema, onda se taj algoritam može primijeniti na sve NP-teške probleme.

Dobar primjer NP teškog problema je problem trgovačkog putnika. Prodavac želi posjetiti N gradova i zna koliko je vremena potrebno da stigne iz jednog grada u drugi. Pitanje je koliko brzo može posjetiti sve gradove? Najbrži poznati algoritam za rješavanje ovog problema je prespor – a mnogi vjeruju da će uvijek biti – pa programeri traže algoritme koji su dovoljno brzi da daju dobro rješenje, ali često nisu optimalni.

Slučajni algoritmi

Drugi pristup koji se koristi za rješavanje nekih problema je da se algoritam učini slučajnim. Ovaj pristup ne poboljšava vrijeme algoritma u najgorem slučaju, ali često dobro funkcionira u srednjem slučaju. Algoritam brzog sortiranja dobar je primjer upotrebe randomizacije. U najgorem slučaju, algoritam brzog sortiranja sortira grupu elemenata u O(N 2), gdje je N broj elemenata. Ako se u ovom algoritmu koristi randomizacija, tada šanse najgoreg slučaja postaju marginalno male, a u prosjeku algoritam brzog sortiranja radi u O(N*Log(N)) vremenu. Drugi algoritmi garantuju O(N*Log(N)) čak iu najgorem slučaju, ali su sporiji u prosečnom slučaju. Dok oba algoritma imaju vremena rada proporcionalna N*Log(N), algoritam brzog sortiranja ima manji konstantni faktor - tj. zahtijeva C*N*Log(N) dok drugi algoritmi zahtijevaju više od 2*C*N*Log(N) operacije.

Drugi algoritam koji koristi nasumične brojeve traži medijanu grupe brojeva i ima prosječno vrijeme rada O(N). Ovo je mnogo brže od algoritma koji sortira brojeve i bira prosjek i radi u O(N*Log(N)). Postoje deterministički algoritmi (ne slučajni) koji mogu pronaći medijanu u O(N) vremenu, ali slučajni algoritam je lakši za razumijevanje i često brži od ovih determinističkih algoritama.

Glavna ideja algoritma srednjeg pretraživanja je odabrati nasumični broj među brojevima i izračunati koliko je brojeva u grupi manje od odabranog broja. Recimo da postoji N brojeva, od kojih je K manji ili jednak odabranom broju. Ako je K manji od polovine N, tada znamo da je medijan (N/2-K)-ti broj koji je veći od slučajnog broja, pa odbacujemo K brojeva manji ili jednaki slučajnom broju. Sada recimo da želimo pronaći (N/2-K)-ti najmanji broj umjesto medijane. Algoritam je isti, samo nasumično biramo broj i ponavljamo opisane korake.

Kompresija

Druga klasa algoritama je dizajnirana za kompresiju podataka. Ovaj algoritam nema očekivani rezultat (kao što je algoritam za sortiranje, na primjer), već se radi optimizacija prema nekim kriterijima. U slučaju kompresije podataka, algoritam (na primjer, LZW) pokušava učiniti da podaci zauzmu što manje bajtova, ali u isto vrijeme, tako da se mogu dekomprimirati u izvorni oblik. U nekim slučajevima, ovaj tip algoritma koristi iste metode kao i drugi algoritmi, što rezultira dobrim rezultatom, ali ne i optimalnim. Na primjer, JPG i MP3 komprimiraju podatke na takav način da je konačni rezultat lošijeg kvaliteta od originala, ali je manja veličina. MP3 kompresija ne zadržava sve karakteristike originalne audio datoteke, ali pokušava zadržati dovoljno detalja da pruži prihvatljiv kvalitet uz značajno smanjenje veličine datoteke. JPG format slijedi isti princip, ali se detalji bitno razlikuju jer cilj je komprimirati sliku, a ne zvuk.

Zašto trebate znati sve vrste algoritama

Za pravilno korištenje algoritama važno je poznavati sve navedene vrste algoritama. Ako morate da razvijete važan deo softvera, trebalo bi da budete u mogućnosti da procenite brzinu vašeg algoritma. Točnost vaše procjene ovisi o tome koliko znate o analizi vremena izvršavanja algoritama. Osim toga, morate znati detalje algoritama, koji će vam omogućiti da predvidite posebne slučajeve u kojima program neće raditi brzo ili će dati neprihvatljive rezultate.

Naravno, biće trenutaka kada ćete naići na ranije neistražene probleme. U takvim slučajevima morate smisliti novi algoritam ili primijeniti stari algoritam na novi način. Što više znate o algoritmima, veća je vjerovatnoća da ćete pronaći dobro rješenje problema. U mnogim slučajevima, novi problem se lako svodi na stari, ali to zahtijeva temeljno razumijevanje starih problema.

Kao primjer, razmotrite kako funkcioniraju mrežni prekidači. Prekidač ima N kablova povezanih na njega i prima paket podataka koji dolazi preko ovih kablova. Prekidač mora prvo analizirati pakete, a zatim ih poslati natrag preko ispravnog kabla. Prekidač, kao i računar, radi u diskretnom režimu - paketi se šalju u diskretnim intervalima, a ne neprekidno. Brzi prekidač pokušava poslati što više paketa tokom svakog intervala, inače će se oni akumulirati i svič će "pasti". Cilj algoritma je da pošalje maksimalan broj paketa tokom svakog intervala, kao i da obezbedi da su paketi koji su stigli ranije od drugih takođe poslati ranije od drugih. U ovom slučaju se ispostavlja da je algoritam poznat kao "stabilno podudaranje" prikladan za rješavanje ovog problema, iako to na prvi pogled možda nije očigledno. Takve veze između problema i rješenja mogu se otkriti samo uz pomoć već postojećeg algoritamskog znanja.

Pravi primjeri

Postoji mnogo primjera rješenja stvarnih problema koji zahtijevaju najnovije algoritme. Gotovo sve što radite na računaru zavisi od algoritama koje neko razvija već dugo vremena. Čak ni najjednostavniji programi ne bi postojali bez algoritama koji rade iza kulisa koji upravljaju memorijom i učitavaju podatke sa tvrdog diska.

Postoji na desetine primjera korištenja složenih algoritama, ali ćemo raspravljati o dva problema koja zahtijevaju iste vještine kao i rješavanje nekih problema na TopCoderu. Prvi problem je poznat kao problem maksimalnog protoka, a drugi se odnosi na dinamičko programiranje, tehniku ​​koja vam često omogućava rješavanje problema naizgled nemogućim munjevitim brzinama.

Algoritam za pronalaženje maksimalnog protoka

Zadatak pronalaženja maksimalnog protoka je korištenje dostupne mreže na najbolji način za premještanje nečega s jednog mjesta na drugo. Konkretno, takav problem se prvi put pojavio 1950-ih u vezi sa željezničkim prugama Sovjetskog Saveza. SAD su željele znati koliko brzo bi Sovjetski Savez mogao prebaciti materijale u satelitske države u istočnoj Evropi putem svoje željezničke mreže.

Osim toga, SAD su željele znati koji dio šina bi se najlakše mogao uništiti kako bi se satelitske države odsjekle od ostatka Sovjetskog Saveza. Ispostavilo se da su ta dva problema usko povezana, te da je rješavanje problema maksimalnog protoka riješilo i problem minimalnog rezanja, što bi na kraju otkrilo najjeftiniji način odsjecanja Sovjetskog Saveza od njegovih satelita.

Prvi efikasan algoritam za pronalaženje maksimalnog protoka izmislili su naučnici Ford i Fulkerson. Algoritam je kasnije nazvan Ford-Fulkerson algoritam i jedan je od najpoznatijih algoritama u kompjuterskoj nauci. U posljednjih 50 godina, algoritam je prošao kroz brojna poboljšanja koja su ga učinila bržim (iako su neka od ovih poboljšanja zastrašujuća po svojoj složenosti).

Pošto je problem bio jasno definisan, otkriveno je mnogo različitih aplikacija. Algoritam je direktno povezan s internetom, gdje je važno prenijeti što više podataka s jedne tačke na drugu. Zadatak se također javlja u mnogim poslovnim procesima i važan je dio operativnog istraživanja. Na primjer, ako postoji N zaposlenika i N zadataka koje treba obaviti, ali ne može svaki zaposlenik obaviti svaki zadatak, onda će traženje maksimalnog protoka dati rješenje kako dodijeliti N zaposlenika zadacima na način da svaki zadatak bude završen , pod uslovom da je Možda. Problem diplomiranja iz TopCoder SRM 200 je dobar primjer problema maksimalnog protoka.

Poređenje sekvenci

Mnogi koderi u cijeloj svojoj karijeri nikada nisu morali implementirati algoritam koji koristi dinamičko programiranje. Međutim, dinamičko programiranje se koristi u brojnim važnim algoritmima. Jedan algoritam je pronalaženje razlika između dvije sekvence, što je većina programera vjerovatno koristila, iako ga vjerovatno nisu razumjeli. Ovaj algoritam izračunava minimalni broj umetanja, brisanja, uređivanja potrebnih za pretvaranje sekvence A u sekvencu B.

Na primjer, razmotrite sekvence "AABAA" i "AAAB". Za pretvaranje prve sekvence u drugu, najjednostavnije je ukloniti B u sredini i promijeniti posljednju A u B. Ovaj algoritam ima mnogo aplikacija, uključujući neke zadatke vezane za DNK i otkrivanje plagijata. Međutim, mnogi programeri ga uglavnom koriste za upoređivanje verzija iste datoteke sa izvornim kodom. Ako su elementi niza linije u datoteci, tada vam ovaj algoritam omogućava da saznate koje linije treba izbrisati, umetnuti, promijeniti kako biste pretvorili jednu verziju datoteke u drugu.

Bez dinamičkog programiranja, morate proći kroz eksponencijalni broj transformacija da biste prešli iz jedne sekvence u drugu. Međutim, dinamičko programiranje smanjuje vrijeme izvršenja algoritma na O(N*M), gdje su N i M broj elemenata u dva niza.

Zaključak

Koliko različitih problema postoji, toliko različitih algoritama postoji za njihovo rješavanje. Međutim, postoji velika šansa da je problem koji pokušavate riješiti na neki način sličan drugom problemu. Razvijajući duboko razumijevanje širokog spektra algoritama, moći ćete odabrati pravi algoritam i primijeniti ga na problem. Osim toga, rješavanje problema na takmičenjima na TopCoderu pomoći će vam da usavršite svoje vještine u ovoj oblasti. Mnogi od ovih zadataka izgledaju umjetni i nerealni, ali zahtijevaju isti skup algoritamskog znanja koji je potreban svaki dan u stvarnom svijetu.