Algoritmi e Strutture Dati

Corso 2023/2024

Le lezio­ni rico­min­cia­no mar­te­dì 12 Settembre, 2023.

Le lezio­ni si ter­ran­no in pre­sen­za, in aula A101 , e in strea­ming sin­cro­no su zoom (tro­va­te link zoom in que­sto docu­men­to, acces­si­bi­le solo tra­mi­te account UniTN).

Per par­te­ci­pa­re al cor­so è necessario:

• Iscriversi al cana­le tele­gram del cor­so. Tutti gli avvi­si (lezio­ni, assen­ze, esa­mi, pub­bli­ca­zio­ni di risul­ta­ti, etc.) ven­go­no noti­fi­ca­ti attra­ver­so il grup­po fino a Settembre 2024. Al ter­mi­ne del­l’an­no acca­de­mi­co, il grup­po reste­rà atti­vo per annun­ci di inte­res­se gene­ra­le (hac­ka­thon, ban­di, oppor­tu­ni­tà, etc.) men­tre chi non ha anco­ra com­ple­ta­to l’e­sa­me dovrà spo­star­si sul grup­po del 24/25.
• Al cana­le è asso­cia­to un grup­po di discus­sio­ne, dove è pos­si­bi­le discu­te­re di tut­to, maga­ri con­cen­tran­do­si sugli algo­rit­mi però.
• Compilare que­sto que­stio­na­rio, che mi ser­ve per ave­re una foto­gra­fia di quan­te per­so­ne sono inte­res­sa­te a fare l’esame.

Tutte le lezio­ni fron­ta­li degli anni scor­si sono già dispo­ni­bi­li onli­ne in que­sto sito, in due for­ma­ti: (1) le regi­stra­zio­ni del 2020/21 (par­te in uffi­cio, par­te in aula) e (2) le regi­stra­zio­ni degli anni pre­ce­den­ti (in aula). Delle due, le pri­me sono più aggior­na­te, le secon­de sono più “vive” (IMHO). In entram­bi i casi è sta­to fat­to un po’ di edi­ting per taglia­re le par­ti inutili.

Metterò a dispo­si­zio­ne le regi­stra­zio­ni anche que­st’an­no (in for­ma non edi­ta­ta) entro il wee­kend di ogni set­ti­ma­na qui; atti­ve­rò una con­nes­sio­ne zoom per chi vuo­le par­te­ci­pa­re in manie­ra sincrona.

Tuttavia, pri­ma del covid, le lezio­ni di eser­ci­ta­zio­ne e di labo­ra­to­rio era­no mol­to inte­rat­ti­ve, par­te­ci­pa­te e basa­te sul­la discus­sio­ne fra tut­ti; inten­do tor­na­re a quel model­lo, e que­sto signi­fi­ca che saran­no scar­sa­men­te frui­bi­li a distan­za, per la dif­fi­col­tà di regi­stra­re le mie inte­ra­zio­ni con gli stu­den­ti. Inoltre, la mia atten­zio­ne sarà comun­que rivol­ta agli stu­den­ti in aula, per­ché per­so­nal­men­te sono con­vin­to che l’u­ni­ver­si­tà sia soprat­tut­to una comu­ni­tà che si for­ma nel­le aule, non online.

Si può pas­sa­re il cor­so eser­ci­tan­do­si da soli? Certamente sì, il mate­ria­le onli­ne è tan­tis­si­mo. E’ fat­ti­bi­le per tut­ti? Sicuramente no, il cor­so è impe­gna­ti­vo e mol­ti fan­no fati­ca a pas­sar­lo, per­ché pen­sa­no che si pos­sa pas­sa­re il cor­so “leg­gen­do” e “stu­dian­do”, in manie­ra pas­si­va; inve­ce biso­gna esse­re atti­vi, risol­ve­re pro­ble­mi, scri­ve­re codice.

