Algoritmi/Uvod

Ova knjiga pokriva tehnike za projektovanje i analizu algoritama. Algoritamske tehnike uključuju: "zavadi, pa vladaj", "bektreking", dinamičko programiranje, "pohlepi algoritmi" i pretraživanje usponom. Bilo koji rešivi problem u opštem smislu ima bar jedan od sledećih tipova algoritama:

1. očigledan način
2. medotičan način
3. pametan način; i
4. čudesan način

Prvi, od svih osnovnih nivoa, "očigledno" rešenje bi možda pokušao da iscrpljujuće pretražuje odgovor. Intuitivno, očigledno rešenje je ono koje nastaje jednostavno ako ste upoznati sa programskim jezikom i osnovnim tehnikama rešavanja problema. Drugi nivo je metodičan nivo i on je ključ ove knjige: nakon razumevanja materijala koji je prikazan ovde, moći ćete da na metodičan način da pretvorite većinu očiglednih algoritama u bolje predstavljen algoritam.

Treći nivo, pametan nivo, zahteva više razumevanja elemenata koji su uključeni u problem i razumevanje njihovih osobina, ili čak redefinisanje algoritma (na primer, numerički algoritmi iskorišćavaju matematička svojstva koja nisu očigledna). Pametan algoritam je možda težak za razumevanje, jer nije očigledno da je tačan, ili je težak za razumevanje, jer se zapravo izvršava brže nego što bi izgledalo to što zahteva.

Četvrti i poslednji nivo algoritamskog rešenja je čudesan nivo: on je rezervisan za retke slučajeve gde je prodoran rezultat veoma ne-intuitivno rešenje. Prirodno, svaki od ova četiri nivoa je relativan i neki pametni algoritmi su takođe obuhvaćeni u ovoj knjizi. Počnimo.

Preduslovi

Kako biste razumeli meteriju koja je prikazana u ovoj knjizi, morate znati programski jezik dovoljno dobro da možete prevedete pseudokod u ovoj knjizi u radno rešenje. Takođe treba da znate osnove o sledećim strukturama podataka: nizovima, stekovima, redovima, ulančanim listama, stablu, hipu ili redu sa prioritetom, razdvojenim skupovima i grafovima. Osim toga, trebalo bi da znate osnovne algoritme kao što su binarna pretraga, algoriam sortiranja (merge sort, heap sort, insertion sort i drugi) i pretraživanje-prvo-u-širinu ili pretraživanje-prvo-u-dubinu. Ako niste upoznati ni sa jednim od ovih preduslova, trebalo bi prvo da pogledate materiju u knjizi Strukture Podataka.

Kada je efikasnost bitna?

Ne zahteva svaki problem najefikasnije moguće rešenje. Za naše namene, termin efikasan se bavi vremenom i/ili prostorom za koje je potrebno da obavi zadatak. Kad su i vreme i prostor obilni i jeftini, onda se možda ne isplati plaćanje programera da provede dan radeći da tome da program postane brži. Međutim, evo nekih slučaja gde je efikasnost bitna:

• Kada su resursi ograničeni, promena u algoritmu može da napravi veliku uštedu i dopusti da se ograničene mašine (kao što su mobilni telefoni, ugrađeni sistemi i senzor mreža) protežu na granicama mogućnosti.
• Kada je podatak jako velik, efikasnije rešenje može označavati razliku između završavanja zadatka u dva dana umesto u dve nedelje. Primer uključuje fiziku, genetiku, veb pretraživanje, masivne onlajn prodavnice i mrežno analiziranje saobraćaja.
• Aplikacije koje rade u realnom vremenu: ovaj termin se, ustvari, odnosi na proračune koji daju vremensku garanciju, naspram značenja reči "brzo". Međutim, kvalitet može samo da raste dalje birajući primereni algoritam.
• Računsko skupi poslovi, kao što je dinamika fluida, parcijalna diferencijalna pitanja, VLSI dizajn i analiziranje kriptograma se nekad samo mogu razmotriti kada rešenje bude nađeno dovonjno efikasno.

Kada se potprogram često koristi, vreme provedeno na efikasnijoj implementaciji može da doprinese korist za svaku aplikaciju koja koristi potprogram. Primeri uključuju sortiranje, pretraživanje, generisanje pseudoslučajnog broja, kernel operacije (ne treba mešati sa operativnim sistemom kernel), upiti baza podataka i grafike.

