Algoritem

Algorítem je navodilo, s katerim se rešuje nek problem. Običajno je zapisan kot seznam korakov, ki pripeljejo do rešitve problema. Kako podrobno se razdela korake, je odvisno od tega, kdo izvaja algoritem (človek, računalnik). Če algoritem izvaja računalnik, potem se govori o računalniškem programu.

Al-Hvarizmi na znamki Sovjetske zveze.

Etimologija

Beseda algoritem izhaja iz imena perzijskega matematika in pisca Al-Hvarizmija, ki je v 9. stoletju postavil algoritme za osnovne matematične operacije. Njegova najbolj pomembna knjiga, Kitab al-Džabr val-Mukabala (Pravila reintegracije in redukcije), je bila osnova za standardizacijo arabskih številk v evropski matematiki. Del njegovega imena, Al-Džabr, je bilo kasneje interpretirano kot beseda algebra. Okoli leta 1960 se je izraz algoritem pojavil v računalniškem izrazoslovju in je deduktivni postopek za reševanje matematičnih problemov.

Značilnosti algoritma

• (lahko) ima podatke,
• (običajno) vrne rezultat,
• je natančno določen,
• je končen,
• je izvedljiv.

Zapis algoritma

Algoritem se lahko zapiše na več načinov:

• v naravnem jeziku
• grafično s pomočjo diagrama poteka
• s pomočjo psevdokode
• kot program v enem od programskih jezikov.

Kategorije algoritmov

Obstajajo različne kategorije algoritmov, bolje rečeno strategij, ki se jih uporablja za reševanje problemov. Poznane in razdelene strategije so:

• deli in vladaj
• dinamično programiranje
• požrešna metoda
• linearno programiranje
• verjetnostni algoritmi

Pri analizi algoritma je običajno v osprednju zanimanja njegova prostorska in časovna zahtevnost.

Ena izmed bolj znanih knjig o algoritmih in o programiranju je Knuthova Umetnost računalniškega programiranja (The Art of Computer Programming).

Glej tudi

• Evklidov algoritem
• algoritmi za urejanje podatkov
• NP problemi
• IDEA