Osnove računarskih nauka

Drugi u seriji tekstova kroz koje ćemo videti kako samostalno možete naučiti da pišete kod. Ukoliko želite čvrste osnove i temeljno znanje o tome kako računari rade, evo odakle da počnete.

Aleksa Vidović - 6. Decembar, 2017.

Budimo realni — možete se baviti programiranjem i zarađivati lepe pare i bez da imate temeljno znanje iz računarskih nauka.

Ne morate znati da implementirate heap sort u C++-u u pola noći da biste mogli da živite od pisanja koda.

Ipak, morate biti svesni da će postojati određena ograničenja u vašoj karijeri, o kojima smo govorili u tekstu Dva tipa programera i zašto je važno da ne budete onaj drugi.

Zašto učiti računarske nauke?

Postoje dve vrste developera: oni koji razumeju računarske nauke dovoljno dobro da bi mogli da rade na izazovnim, inovativnim stvarima, i oni koji se samo provlače kroz karijeru jer znaju da koriste par alata.

I jedni i drugi sebe nazivaju softverskim inženjerima, i jedni i drugi slično zarađuju na početku svojih karijera. Ali developeri prvog tipa kasnije rade na poslovima koji nude mnogo više satisfakcije, bilo da je to komercijalni rad, uticajni open-source projekti, tehičko liderstvo ili značajan individualni doprinos.

Inženjeri prvog tipa nađu način da temeljno izuče računarske nauke, na konvencionalan način ili neprestanim učenjem kroz karijeru.

Inženjeri drugog tipa uglavnom ostaju na površini, fokusirajući se na specifične alate i tehnologije umesto na fundamentalne principe, učeći nove tehnologije kada ih trendovi na to nateraju. Ne bi se zapravo ni moglo reći da su oni “inženjeri”.

Broj ljudi koji ulaze u industriju vrtoglavo raste, dok broj svršenih studenata računarstva manje-više ostaje isti. Ova prezasićenost inženjerima drugog tipa počinje njima samima da umanjuje šanse za zaposlenje, i ne dozvoljava im da se bave ispunjavajućim poslovima koje industrija nudi.

Bilo da stremite ka tome da postanete inženjer prvog tipa ili želite sigurnost zaposlenja, učenje računarskih nauka je jedini pouzdan način za to.

Ukoliko se odlučite da istražite šta se to krije ispod haube, shvatićete da je kucanje koda najmanje važna aktivnost u razvoju softvera, samo nuspojava koja proizilazi iz razmišljanja i rešavanja problema.

Uz dozvolu autora, preveli smo delove stajta teachyourselfcs.com. Izložene su oblasti računarskih nauka, uz objašnjenje zašto je poznavanje svake od njih važno za nekoga ko se bavi razvojem softvera, a preporučeni su i kursevi i knjige za svaku od njih.

Očigledno, ovo su kursevi i knjige koje autori smatraju za najbolje u datim oblastima, ali verovatno za svaku od oblasti možete da nađete i neki kurs i knjigu koji vama više odgovaraju — Google (khm, i torent) je vaš prijatelj.

Nismo prevodili imena knjiga, jer nismo sigurni da sve možete da ih nabavite na srpskom.

***

Postoje brojni resursi, ali su neki bolji od drugih. Ne treba vam još jedan članak tipa “200+ besplatnih onlajn kurseva”. Trebaju vam odgovori naa sledeća pitanja:

Koje oblasti treba da učite, i zašto?

Koji su najbolji knjiga i video kurs za svaku od oblasti?

Ovaj vodič je naš pokušaj da konačno odgovorimo na ta pitanja.

Ukratko:

Upoznajte se sa svim oblastima ispod, otprilike po navedenom redosledu, koristeći ili navedeni kurs ili knjigu, idealno oba. Trudite se da posvetite od 100 do 200 sati svakoj oblasti, a onima koje vam se svide se možete vratiti kasnije tokom vaše karijere.

Programiranje

Ne budite jedan od onih koji “nisu baš najbolje razumeli” rekurziju.

Preporučena knjiga: Structure and Interpretation of Computer Programs