In short, it's important to save time when you do not have any time to spare. When is efficiency unimportant? Examples of these cases include prototypes that are used only a few times, cases where the input is small, when simplicity and ease of maintenance is more important, when the area concerned is not the bottle neck, or when there's another process or area in the code that would benefit far more from efficient design and attention to the algorithm(s).

Ukratko, bitno je uštedeti vreme, kada nemate vremena za gubljenje. Kada je bitna efikasnost? Primeri ovih slučajeva uključuju prototipe koji se koriste samo nekoliko puta, kada je ulaz vrlo mali, kada je jednostavnost održavanja bitnija, kada posmatrana oblast nije "usko grlo" ili kada kada postoji drugi proces ili oblast u kodu gde bi bilo mnogo više koristi od efikasnog projektovanja i pažnje na algoritam (algoritme).

Smisliti algoritam

Pošto pretpostavljamo da imate neko znanje o nekom programskom jeziku, počnimo sa pitanjem kako bismo preveli ideju u algoritam. Pretpostavimo da želite da napišete funkciju koja uzima string kao ulazni podatak i isti taj string sa malim slovima kao izlazni podatak:

// tolower -- funkcija koja prevodi sva alfabetska velika slova, u nekom nizu karaktera str, u mala slova

function tolower(string str): string

Šta vam prvo pada na pamet kada razmišljate kako biste rešili ovaj problem? Možda neka od ova dva razmatranja:

1. Svaki karakter u str se mora razmotriti
2. Potrebna je funkcija koja prebacuje jedan karakter u malo slovo

Prva tačka je "očigledna", jer karakter koji treba da bude pretvoren u malo slovo se može nalaziti bilo gde u stringu. Druga tačka proizilazi iz prve jer, onda kada razmotrimo svaki karakter, moramo nešto i uraditi sa njim. Postoji mnogo načina da se napiše tolower funkcija za karaktere:

Postoji par načina da implementirate ovu funkciju, koji uključuju sledeće:

• pogledati c u tabeli -- indeksirani karakter u nizu karaktera koji ima verziju malog slova za svaki karakter.

• proveriti da li je c u opsegu 'A' ≤ c ≤ 'Z' i onda mu dodati numerički ofset.

Ove tehnike zavise od koda karaktera. (Kao problem podele, možda je tabela bolje rešenje, jer je jasnije da treba promeniti samo jedan deo koda.)

Međutim kada je takav podprogram implementiran, implementacija našeg originalnog problema odmah sledi:

function tolower(string str): string
  let result := ""
  for-each c in str:
    result.append(tolower(c))
  repeat
  return result
end

Petlja je rezultat naše sposobnosti da prevedemo "svaki karakter treba razmotriti" u naš nativni programski jezik. Da poziv funkcije tolower treba biti u telu petlje, postaje očigledno. Ovde smo rešili da počnemo sa praznim stringom i da dodamo karaktere na kraj stringa.

Sada pretpostavimo da želite da napišete funkciju koja poredi dva stringa tako što testira da li su isti, zanemarujući da li su slova mala ili velika:

// equal-ignore-case -- vraća true ako su stringovi s i t jednaki, bez obzira na to da li su slova mala ili velika

function equal-ignore-case(string s, string t): boolean

Ove ideje vam možda padnu na pamet:

1. Svaki karakter u stringu s i t će se morati razmotriti
2. Jedna petlja koja će prolaziti kroz oba stringa bi to rešila
3. Ali takva petlja bi trebalo da pripazi prvo da li su stringovi iste dužine
4. Ako stringovi nisu istih dužina, onda ne mogu biti jednaki, jer ignorisanje veličine slova ne utiče na to koliko je string dugačak
5. tolower potprogram za karaktere se može ponovo iskoristiti i poredi će samo mala slova

Funkcija koju smo razmotrili bi izgledala otprilike ovako:

function equal-ignore-case(string s[1..n], string t[1..m]): boolean
  if n != m:
    return false               \if they aren't the same length, they aren't equal\
  fi
  
  for i := 1 to n:
    if tolower(s[i]) != tolower(t[i]):
      return false
    fi
  repeat
  return true
end

Ili, ako ste razmatrali problem u smislu funkcionalne dekompozicije umesto iteracija, funkcija bi izgledala ovako:

function equal-ignore-case(string s, string t): boolean
  return tolower(s).equals(tolower(t))
end

Alternativno, možda smatrate da ni jedan od ovih rešenja nije doboljno efikasan i da biste više voleli da algoritam napravi jedan prolaz kroz s ili t. Ove dve implementacije iznad zahtevaju dva prolaza: prva verzija računa dužinu stringa i onda poredi karaktere, dok druga verzija računa da li je karakter malo ili veliko slovo u stringu i onda poredi rezultate. (Primetite da je za par stringova takođe moguće da se njihova dužina izračuna pre drugog prolaza, ali to takođe ima nedostataka ponekad.) Možete zamisliti koliko sličnih potprogorama koji testiraju jendakost stringova koji ne samo da ignorišu mala i velika slova, već i akcente, mogu biti napisani.

Već sad možda možete da uvidite kako se piše pseudokod. Pseudokod nije namenjen da bude pravi programski jezik: apstrahuje detalje koje biste morali da sadržite u bilo kom proramskom jeziku. Na primer, jezik ne preuzima generičke tipove ili dinamične u odnosu na statičke tipove: ideja je da bude jasno da ste namenili i da ne bude mnogo teško da ga prevede na svoj nativni jezik. (Međutim, tako radeći, morate da donsete neke odluke što se tiče projektovanja koje ograničavaju implementaciju u jedan konkretan tip forme podatka.)

Nema ničeg posebnog u tehnikama koje smo koristili kako bismo rešili jednostavan problem stringa: možda ste pronašli bolje ili elegantnije rešenje u programskom jeziku koji ste izabrali. U ovoj knjizi smo istražili opšte tehnike algoritama kako bismo proširili vaše znanje. Možda nećete odmah uspeti da neki nativni algoritam napravite efikasnijim, ali nakon razumevanja materije ove knjige ćete moći da metodično nađete različita rešenja i, što je još bitnije, moći ćete da pitate sebe više pitanja o svom programu. Postavljanje pitanja može biti jednako bitno kao i odgovaranje na pitanja, jer postavljanje dobrih pitanja vam može pomoći da reformulišete problem i da razmišljate inventivno.

Razumevanje algoritma

Programeri treba odlično da razumeju višestruko-slojevite abstrakcije. Na primer, pogledajte sledeći kod:

function foo(integer a):
  if (a / 2) * 2 == a:
     print "The value " a " is even."
  fi
end

Depending on the programming task, you may think on the layer of hardware, on down to the level of processor branch-prediction or the cache.

Da biste razumeli ovaj primer, morate da znate da deljenje celih brojeva koristi skraćivanje i da ako je if-uslov tačan, onda je poslednji značajan bit u a nula (što znači da a mora da bude paran). Takođe, kod koristi ispisivanje stringa API i sam po sebi je definicija funkcije koja se koristi različite module. U zavisnosti od zadatka, možete razmišljati ??

Često je razumevanje binarnog sistema je od presudnog značaja, ali mnogi moderni jezici imaju abstrakcije dovoljno daleke od hardvera tako da ovi niži nivoi nisu potrebni. Negde se abstrakcije zaustavljaju: mnogi programeri ne moraju da misle o logičkim kapijama, niti su fizika i elektronika potrebne. Ipak, bitan deo programiranja je višestruko-slojeviti način razmišljanja.

Ali udaljavanjem od komjuterskih programa prema algoritmima zahteva još jedan sloj: matematiku. Program može da iskoristi svojstva binarne reprezentacije. Algoritam može da iskoristi i svojstva teorije skupova i drugih matematičkih struktura. Baš kao što binarni sistem nije eksplicitno u programu, ni matematička svojstva korišćena u algoritmu nisu eksplicitna.

Tipično, kada je algoritam upoznat, diskusija (odvojena od koda) je potrebna da objasni matematiku koja se koristi u algoritmu. Na primer, da biste zaista razumeli "pohlepi" algoritam (kao što je Dajkstrin algoritam) morate da razumete matematička svojstva koja pokazuju da je "pohlepi" algoritam validan za sve slučajeve. Na neki način, možete posmatrati matematiku kao posebnu vrstu potprograma koji algoritam poziva. Ali ovaj "potprogram" nije pokazan u kodu zato što nema šta da se poziva. Dok čitate ovu knjigu, pokušajte da posmatrate matematiku kao implicitan potprogram.

