Palestra di algoritmi

Il Dipartimento di Ingegneria e Scienze dell’Informazione (DISI), in col­la­bo­ra­zio­ne con la rete STAAR, pro­po­ne un per­cor­so di alle­na­men­to per le Olimpiadi dell’Informatica per l’a.s. 2018–2019.

Premessa

Per mol­ti, l’informatica è una mate­ria mera­men­te tec­ni­ca: un’attività da “sma­net­to­ni”, da maghi del­la tec­no­lo­gia. Non è così: l’informatica è soprat­tut­to una scien­za. Per chi uti­liz­za un com­pu­ter, l’informatica è vista come uno stru­men­to per risol­ve­re i pro­pri pro­ble­mi (mate­ma­ti­ci, scien­ti­fi­ci, finan­zia­ri, etc.). Per gli infor­ma­ti­ci, essa è inve­ce la scien­za che stu­dia i meto­di gene­ra­le per risol­ve­re pro­ble­mi (quan­to­me­no, quel­li che sono effet­ti­va­men­te riso­lu­bi­li). Come tale, si occu­pa dei pro­ble­mi in tut­ti i loro aspet­ti: come ven­go­no descrit­ti (model­li), come ven­go­no rap­pre­sen­ta­ti (dati), come ven­go­no risol­ti (algo­rit­mi).
Ad esem­pio, scom­por­re un pro­ble­ma in sot­to­pro­ble­mi, fino a quan­do que­sti si pos­so­no risol­ve­re in manie­ra ele­men­ta­re, e poi ricom­por­re via via le solu­zio­ni inter­me­die fino a rag­giun­ge­re la solu­zio­ne com­ple­ta, è un tipi­co prin­ci­pio infor­ma­ti­co, det­to divi­de-et-impe­ra. Nel cam­po del pro­blem sol­ving, i meto­di riso­lu­ti­vi pro­pri dell’informatica han­no ori­gi­ne dal­la mate­ma­ti­ca, ma la esten­do­no con moda­li­tà nuo­ve, pos­si­bi­li solo gra­zie alla pre­sen­za di un ese­cu­to­re auto­ma­ti­co.
Acquisire e pra­ti­ca­re i meto­di pro­pri dell’informatica si riflet­te quin­di sull’approccio men­ta­le usa­to per risol­ve­re i pro­ble­mi di tut­ti i gior­ni. Comprendere il carat­te­re scien­ti­fi­co dell’informatica ha anche un aspet­to di orien­ta­men­to: signi­fi­ca apprez­za­re il suo lin­guag­gio auto­no­mo, degno di esse­re stu­dia­to quan­to le altre scien­ze.

Obiettivi

Questo per­cor­so di alle­na­men­to ha mol­te­pli­ci obiet­ti­vi:

  • far cono­sce­re agli stu­den­ti lo stu­dio degli algo­rit­mi come uno degli argo­men­ti fon­da­men­ta­li dell’informatica
  • allar­ga­re la pla­tea degli stu­den­ti che par­te­ci­pa­no alle gare del­le Olimpiadi dell’Informatica (indi­vi­dua­li e di grup­po)
  • dare agli stu­den­ti eccel­len­ti una mar­cia in più nel­la riso­lu­zio­ne dei pro­ble­mi, for­nen­do un più ampio insie­mi di nozio­ni di base nel cam­po del­le strut­tu­re dati e dell’algoritmica.

Aspetti di genere

La par­te­ci­pa­zio­ne fem­mi­ni­le alle Olimpiadi è mol­to bas­sa. Per incen­ti­va­re la par­te­ci­pa­zio­ne del­le ragaz­ze, si sono rese dispo­ni­bi­li due stu­den­tes­se, iscrit­te al cor­so di Informatica, bra­ve e capa­ci anche didat­ti­ca­men­te. Costoro potreb­be­ro sia alle­na­re le stu­den­tes­se par­te­ci­pan­ti che esse­re per loro un model­lo di rife­ri­men­to.

Requisiti (solo per chi partecipa agli allenamenti)

  • La cono­scen­za di un lin­guag­gio di pro­gram­ma­zio­ne impe­ra­ti­vo fra quel­li uti­liz­za­ti nel­le Olimpiadi dell’Informatica, qua­li C, C++
  • Oltre ovvia­men­te alla voglia di met­ter­si in gio­co!

Scuole: come partecipare?

  • Contattando alberto.montresor@unitn.it

Piano degli interventi

  • Seminario “Padroni del vapo­re — Gli algo­rit­mi (e chi li cono­sce) domi­na­no il mon­do”: aper­to a tut­ti,  non solo stu­den­ti di infor­ma­ti­ca, ha carat­te­re orien­ta­ti­vo
  • Ciclo di lezio­ni fron­ta­li: rivol­te a stu­den­ti che voglia­no appro­fon­di­re i temi del­la com­ples­si­tà com­pu­ta­zio­na­le, dei gra­fi, del­le tec­ni­che algo­rit­mi­che
  • Allenamenti con tutor: rivol­ti a tut­ti, svol­ti da stu­den­ti UniTN, sicu­ra­men­te la par­te più uti­le per miglio­ra­re i pro­pri risul­ta­ti.