Preporučane predavanjaBerkeley CS 61A

Arhitektura računara

Ukoliko nemate jasan mentani model toga kako računar zaista radi, sve vaše apstrakcije visokog nivoa stajaće na klimavim nogama.

Preporučena knjiga: Computer Organization and Design

Preporučane predavanjaBerkeley CS 61C

Algoritmi i strukture podataka

Ako ne umete da koristite strukture podataka kao što su stek, kju, stablo, i graf, nećete moći da rešavate teške probleme.

Preporučena knjiga: The Algorithm Design Manual

Preporučane predavanja: predavanja Stivena Skiene

Matematika za računarske nauke

Računarske nauke su u stvari dalji rođak primenjene matematike, tako da će vam učenje matematike dati kompetitivnu prednost.

Preporučena knjiga: Mathematics for Computer Science

Preporučane predavanja: Tom Lejtononv MIT 6.042J

Operativni sistemi

Većinu koda koji pišeš pokreće operativni sistem, pa bi trebalo da znaš kakvu interakciju imaju ta dva.

Preporučena knjiga: Operating Systems: Three Easy Pieces

Preporučane predavanja: Berkeley CS 162

Računarske mreže

Internet je sveprisutan, ukoliko razumeš kako on radi možeš da iskoristiš njegov pun potencijal.

Preporučena knjiga: Computer Networking: A Top-Down Approach

Preporučane predavanja: Stanford CS 144

Baze podataka

Podaci su u srži svih važnih programa, ali malo ko razume kako baze podataka funkcionišu.

Preporučena knjiga: Readings in Database Systems

Preporučane predavanja: Berkeley CS 186

Jezici i kompajleri

Ukoliko budete razumeli kako programski jezici i kompajleri u stvari rade, pisaćete bolji kod i lakše učiti nove jezike.

Preporučena knjiga: Compilers: Principles, Techniques and Tools

Preporučane predavanja: Kurs Aleksa Ajkena

Distribuirani sistemi

U današnjem svetu, većina sistema su distruibuirani sistemi.

Preporučena knjiga: Distributed Systems, 3rd Edition — Maarten van Steen

Objašnjenja za svaku oblast

Programiranje

Većina studijskih programa vezanih za računare počinje sa “uvodom” u programiranje. Najbolje verzije ovih kurseva nisu namenjene samo početnicima, već i onima koji su propustili da nauče važne i korisne koncepte kada su počinjali da uče.

Naša standardna preporuka ovde je Structure and Interpretation of Computer Programs, koja je dostupna i kao besplatna knjiga, ali i u vidu video predavanja sa MIT-a. Ta predavanja jesu odlična, ali smo se po tom pitanju ipak odlučili za kurs CS 61A sa Berklija, jer je prilagođeniji za početnike od predavanja sa MIT-a.

Onima koji misle da su im preporučeni materijali previše teški, preporučujemo How to Design Programms. Onima kojima je prelako, preporučujemo Concepts, Techniques, and Models of Computer Programming.

Arhitektura računara

Proučavanje arhitekture računara je prvi korak ka razumevanju principa rada računara ispod površine softvera. Iz našeg iskustva, ovo je oblast koju samouki developeri najčešće zapostavljaju.

The Elements of Computing Systems, poznatija i kao “Nand2Tetris” knjiga sa ambicioznim ciljem da vam predstavi kako računar radi. Svako poglavlje bavi se prikazivanjem malog dela celokupne slike, od pisanja osnovnih logičkih kola u HDL-u, preko procesora i asemblera, sve do aplikacije veličine Tetrisa.

Preporučujemo da pročitate barem prvih šest poglavlja i uradite zadatke u njima. Ovo će produbiti vaše razumevanje veze između arhitekture mašine i softvera koji ona pokreće.

Prva polovina knjige (i projekti zadati u njoj) besplatno je dostupna na Nand2Tetris sajtu, ali i u vidu kursa na Coursera.com.

