FIŞA DISCIPLINEI

1. Date despre program 1.1 Instituţia de învăţământ superior Universitatea de Vest din Timişoara 1.2 Facultatea / Departamentul Chimie-Biologie-Geografie / Departamentul de Geografie 1.3 Catedra Geografie 1.4 Domeniul de studii Geografie 1.5 Ciclul de studii Masterat 1.6 Programul de studii / Calificarea Sisteme informatice geografice (SIG)

2. Date despre disciplină 2.1 Denumirea disciplinei Introducere in programare 2.2 Titularul activităţilor de curs Lector. dr. Bonchis COSMIN 2.3 Titularul activităţilor de seminar Lector. dr. Bonchis COSMIN 2.4 Anul de studiu I 2.5 Semestrul 1 2.6 Tipul de evaluare E 2.7 Regimul disciplinei Ob

3. Timpul total estimat (ore pe semestru al activităţilor didactice) 3.1 Număr de ore pe săptămână 4 din care: 3.2 curs 2 3.3 seminar/laborator 2 3.4 Total ore din planul de învăţământ 56 din care: 3.5 curs 28 3.6 seminar/laborator 28 Distribuţia fondului de timp: ore Studiul după manual, suport de curs, bibliografie şi notiţe 15 Documentare suplimentară în bibliotecă, pe platformele electronice de specialitate / pe teren 15 Pregătire seminarii / laboratoare, teme, referate, portofolii şi eseuri 15 Tutoriat 15 Examinări 9 Alte activităţi…………………………………… - 3.7 Total ore studiu individual 144 3.8 Total ore pe semestru 200 3.9 Numărul de credite 8

4. Precondiţii (acolo unde este cazul) 4.1 de curriculum • Informatica generală 4.2 de competenţe • Notiuni de baza de utilizare calculatoarelor

5. Condiţii (acolo unde este cazul) 5.1 de desfăşurare a cursului • cel puţin 50% prezenţă la activităţile de curs;

5.2 de desfăşurare a seminarului/laboratorului • Prezenţă obligatorie. Se admit maximum 3 absenţe • îndeplinirea integrală a obligaţiilor la lucrările de laborator

6

150

94

20

20

25

20

6. Competenţele specifice acumulate Co

mpete

nţe

profe

siona

le • Cunoaşterea conceptelor utilizate în informatică; • Înţelegerea funcţionării unui algoritm; • Realizarea algoritmilor în pseudocod; • Analiza complexităţii şi corectitudinii unui cod; • Implementarea şi testarea unui program • Dezvoltarea unui spirit critic şi de analiză în cadrul studenţilor; aprecierea avantajelor utilizării unei

gândiri algoritmice • Includerea studenţilor în echipe de studiu pentru realizarea proiectelor propuse;

Comp

etenţe

tra

nsve

rsale

• Aplicarea strategiilor de muncă eficientă şi responsabilă, pe baza principiilor, normelor şi a valorilor

codului de etică profesională; • Aplicarea tehnicilor de muncă eficientă în echipă multidisciplinară, atitudine etică faţă de grup, respect

faţă de diversitate şi multiculturalitate; acceptarea diversităţii de opinie; • Autoevaluarea nevoii de formare profesională continuă în scopul inserţiei şi adaptabilităţii la cerinţele

pieţii muncii.

7. Obiectivele disciplinei (reieşind din grila competenţelor specifice acumulate) 7.1 Obiectivul general al disciplinei Dezvoltarea cunoștințelor legate de conceptele specifice informaticii

Dezvoltarea unui mod de gândire critic şi algoritmic. 7.2 Obiectivele specifice Trezirea motivaţiei studenţilor pentru utilizarea programării în realizarea aplicațiilor GIS

Formarea unor deprinderi de lucru cu softuri specifice Realizarea de proiecte originale cu metodele învățate

8. Conţinuturi 8.1 Curs Metode de predare Observaţii

