Algoritem

Algorítem je navodilo, s katerim rešujemo določen problem. Običajno je zapisan kot seznam korakov, ki nas pripeljejo do rešitve problema. Kako podrobno razdelamo korake, je odvisno od tega, kdo izvaja algoritem (človek, računalnik). Če algoritem izvaja računalnik, potem govorimo o računalniškem programu. Primer algoritma iz vsakdanjega življenja je kuharski recept.

Al-Hvarizmi na znamki Sovjetske zveze.

[uredi] 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-Jabr wal-Muqabala (Pravila reintegracije in redukcije), je bila osnova za standardizacijo arabskih številk v evropski matematiki. Del njegovega imena, Al-Jabr, 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.

[uredi] Značilnosti algoritma

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

[uredi] Zapis algoritma

Algoritem lahko zapišemo 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.

[uredi] Kategorije algoritmov

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

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

Pri analizi algoritma nas običajno zanimata njegova prostorska in časovna zahtevnost.

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

[uredi] Glej tudi

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