Kako bi postigla jednostavnost i konciznost, Nand2Tetris žrtvuje temeljitost. Konkretno, dva veoma važna koncepta vezana za moderne računare, pajplajning i hijerarhija memorije, nisu obrađeni u knjizi.

Kada vam materijal iz Nand2Tetrisa postane blizak, naša preporuka je Patersonova i Henesijeva knjiga Computer Organization and Design, koja ima status klasika u ovoj oblasti. Nisu svi delovi knjige podjednako važni; preporučujemo da pratite kurs CS61C sa Berklija, u okviru kojeg su data uputstva za čitanje. Beleške sa predavanja i vežbi su dostupne onlajn, a prošla predavanja su dostupna ovde.

Algoritmi i strukture podataka

Saglasni smo sa višedecenijskim iskustvom da je poznavanje popularnih algoritama i struktura podataka jedan od najosnažujućih aspekata obrazovanja u oblasti računarskih nauka. Ovo je takođe i sjajna prilika da izoštrite svoje veštine rešavanja problema, što će pozitivno uticati na sve što kasnije budete učili.

Postoje na stotine knjiga, ali naš favorit je The Algorithm Design Manual od Stivena Skijene. On očigledno obožava ovu temu i ne može da dočeka da podeli svoje znanje sa vama. Ovo je fino osveženje u odnosu na najčešće preporučivane autore.

Za one koji preferiraju video format, Skijena je velikodušno podelio svoja predavanja onlajn. Tu je i kurs Tima Rafgardena, koji je dostupan na Stenfordovoj MOOC platformi Lagunita, kao i na Courseri. Izaberite kurs prema tome čiji vam stil predavanja više leži.

Za vežbu, preporučujemo neku od platformi za rešavanje algoritamskih zadataka — Leetcode, HackerRank, Spoj, i slične. Na njima se mogu naći zanimljivi problemi, a dosta ćete naučiti dok ih budete rešavali. Oni vam pomažu i da vidite svoj napredak rešavajući pitanja i zadatke koji se često pojavljuju i na intervjuima za posao.

Konačno, preporučujemo knjigu How to Solve It, odličan vodič kroz rešavanje problema. Primenjiva je kako na matematiku, tako i na programiranje.

Matematika za računare

Na neki način, računarske nauke su prerasla grana primenjene matematike. Dok mnogi programeri pokušavaju — i u različitoj meri uspevaju — da ignorišu ovu činjenicu, mi vam preporučujemo da je oberučke prihvatite. Ukoliko vam to pođe za rukom, imaćete ogromnu kompetitivnu prednost nad onima koji su slabije upoznati sa ovom temom.

Najrelevantnija oblast matematike za bavljenje softverom naziva se krovnim terminom “diskretna maetmatika”, gde je “diskretno” suprotno od “kontinualnog”, i vezuje se za skup zanimljivih tema u primenjenoj matematici koji se ne odnose kalkulus.

Uzimajući u obzir široku i neodređenu definiciju, ne bi imalo puno smisla da pokušate da naučite sve što termin “diskretna matematika” pokriva.

Realističniji cilj bi bio da izgradite primenjivo znanje u oblastima kao što su logika, kombinatorika i verovatnoća, teorija skupova, teorija grafova, i malo teorije brojeva vezane za kriptografiju. Linearna algebra je još jedna zanimljiva oblast koju je korisno proučiti, s obzirom na njenu važnost u kompjuterskoj grafici i mašinskom učenju.

Naša preporuka za upoznavanje sa diskretnom matematikom jesu beleške sa predavanja profesora Lasla Lovaša. Profesor Lovaš je učinio materiju razumljivom i intuitivnom, tako da ovo može da posluži kao bolja polazna tačka od većine formalnih knjiga i udžbenika.

Za naprednije, preporučujemo Mathemathics for Computer Science, beleške sa istoimenog kursa sa MIT-a. Dostupni su i video snimci predavanja, i to su predavanja koja preporučujemo za diskretnu matematiku.

Što se tiče linearne algebre, možete početi sa video serijalom Essence of linear algebra, a zatim preći na knjigu i predavanja Gilberta Stranga.