Il potere sociale degli algoritmi — Gli algoritmi (e chi li conosce) dominano il mondo”

 In que­sto semi­na­rio, discu­te­re­mo degli algo­rit­mi alla base dei siste­mi soft­ware che uti­liz­zia­mo tut­ti i gior­ni, qua­li Google e Facebook. Discuteremo del­l’e­nor­me pote­re che si sta con­cen­tran­do nel­le mani di chi con­trol­la tali algo­rit­mi, e del­la tota­le man­can­za di tra­spa­ren­za attor­no ad essi. Vedremo infi­ne come la com­ples­si­tà degli algo­rit­mi che gover­na­no il mon­do sta diven­tan­do tal­men­te alta, che gli auto­ri stes­si sten­ta­no a man­te­ne­re il loro con­trol­lo.

  • Il semi­na­rio è indi­riz­za­to a tut­ti gli stu­den­ti, non solo a quel­li che han­no infor­ma­ti­ca fra le mate­rie di stu­dio, non solo quel­li che han­no già deci­so di par­te­ci­pa­re agli alle­na­men­ti; ha l’obiettivo ambi­zio­so di allar­ga­re la pla­tea di colo­ro che sono inte­res­sa­ti a par­te­ci­pa­re.
  • Il semi­na­rio è offer­to diret­ta­men­te nel­le scuo­le inte­res­sa­te in ora­rio cur­ri­cu­la­re, oppu­re in sede al Dipartimento di Ingegneria e Scienza dell’Informazione (Povo-Trento)
  • Il semi­na­rio non è obbli­ga­to­rio per par­te­ci­pa­re agli alle­na­men­ti e il nume­ro di edi­zio­ni che potran­no esse­re svol­te dipen­de­rà dal­la dispo­ni­bi­li­tà del rela­to­re.
  • Può esse­re svol­to agli ini­zi di otto­bre (al fine di atti­ra­re più stu­den­ti ver­so le olim­pia­di) oppu­re nel perio­do gen­na­io-mag­gio.

Materiali

Titolo Link
Il pote­re socia­le degli algo­rit­mi [PDF]

Ciclo di lezioni frontali

Un ciclo di tre lezio­ni sui temi del­la com­ples­si­tà com­pu­ta­zio­na­le, dei gra­fi, del­le tec­ni­che algo­rit­mi­che. Essendo dedi­ca­ti a stu­den­ti che han­no già scel­to di par­te­ci­pa­re alle olim­pia­di, non mi è pos­si­bi­le ripe­ter­lo più vol­te e quin­di si svol­ge­rà una vol­ta sola, nel­la cit­tà di Trento, in ora­rio pome­ri­dia­no.

Materiali

Titolo Link
Analisi com­ples­si­tà algo­rit­mi [PDF]
Grafi [PDF]
Programmazione Dinamica [PDF]

Allenamenti

Ciclo di 6 incon­tri di 2 ore. Le date pre­ci­se saran­no comu­ni­ca­te in otto­bre, dopo aver pre­so accor­di con le sin­go­le scuo­le.

Gli alle­na­men­ti si svol­go­no in alcu­ne del­le scuo­le par­te­ci­pan­ti, aper­ti a tut­ti, in gior­na­te diver­se per favo­ri­re la par­te­ci­pa­zio­ne, a secon­do del­la dispo­ni­bi­li­tà dei tutor.

Materiali per allenamenti

Titolo Link
Olimpiadi di Informatica — Guida per le sele­zio­ni ter­ri­to­ria­li [Link]
Syllabus e mate­ria­le didat­ti­co [Link]
Indian Computing Olympiad [Link]

 

Edizione 2018/2019

Date con­cor­da­te per il semi­na­rio

Data Orario Istituto Città
2/10 10.40–12.40 Galilei Trento
3/10 10.45–12.45 Rosmini Rovereto
9/10 10.30–12.30 Da Vinci Trento
10/10 10.40–12.40 Marconi Rovereto
11/10 10.40–12.40 Buonarroti Trento

Incontri di alle­na­men­to

Titolo Galilei Buonarroti Marie-Curie
Allenamento base 1 5/10 10/10 16/11
Allenamento base 2 12/10 17/10 23/11
Allenamento gra­fi 1 9/11 7/11 30/11
Allenamento gra­fi 2 16/11 14/11 7/12
Allenamento PD 1 7/12 5/12 14/12
Allenamento PD 2 14/12 12/12 21/12