1. Introducere in algoritmica. Notiunea de algoritm. Obiectul disciplinei. Proprietati ale algoritmilor. Date si clasificari ale datelor. Prelucrari simple. Prelucrari structurate (secventiale, de decizie, de ciclare).

2. Descrierea algoritmilor. Pseudocod. Descrierea prelucrarilor fundamentale si a datelor structurate. Exemple de algoritmi simpli (calcule sume si produse finite, aproximarea sumelor infinite, prelucrari asupra numerelor intregi, prelucrari asupra tablourilor). Tehnica rafinarii succesive si descompunerea unui algoritm in subalgoritmi.

3. Verificarea corectitudinii algoritmilor. Etapele verificarii corectitudinii algoritmilor. Elemente de analiza formala a corectitudinii: preconditii, postconditii, invarianti, functii de terminare. Regula structurii secventiale, regula structurii alternative, regula structurii repetitive. Exemple: determinarea valorii minime dintr-un tablou, algoritmul lui Euclid.

4. Analiza complexitatii algoritmilor I. Scopul analizei. Resurse analizate. Estimarea timpului de executie (cazul cel mai favorabil, cazul cel mai defavorabil, cazul mediu). Exemple: sume finite, produsul a doua matrici, determinare minim, cautare secventiala.

5. Analiza complexitatii algoritmilor II. Ordin de complexitate. Notatia asimptotica. Proprietati. Analiza asimptotica a

Prelegerea, conversaţia euristică, problematizarea.

structurilor fundamentale. Exemple. Clase de complexitate. 6. Metode elementare de sortare. Problematica. Metoda

insertiei, selectiei si interschimbarii elementelor vecine (pentru fiecare metoda: variante ale algoritmului, verificarea corectitudinii, analiza complexitatii).

7. Tehnica reducerii (decrease and conquer). Principiul de baza. Recursivitate (definitie, exemple, mecanismul apelului recursiv, verificarea corectitudinii, analiza complexitatii, teorema master). Exemple: calcul factorial, generarea permutarilor, turnurile din Hanoi

8. Tehnica divizarii (divide and conquer). Principiul de baza. Exemple: cautare binara, determinarea celor mai apropiate doua puncte. Utilizarea teoremei master in analiza algoritmilor de tip divide-et-impera.

9. Aplicatii ale tehnicii de divizare (algoritmi eficienti de sortare si selectie). Sortarea prin interclasare (algoritm, verificare corectitudine, analiza complexitatii). Sortare rapida (algoritm, verificare corectitudine, analiza complexitatii). Problema selectiei.

10. Tehnica alegerii local optimale (greedy). Clasa de probleme. Principiul tehnicii. Verificarea corectitudinii si analiza complexitatii. Exemple: problema submultimii de suma maxima, problema monedelor. Aplicatii: problema rucsacului (fractionara), problema selectarii activitatilor.

11. Tehnica programarii dinamice I . Clasa de probleme. Principiul tehnicii si etapele aplicarii. Complexitatea dezvoltarii ascendente si descendente a relatiilor de recurenta. Exemplu: problema determinarii celui mai lung subsir strict crescator.

12. Tehnica programării dinamice II. Utilizarea functiilor de memorie (tehnica memoizarii). Aplicatii. inmultirea optimala a unui sir de matrici, problema rucsacului (0-1), problema inchiderii tranzitive.

13. Tehnica cautarii cu revenire (backtracking). Clasa de probleme. Principiul metodei si structura generala. Exemple: generarea permutarilor, generarea submultimilor unei multimi, problema plasarii damelor pe tabla de sah, colorarea hartilor, determinarea drumurilor intre doua orase.

14. Tehnica limitarii cautarii (branch-and-bound). Clasa de probleme. Principiul metodei si structura generala. Exemple: problema afectarii job-urilor, problema rucsacului, problema comis-voiajorului.