Ako ljudi ne misle da je matematika jednostavna, to je zato što ne shvataju koliko je život komplikovan.

-Džon von Nojman

Operativni sistemi

Operating System Concepts (takozvana “Dinosaurus knjiga”) i Modern Operating Systems su “klasici” na temu operativnih sistema. Obe su dobile negativne kritike zbog stila kojim su napisane, i zbog toga što su napisane kao preobimni udžbenici od 1000 i više strana, u kojima se na svakih par godina promeni par sitnica kako bi čitaoci bili naterani da kupe “najnovije izdanje”.

Operating Systems: Three Easy Pieces je dobra alternativa koja je besplatno dostupna onajn. Nama se pogotovo dopala struktura knjige i smatramo da su vežbe vredne rađenja.

Nakon toga, bilo bi dobro da se upoznate sa odlukama donesenim prilikom dizajna popularnih operativnih sistema. Ovo ćete najbolje uraditi kroz knjige poput Lion’s commentary on Unix, The Design and Implementation of the FreeBSD Operating System, i Mac OS X Internals. Za svaki od operativnih sistema možete pronaći knjige koje objašnjavaju njegovu strukturu i princip rada.

Odličan način da utvrdite svoje razumevanje operativnih sistema jeste da pročitate kod malog kernela i da pokušate da ga nadogradite. Za to možete koristiti xv6, a knjiga OSTEP ima dodatak koji pokriva ovo, uz to dajući vam mnoge ideje za potencijalne projekte.

Računarske mreže

Kada pogledate koliko modernog softvera se piše za web servere i klijente, ne čudi što su računarske mreže jedna od oblasti čije vam se poznavanje može najbrže isplatiti. Samouki developeri koji odluče da posvete svoje vreme učenju mreža uglavnom kažu da su im pojmovi, koncepti, i protokoli kojima su bili okruženi godinama konačno postali jasni.

Naša omiljena knjiga na ovu temu je Computer Networking: A Top-Down Approach. Vredi proći sve vežbe i projekte iz knjige, a najviše nam se dopao “Wireshark labs”, koji je besplatno dostupan onlajn.

Za one koji preferiraju video format, preporučujemo kurs sa Stenforda Introduction to Computer Networking.

U učenju mreža više će vam pomoći projekti nego vežbe. Neki od mogućih projekata su: HTTP server, čet aplikacija koja koristi UDP, mini TCP stek, proksi ili load balancer, distribuirana heš tabela.

Baze podataka

Za samostalno učenje baza podataka potrebno vam je više rada nego za bilo koju drugu oblast. Ovo je relativno nova (od 70-ih pa nadalje) oblast sa jakim komercijalnim interesom da ideje ostanu iza zatvorenih vrata. Uz to, mnogi potencijalno sjajni autori odlučili su da se pridruže nekoj ili osnuju svoju kompaniju.

Imajući sve to u vidu, preporučujemo svima koji žele da nauče nešto da za početak izbegnu knjige i udžbenike i krenu od CS 186 na Berkliju, a kasnije nastave sa čitanjem naučnih radova na ovu temu.

Jedan od radova posebno vrednih čitanja za početnike je “Architecture of a Database System”. On pruža odličan pregled toga kako RDBMS radi, i postavlja odličan temelj za dalje učenje.

Readings in Database Systems, poznatija kao “Crvena Knjiga” o bazama podataka, je kolekcija studija koje su prikupili i uredili trojica autora. Za one koji su prevazišli nivo znanja iz kursa CS 186, Crvena Knjiga bi trebalo da bude sledeća stanica.

Ako želite da počnete od knjige koja je više namenjena početnicima, preporučujemo Database Management Systems od Ramakrišnana i Gerkea. Za one naprednije, knjiga Džim Greja Transaction Processing: Concepts and Techniques bi trebalo da bude adekvatna, ali je ne preporučujemo kao prvu knjigu o bazama podataka.

Teško ćete utvrditi teoriju bez da napišete dobru količinu koda. Oni koji budu pratili CS 186 nadograđivaće Spark, što je dobar projekat, ali ipak vam reporučujemo da sami napišete RDBMS od nule. Neće biti sjajan, naravno, ali pisanje čak i najosnovnije verzije svakog od aspekata RDBMS-a može delovati prosvetljujuće.

