Conţinutul principal
Biblioteca de informatică
Curs: Biblioteca de informatică > Unitatea 1
Lecția 1: Introducere în algoritmiCe este un algoritm şi de ce să înveți algoritmi?
Vrei să te alături conversației?
Nici o postare încă.
Transcript video
Ce este un algoritm? O definiție ar putea fi: succesiunea de pași care ne conduce la îndeplinirea unei sarcini. Probabil că ai un algoritm pentru a ajunge
de acasă la școală, pentru a face un sandwich prăjit cu brânză, ori pentru a găsi ce cauți într-un magazin alimentar. În informatică, un algoritm este un set de pași prin care un program execută o sarcină. Datorită algoritmilor, informatica este
o știință. Găsirea algoritmilor buni și aplicarea lor
la momentul potrivit te vor ajuta să implementezi
programe interesante și importante. Hai să vorbim despre câțiva algoritmi cunoscuți. Cum transmite live Google Hangouts atât de repede? Sunt folosiți algoritmi de compresie audio și video. Cum te ajută Google Maps să ajungi din Dallas, Texas în Orlando, Florida și apoi la Disney World? Este folosit un algoritm de găsire a drumului. Cum colorează Pixar un model 3D al unui caracter bazat pe iluminare într-o cameră virtuală? Este utilizat un algoritm de interpretare/transmitere. Cum alege NASA să aranjeze panourile solare ale Stației Spațiale Internaționale și când să le rearanjeze? Utilizează un algoritm
de optimizare și programare. Acești algoritmi sunt mult mai complecși
decât algoritmii tăi zilnici de pregătire a unui sandwich cu brânză,
dar se reduc la același lucru: o serie de pași care trebuie executați
pentru îndeplinirea unei sarcini. Dacă știi ceva despre existența algoritmilor, poți să lucrezi mai eficient, iar programele tale vor fi mai rapide dacă vei alege algoritmul potrivit. De exemplu, să spunem că scrii un joc
și vrei ca utilizatorul să poată juca împotriva computerului. Poți să te gândești la jocul de table,
care să te inspire. Informaticienii au determinat jocul de table
care nu pierde niciodată, folosind algoritmul de căutare Minimax în uriașul "arbore" al mutărilor posibile. Dacă jocul tău este asemănător
jocului de table, poți utiliza algoritmi bazați pe aceste tehnici. Dacă nu, cunoașterea limitărilor acestor algoritmi
te poate conduce la reproiectarea jocului, dacă este nevoie de un jucător inteligent,
controlat de calculator. Este important să știi cum să proiectezi noi algoritmi dar și să știi să analizezi
precizia și eficiența. În biologie, noi algoritmi sunt mereu proiectați, cu scopul de a imita structuri moleculare care stau la baza medicamentelor
ce combat boli. În fizică, algoritmii simulează modele de climat și vreme, iar alții caută și analizează date ale stelelor din Univers care sunt colectate de telescoape. În toate științele, cât și în site-uri web cum este Khan Academy sunt necesari algoritmi eficienți pentru a analiza seturile enorme de date, ori pentru a face o alegere inteligentă. În majoritatea domeniilor care te-ar putea interesa, algoritmii au putere de calcul pentru a face lucruri de care oamenii au nevoie. Acum, nu toți algoritmii sunt creați la fel. Ce face ca un algoritm să fie bun? Sunt două criterii importante de rezolvare a unei probleme pentru ca rezolvarea să fie corectă și eficientă. Un algoritm bun/eficient trebuie
să ne dea întotdeauna răspunsul corect. Uneori însă, putem accepta un algoritm
care nu ne dă cel mai bun răspuns: atunci când singurii algoritmi perfecți
pe care îi cunoaștem, pentru aceste probleme, au nevoie de foarte mult timp. De exemplu, vrem un program care determină cea mai eficientă rută pentru un camion care să livreze pachete, începând și terminând ziua într-o anumită stație. Ar dura săptămâni să încerci toate posibilitățile. Dar dacă ne conformăm unui program
care determină o rută bună, nu chiar cea mai eficientă, dar rapidă? În unele cazuri, "bun" e de ajuns. Cum măsurăm eficiența unui algoritm? Putem măsura cât timp durează execuția codului, dar asta descrie cea mai bună implementare pentru acel calculator și în acel limbaj de programare, doar pentru acele date de intrare. Informaticienii folosesc o tehnică
numită "Analiza asimptotică". Aceasta permite compararea algoritmilor,
independent de limbaj sau hardware. Deci, putem spune că unii algoritmi
sunt mai eficienți decât alții. Acum poți învăța despre algoritmi și analiza asimptotică la Khan Academy, mulțumită contribuției celor doi
profesori de la Universitatea Dartmouth: Thomas Cormen este primul autor al celei
mai populare cărți de algoritmi din lume, fiind și autorul cărții "Algoritms unlocked" . Devin Balkcom a proiectat cursul
instructiv de informatică Dartmouth și este cercetător în domeniul roboticii. A construit primul robot din lume
care face origami. Tom și Devin te vor învăța multe despre
algoritmii prezentați în APCS sau CS-101, precum algoritmii de căutare,
algoritmii de ordonare, algoritmii recursivi și preferații mei, algoritmii pe grafuri. Vor fi jocuri, teste, provocări
legate de programare care să te ajute să îi înțelegi mai bine,
în aventura ta de cunoastere.