Bibliografie 1. T.H. Cormen, C.E.Leiserson, R.R. Rivest– Introducere in algoritmi, Mit Press 1990, trad. Computer Libris Agora 2. D. Zaharie – Introducere in proiectarea si analiza algoritmilor, ed. Eubeea, 2008 3. A. Downey,J. Elkner, C. Meyers – How to think like a computer scientist. Learning with Python, Green Tea Press, 2002 8.2 Seminar / laborator Metode de predare Observaţii

1. Introducere in Python. Instalare. Familiarizare cu interfata. Ciclul citire-evaluare-tiparire. Evaluarea expresiilor. Prelucrari matematice simple.

2. Specificarea variabilelor (numerice, logice, siruri de caractere). Reguli de construire a expresiilor. Afisarea explicita a rezultatelor. Specificarea prelucrarilor conditionale si a celor repetitive.

3. Liste si dictionare. Definire si acces la elemente.

Explicaţia ştiinţifică, studii de caz, demonstraţia, aplicații practice

Prelucrari simple asupra listelor. 4. Definirea functiilor. Variabile locale. Specificarea

parametrilor. Apelul functiilor. Returnarea rezultatelor. 5. Lucrul cu fisiere. Tratarea exceptiilor. 6. Prelucrari asupra listelor. Implementarea unor algoritmi

de cautare si sortare 7. Implementarea funcţiilor recursive. Implementarea unor

algoritmi recursivi (generare permutari, generare submultimi).

8. Implementarea unor algoritmi bazati pe tehnica divizarii (cautare binara, algoritmi simpli din geometria computationala)

9. Implementarea sortarii rapide si a sortarii prin interclasare

10. Alte tipuri de date (tuple). Diferenta dintre tipurile modificabile si cele nemodificabile. Implementarea unor algoritmi euristici de tip greedy.

11. Particularitati ale lucrului cu liste multidimensionale. Implementarea unor algoritmi de optimizare bazati pe programare dinamica.

12. Module si pachete. Creare si utilizare. Functiile import si reload. Spatii de nume.

13. Implementarea unor algoritmi bazati pe tehnica cautarii cu revenire.

14. Implementarea unor algoritmi bazati pe tehnica branch and bound.

M. Lutz– Learning Python, 3rd edition, O. Reilly , 2007 S. Tanimoto- Introduction to Python for Artificial Intelligence, IEEE Computer Society, (http://www.info.uvt.ro/~dzaharie) (www.python.org/download)

9. Coroborarea conţinuturilor disciplinei cu aşteptările reprezentanţilor comunităţii epistemice, asociaţiilor

profesionale şi angajatori reprezentativi din domeniul aferent programului Conținutul disciplinei a fost elaborat în conformitate cu planul de învățământ și răspunde exigențelor didactice și științifice corespunzătoare specializărilor similare din alte centre universitare. Stimulează implicarea personală a studenţilor în identificarea unor probleme turistice care se preteaza la analiza spațială in mediul GIS. Facilitează iniţierea din partea studenților a unor contacte şi eventuale colaborări cu organisme și instituții de profil din domeniul GIS. Softurile cu care se lucrează în cadrul aplicaţiilor practice sunt dintre cele mai moderne şi frecvent utilizate în instituţiile de profil.

10. Evaluare

Tip activitate 10.1 Criterii de evaluare 10.2 Metode de evaluare 10.3 Pondere din nota finală

10.4 Curs Înţelegerea şi asimilarea cunoştinţelor

Examinare scrisă din cursul predat şi bibliografia obligatorie

40%

Participare la dezbaterile iniţiate la curs

Evaluare continuă pe parcursul semestrului

10%

10.5 Seminar / laborator

Calitatea conţinutului şi a prezentării proiectului

Prezentare proiect 25%

Verificarea cunoașterii tehnicilor de programare

Examen practic 25%

10.6 Standard minim de performanţă

• Minim nota 5 la laborator; • Minim nota 5 la curs

Data completării

20.09.2013

Semnătura titularului de curs

Semnătura titularului de seminar

Data avizării în catedră/departament

09.10.2013

Semnătura şefului catedrei/departamentului

1.10.201429.09.2015