Konačno, modeliranje podataka je zapostavljen i loše podučavan aspekt rada sa bazama podataka. Na tu temu preporučujemo knjigu Data and Reality: A Timeless Perspective on Perceiving and Managing Information in Our Imprecise World.

Distribuirani sistemi

Kako im se povećavao broj, kompjuteri su postajali sve rasprostranjeniji. Dok su se ranije za poslovne svrhe koristili mainframe računari, sada je uobičajeno da i najmanje aplikacije rade na više računara.

Knjiga koju preporučujemo za samostalno izučavanje ove oblasti je Distributed Sytems, 3rd Edition, autora Martina van Stina i Endrjua Tanebauma. Zahvaljujući darežljivosti autora, ona je besplatno dostupna onlajn. S obzirom da su distribuirani sistemi oblast koja se brzo menja, ni jedna knjiga ne može vam poslužiti kao potpun vodič, ali van Stinova i Tanebaumova knjiga daje najbolji pregled do sada utemeljenih principa.

Nezavisno od izbora knjige i ostalih resursa za učenje, proučavanje distribuiranih sistema zahteva čitanje studija. Evo dobre liste za početak.

***

Da biste ispratili sve što je iznad navedeno, trebalo bi vam više od godinu dana. Shvatamo da je za mnoge to previše, pa smo spremili i nešto lakšu varijantu koju možete da uradite za početak, iako je preporučljivo da se kad-tad prođete resurse sa liste iznad.

Jedan od najboljih uvoda u računarske nauke — koji nam se toliko svideo da smo mu posvetili i jedan tekst — jeste kurs CS50.

On vam može poslužiti kao sjajan uvod u računarstvo, i dotiče veliki broj korisnih tema.

Naravno, on nije zamena za temeljno izučavanje pojedinačnih oblasti i čitanje knjiga.

Postoji još nešto za šta mnogi iskusni programeri  tvrde da je odlično za postavljanje jakih temelja za razumevanje programiranja. Učenje programskog jezika C.

Zašto baš C?

Danas, teško da ćete naći posao za ovaj programski jezik u Srbiji. Ima ih, ali ne mnogo, i uglavnom se tiču ugrađenih (embedded) sistema. U njemu se pišu i operativni sistemi, a pretpostavljam da mnogima od vas nije ambicija da se time bavite.

Programski jezik C je važan jer se na njemu baziraju skoro svi moderni jezici. On je značajan jer je od svih popularnih jezika jedan od najpribližnijih mašini (shvatićete šta ovo znači kada budete učili o arhitekturi računara). Na osnovu njega nastali su — između ostalih — C++ i Java, pa će vam razumevanje C-a pomoći da kasnije razumete neka od svojstava viših programskih jezika i kako su ona u stvari implementirana.

Još jedna važna stvar koju ćete naučiti kroz upoznavanje sa C jezikom jeste upravljanje memorijom. C vam daje direktan pristup radnoj memoriji, možete da pišete, brišete, alocirate i dealocirate, a nakon igranja sa tim mogućnostima postaće vam mnogo jasnije kako računari i programi u stvari rade.

Suplementirajte ovo nekom dobrom knjigom o osnovama računara ili operativnim sistemima i udarili ste sebi temelj da jednog dana postanete dobar programer, bez potrebe da se naknano vraćate na osnovne koncepte, jer ste ih savladali na vreme.

Kako i odakle da naučite C?

Postoji knjiga koja je klasik, i napisali su je kreatori C jezika. Zove se “C programming language” i dugo je predstavljala obaveznu lektiru za sve programere.

Da biste utvrdili svoje znanje C-a i jednostavnih algoritama (od kojih ćete mnoge naučiti kroz CS50), preporučujem vam neku od platformi za rešavanje problema koje evaluiraju vaš kod. O nekima od njih pisali smo ovde, a za vežbu će vam odlično poslužiti hackerrank.com i projecteuler.com.