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 per partecipare ai soli 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++, Python
  • La let­tu­ra del mate­ria­le didat­ti­co pre­sen­te a que­sto link
  • Oltre ovvia­men­te alla voglia di met­ter­si in gio­co!

Scuole: come partecipare?

  • Contattando alberto.montresor@unitn.it

Attività previste

Padroni del Vapore — Gli algoritmi (e chi li conosce) dominano il mondo

Padrone del vapo­re” è un ter­mi­ne di ori­gi­ne mari­na­re­sca che indi­ca colui che coman­da, ha pote­re asso­lu­to; spre­gia­ti­va­men­te, indi­ca chi coman­da con­di­zio­nan­do i pote­ri pub­bli­ci. 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 dell’enorme 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.

  • Seminario tema­ti­co intro­dut­ti­vo, tenu­to dal Prof. Montresor e offer­to da UniTN.
  • Il semi­na­rio è indi­riz­za­to a tut­ti gli stu­den­ti, non solo di scien­ze appli­ca­te / infor­ma­ti­ca, 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 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.

Date con­cor­da­te

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

Corso introduttivo

Le date al Galilei o al Buonarroti duran­te la stes­sa set­ti­ma­na sono in alter­na­ti­va.

Titolo Galilei Buonarroti Marie-CurieComplessità com­pu­ta­zio­na­le            9/10 15/11Allenamento base 1 5/10 10/10 16/11Allenamento base 2 12/10 17/10 23/11Introduzione ai gra­fi            30/10 29/11Allenamento gra­fi 1 9/11 7/11 30/11Allenamento gra­fi 2 16/11 14/11 7/12Prog. dina­mi­ca            20/11 13/12Allenamento PD 1 7/12 5/12 14/12Allenamento PD 2 14/12 12/12 21/12

Materiali

Titolo Link
Seminario “Padroni del vapo­re” [PDF]
Analisi com­ples­si­tà algo­rit­mi [PDF]
Grafi [PDF]
Programmazione Dinamica [PDF]

Corso avanzato

Le date pre­ci­se saran­no comu­ni­ca­te a dicem­bre

6 incon­tri di 2h con i tutor, solo alle­na­men­ti, con solu­zio­ni a richie­sta degli stu­den­ti (rac­co­glien­do le esi­gen­ze qual­che gior­no pri­ma).
Periodo: gen­na­io-mar­zo

Dove

  • Il semi­na­rio è offer­to nel­le scuo­le par­te­ci­pan­ti (pre­via dispo­ni­bi­li­tà tem­po­ra­le del rela­to­re), oppu­re in sede al Dipartimento di Ingegneria e Scienza dell’Informazione (Povo-Trento)
  • Le lezio­ni si svol­go­no al Liceo Galilei, aper­te a tut­ti.
  • 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]
Indian Computing Olympiad [Link]