Ritengo che il modo miglio­re per capi­re se si è sul­la stra­da giu­sta è con­fron­tar­si con gli altri. Quest’affermazione fa par­te del mio “cre­do” didattico.

Le comu­ni­ca­zio­ni non avver­ran­no tra­mi­te piat­ta­for­ma mood­le, la qua­le con­ter­rà solo un link a que­sto sito.

Organizzazione

• Per gli stu­den­ti del Corso di Laurea in Informatica, il cor­so è annua­le (!!):  un uni­co cor­so di 12 cre­di­ti, che ini­zia a set­tem­bre e fini­sce a mag­gio (145004). E’ divi­so in due par­ti, la par­te A nel pri­mo seme­stre e la par­te B nel secon­do semestre.
• Per gli stu­den­ti del Corso di Laurea in Matematica, esi­ste la ver­sio­ne da 6 cre­di­ti (145946), che si svol­ge nel pri­mo seme­stre; oppu­re la ver­sio­ne inte­ra da 12 cre­di­ti. Se sie­te anco­ra inde­ci­si, ecco due righe sul per­ché uno stu­den­te di Matematica dovreb­be stu­dia­re Algoritmi e Strutture Dati.
• Per gli stu­den­ti del Corso di Laurea in Ingegneria Informatica, del­le Comunicazioni ed Elettronica (ICE), è pos­si­bi­le sce­glie­re come opzio­na­le il cor­so inte­ro (145004, dal mani­fe­sto di Informatica), oppu­re solo la pri­ma par­te (145946, dal mani­fe­sto di Matematica). Se sie­te anco­ra inde­ci­si, ecco due righe sul per­ché uno stu­den­te di ICE dovreb­be stu­dia­re Algoritmi e Strutture Dati.

Sommario

Il cor­so ha lo sco­po di pre­sen­ta­re i con­cet­ti fon­da­men­ta­li del­l’al­go­rit­mi­ca, ovve­ro quel­la bran­ca del­l’in­for­ma­ti­ca che si occu­pa del­la defi­ni­zio­ne e la pro­get­ta­zio­ne degli algo­rit­mi, l’a­na­li­si del­la loro cor­ret­tez­za e del­la loro effi­cien­za, la dimo­stra­zio­ne del­le loro limi­ta­zio­ni e com­ples­si­tà, e lo stu­dio dei dati da essi elaborati.

Verranno pre­sen­ta­ti algo­rit­mi per risol­ve­re alcu­ni pro­ble­mi fon­da­men­ta­li (qua­li ad esem­pio l’or­di­na­men­to), tec­ni­che per l’a­na­li­si degli algo­rit­mi (nota­zio­ne asin­to­ti­ca e ricor­ren­ze),  strut­tu­re dati ele­men­ta­ri (qua­li liste, pile, code), strut­tu­re dati non linea­ri (albe­ri e gra­fi) e gli algo­rit­mi ad esse col­le­ga­ti, strut­tu­re dati avan­za­te (albe­ri red-black, heap, tabel­le hash, etc.). Particolare enfa­si ver­rà dedi­ca­ta alle meto­do­lo­gie di pro­get­ta­zio­ne di algo­rit­mi (divi­de et impe­ra, pro­gram­ma­zio­ne dina­mi­ca, meto­do gree­dy, back­trac­king, ricer­ca locale).

Prerequisiti

Si assu­me che lo stu­den­te cono­sca i con­cet­ti pre­sen­ta­ti nei cor­si di Analisi, Geometria ed Algebra Lineare, Fondamenti Matematici per l’Informatica, Programmazione 1, più qual­che ele­men­to di cal­co­lo del­le probabilità.

Per gli stu­den­ti del cor­so di lau­rea in Matematica, le mag­gio­ri cono­scen­ze nel cam­po del­la mate­ma­ti­ca com­pen­sa­no la mino­re espe­rien­za nel cam­po del­la pro­gram­ma­zio­ne, ren­den­do l’e­sa­me affron­ta­bi­le sen­za problemi.