Pregled tehnika

• Podeli, pa vladaj: Mnogi problemi, posebno kada je ulazni podatak dat u nizu, se može rešiti tako što podelimo problem u manje delove, rešimo te manje delove rekurzivno (vladaj) i onda kombinujemo rezultate u jedan rezultat. Primeri uključuju sortiranje spajanjem i algoritam brzog sortiranja.

• Randomizacija: Tehnike randomizacije su bitne za sve više i više aplikacija. Ovo poglavlje pokazuje neke klasične algoritme koji koriste slučajne brojeve.

• Bektreking: Skoro svaki problem može da se formuliše kao bektreking algoritam. Kod bektreking algoritama, treba uzeti u obzir sve moguće izbore kako bi rešili problem i rekurzivno rešili potprobleme pod pretpostavci da je izbor donet. Skup svih rekurzivnih poziva generiše stablo u kom se svaki skup izbora se uzima u obzir uzastopno. Stoga, ako rešenje postoji, ono će se u svoje vreme naći.

  Bektreking je generalno neefikasan, nasilna tehnika, ali postoje optimizacije koje mogu biti izvršene da smanje i dubinu stabla i broj grana. Tehnika se zove bektreking, jer nakon što je prvi list posećen, algoritam se vraća nazad i poziva stek (poništavanje izbora koji ne vode ka uspehu) i onda nastaviti na donju granu. Da bi rešili problem tehnikama bektreking-a, problem treba da ima formu "samo-sličnosti", tako da manji primerak problema (nakon što je donešena odluka) mora da liči na originalan problem. Obično, problemi mogu biti uopšteni da bi postali samo-slični.

• Dinamičko programiranje: Dinamičko programiranje je optimizaciona tehnika za bektreking algoritme. Kada potproblemi treba da se reše brzo (npr. kada ima puno duplikata grana u bektreking algoritmu) vreme može biti zapamćeno tako što se reši prvo svaki problem (od dole-pa na gore, od najmanjeg do najvćih) i tako što se skladište rešenja svakog potproblema u tabelu. Tako, svaki potproblem može biti posećen i rešen jednom umesto brzo. "Programiranje" u nazivu ove tehnike dolazi od programiranja u smislu upisivanja u tabelu; na primer, programiranje televizije je pravljenje tabele emisija koje će se emitovati i kada će se emitovati.

• "Pohlepni" algortmi: Pohlepi algoritam može biti koristan kada se zna dovoljno informacija o mogućim izborima. Najbolji izbor se može odrediti bez obzira na sve moguće izbore. Tipično, pohlepni algoritam nisu teški za pisanje, ali se teško dokazuju da su tačni.

• Pretraživanje usponom: Poslednja tehnika koju samo istražili je pretraživanje usponom. Osnovna ideja je da se počne sa lošem rešenjem i da se brzo primeni optimizacija za rešenje dok ne postane optimalan ili se ne ispuni neki drugi uslov. Bitan slučaj pretraživanja usponom je mrežni protok. Uprkos imena, mrežni protok je koristan za mnoge probleme koji opisuju odnose, tako da nisu samo za računarske mreže. Mnogi slični problemi se mogu rešiti korišćenjem mrežne protoke.

---

Algoritmi i primeri kodova

Prvi nivo (najlakši)

1. Pronaći maksimum: sa algoritmom i više različitih programskih jezika

2. Pronaći minimum: sa algoritmom i više različitih programskih jezika

3. Pronaći srednju vrednost: sa algoritmom i više različitih programskih jezika

4. Pronaći stanje: sa algoritmom i više različitih programskih jezika

5. Pronaći total: sa algoritmom i više različitih programskih jezika

6. Računanje: sa algoritmom i više različitih programskih jezika

Drugi nivo

1. Razgovor sa računarom Nivo 1: sa algoritmom i više različitih programskih jezika 2. Sortitanje - bublle sort: sa algoritmom i više različitih programskih jezika

Treći nivo

1. Razgovor sa računarom Nivo 2: sa algoritmom i više različitih programskih jezika

Četvrti nivo

1. Razgovor sa računarom Nivo 3: sa algoritmom i više različitih programskih jezika 2. Pronaći približan maksimum: sa algoritmom i više različitih programskih jezika

Peti nivo

1. Quicksort