UNIVERSITATEA BABEŞ-BOLYAI Facultatea de …lauras/test/docs/school/FP/2013-2014/lectures/... ·...

FUNDAMENTELE

PROGRAMĂRII

Laura Dioşan

INTRODUCERE

UNIVERSITATEA BABEŞ-BOLYAI

Facultatea de Matematică şi Informatică

Sumar

Elemente organizatorice

Scopul activității

Conținut curs

Activități și evaluare

Dezvoltarea proceselor de programare

Ce este programarea?

Elementele de bază ale unui program Python

Un simplu proces de dezvoltare bazat pe funcționalități

Octombrie, 2013 Fundamentele programării - Introducere 2

Elemente organizatorice Profesori coordonatori

Conf. Dr. Laura Dioșan www.cs.ubbcluj.ro/~lauras

Lect. Dr. Vasile Prejmarean http://www.cs.ubbcluj.ro/~per/

Asist. Dr. Camelia Șerban http://www.cs.ubbcluj.ro/~camelia/

Orar Curs – 2 ore/săptămână

Seminar – 2 ore/săptămână

Laborator – 2 ore/săptămână

Informații utile www.cs.ubbcluj.ro/~lauras/

Teaching

Current year

Fundamentele programarii


http://www.cs.ubbcluj.ro/~lauras

http://www.cs.ubbcluj.ro/~per/

http://www.cs.ubbcluj.ro/~camelia/

http://www.cs.ubbcluj.ro/~lauras/




Scopul activității Cunoașterea celor mai importante concepte din

programare

Familiarizarea cu conceptele din software engineering (arhitectură, implementare, întreținere)

Înțelegerea instrumentelor sofware de bază

Învățarea limbajului de programare Python și utilizarea lui pentru implementarea, rularea, testarea și depanarea programelor

Însușirea și îmbunătățirea stilului de programare


Conținut curs Introducere în procesul de dezvoltare software Programare procedurală Programare modulară Tipuri definite de utilizator Principii de dezvoltare a softului Testarea și inspectarea programelor Recursivitate Complexitatea algoritmilor Metode prin divizare Backtracking Algoritmi de căutare Algoritmi de sortare Recapitulare



Activități de laborator – 30% Documentații și programe

În timpul semestrului

Evaluare practică – 30% În sesiune

Evaluare scrisă – 30% În sesiune

Activitate de seminar – 10% În timpul semestrului


Activități și evaluare Toate activitățile sunt obligatorii

Participarea la examen este condiționată de o prezență de 75% la orele de curs

Condiții de promovare:

Nota finală >= 5

Fiecare laborator este evaluat cu o notă între 1 și 10 pe baza explicațiilor, codului sursă, exemplelor, testelor, etc.

Întârzierea în predarea unui laborator este penalizată prin diminuarea notei cu 1p pentru fiecare săptămână de întârziere

Nota pentru laborator se stabilește ca o medie a notelor pentru toate laboratoarele realizate. Laboratoarele nerealizate vor primi nota 1.

Este permisă o singură absență de la orele de laborator (absențele suplimentare vor diminua nota cu 1p/absență)

În cursul unui laborator (2 ore) se pot preda maxim 2 teme de laborator

O temă de laborator copiată este notată cu 0



În sesiunea de restanțe

Se mai pot preda laboratoare, dar nota primită va fi maxim 5

Se poate re-susține examenul practic

Se poate re-susține examenul scris


Dezvoltarea proceselor de programare Ce este programarea?

Hardware Computere (desktop, laptop, etc) și dispozitive înrudite

Software Programe sau sisteme care rulează pe un hardware

Limbaj de programare Notații și reguli pentru definirea sintaxei și semanticii

programelor

Python Un limbaj de programare de nivel înalt

Interpretatorul Python Un program care permite rularea/interpretarea unor alte

programe

Bibliotecile Python Subprograme și tipuri de date deja definite de alți

programatori


Dezvoltarea proceselor de programare Ce este programarea?

Ce fac computerele? Stochează informații și date în

Memoria internă Memoria externă (hard, stick, CD, etc)

Operează Cu ajutorul procesorului

Comunică Prin tastatură, mouse, ecran Conexiuni de tip rețea

Informații și date Informații – interpretarea unor date

Numărul 123 Stringul „abc”

Data – o colecție de simboluri stocate (într-o anumită reprezentare) într-un computer 12 – 1100 „abc” – 97 98 99

Procesarea datelor și informațiilor Dispozitivele de intrare transformă informațiile în date Datele sunt stocate în memorie Dispozitivele de ieșire produc informații din date

Operații de bază ale procesoarelor În reprezentare binară Ex. AND, OR, NOT, XOR, etc.


Dezvoltarea proceselor de programare Elementele de bază ale unui program Python

Exemplu

Elemente lexicale Un program Python poate fi alcătuit din mai multe linii de

cod Comentarii

încep cu # și țin până la sfârșitul liniei încep cu ’’’ și țin mai multe rânduri, până la un nou ’’’

Identificatori secvențe de caractere (litere, cifre, _) care încep cu o

literă sau cu _ Literali

notații pentru valorile constante sau pentru tipuri definite de utilizator


# takes two integers and prints the sum of them a = 3 b = 4 c = a + b print("The sum of ", a, " + ", b, " is ", c)


Modelul de date

Toate datele unui program Python – obiecte

Un obiect are o identitate – adresa lui în memorie un tip – care determină valorile pe care le poate lua

obiectul respectiv, precum și operațiile posibile cu acel obiect

o valoare

Odată creat, identitatea și tipul obiectului nu mai pot fi modificate

Valoarea unor obiecte se poate modifica Obiecte mutabile Obiecte ne-mutabile



Tipuri de date

Conținut

Domeniu – set de valori

Operații posibile

Tipologie

Numere - ne-mutabile

Secvențe – mutabile și ne-mutabile

Mulțimi finite și ordonate, indexate prin numere ne-negative

Dacă s este o secvență, atunci

len(s) – returnează numărul de elemente ale lui s

s[0], s[1], …, s[len(s)-1] – elementele lui s

Exemplu: s = [1, ‘a’, 23, “abc”]



Tipuri de date numerice - ne-mutabile

int

Domeniu: întregi pozitivi și negativi

Operații: +, -, *, /

Literali: 1, 2

bool

Domeniu: adevărat sau false

Operații: logice (and, or, not,...)

Literali: True, False, 1, 0

float

Domeniu: numere reale în dublă precizie

Operații: +, -, *, /

Literali: 3.14, -0.25



Tipuri de date secvențiale

Stringuri – ne-mutabile

Domeniu: șiruri de caractere

Operații: concatentare, căutare

Literali: „abc”


#concatenate a = "abc" b = "xybc" c = a + b print(c) #search n = c.find("bc") print(n) # n = 1 m = c.rfind("bc") print(m) # m = 5




Liste – mutabile

Domeniu: secvențe de elemente (similare sau diferite ca tip) separate prin „,” și încadrate de „[ ]”

Operații

Creare (manuală, range)

Accesare (index, len) și modificare elemente

Eliminare (pop) și inserție (insert) de elemente

Feliere și încapsulare

Utilizare ca stive (append, pop)




Liste – mutabile


# create a = [1, 2, 'a'] print (a) x, y, z = a print(x, y, z) # indices: 0, 1, ..., len(a) - 1 print (a[0]) print ('last element = ', a[len(a)-1]) # lists are mutable a[1] = 3 print(a) # slicing print (a[:2]) b = a[:] print (b) b[1] = 5 print (b) a[len(a):] = [7, 9] print(a) a[:0] = [-1] print(a) a[0:2] = [-10, 10] print(a)

# lists as stacks stack = [1, 2, 3] stack.append(4) print (stack) print (stack.pop()) print (stack) # nesting c = [1, b, 9] print (c) #generate lists using range l1 = range(10) print (l1) l2 = range(0,10) print (l2) l3 = range(0,10,2) print (l3) l4 = range(9,0,-1) print (l4) #list in a for loop l = range(0,10) for i in l: print (i)




Tuple – ne-mutabile

Domeniu: secvențe de valori (similare sau diferite ca tip) separate prin „,”

Operații

Creare (manuală – împachetare) și despachetare

Încapsulare

Tuplu cu 0 elemente și tuplu cu un singur element


# Tuples are immutable sequences # A tuple consists of a number of # values separated by commas # tuple packing t = 12, 21, 'ab' print(t[0]) # empty tuple (0 items) empty = () # sequence unpacking x, y, z = t print (x, y, z)

# tuple with one item singleton = (12,) print (singleton) print (len(singleton)) #tuple in a for t = 1,2,3 for el in t: print (el) # Tuples may be nested u = t, (23, 32) print(u)



Dicționare – ne-mutabile

Domeniu: mulțimi ne-ordonate de perechi (cheie, valoare) cu chei unice

Operații:

Creare

Accesarea valorii pentru o cheie dată

Adăugarea/modificarea/eliminarea unei perechi (cheie, valoare)

Verificarea existenței unie chei


#create a dictionary a = {'num': 1, 'denom': 2} print(a) #get a value for a key print(a['num']) #delete a key value pair del a['num'] print (a)

#set a value for a key a['num'] = 3 print(a) print(a['num']) #check for a key if 'denom' in a: print('denom = ', a['denom']) if 'num' in a: print('num = ', a['num'])



Variabile

Locații de memorie care stochează valori

Au nume, tip și valoare

Introducerea unei variabile într-un program – asignare

Expresii

O combinație de valori, constante, variabile, operatori și funcții care sunt interpretate conform regulilor de precedență, calculate și care produc o altă valoare

Exemple

Expresii numerice: 1+2

Expresii booleene: 1 < 2

Expresii de tip string: ”1”+”2”




Instrucțiuni

Operațiile de bază ale unui program

Tipologie

Asignări

Scop: (re)legarea numelor de valori și pentru a modifica valoarea unor obiecte mutabile

Legarea numelui: x = 1, s = [1, 2]

Re-legarea numelui: x = x + 2, s[0] = 3

Blocuri

Parte a unui program care este executată ca o unitate

Secvență de instrucțiuni

Identiicate prin indentarea liniilor de cod




Instrucțiuni

Atribuiri (asignări)

Condiționale


# takes two integers and prints the sum of them a = 3 b = 4 c = a + b print("The sum of ", a, " + ", b, " is ", c)

# takes two integers and prints the max of them a = 3 b = 4 if (a < b): c = b else: c = a print("The max of ", a, " and ", b, " is ", c)


Instrucțiuni

De ciclare

for

while


# prints the elements of a sequence a = ['Mary', 'has', 'more', 'flowers'] for i in range(len(a)): print(i, a[i])

# prints the elements of a sequence a = ['Mary', 'has', 'more', 'flowers'] for w in a: print(w)

# computes the gcd of two numbers a = 42 b = 18 if a == 0: gcd = b; else: if b == 0: gcd = a else: while a != b: if a > b: a = a - b else: b = b - a gcd = a print("gcd = ", gcd)


Cum se scriu programele?

Roluri în ingineria soft

Programator/dezvoltator

Scrie/dezvoltă programe pentru utilizatori

Client

Cel interesat/afectat de rezultatele unui proiect

Utilizator

Rulează programe pe computer

Procesul dezvoltării unui soft

include construirea, lansarea și întreținerea unui soft

indică pașii care trebuie efectuați și ordinea lor


Dezvoltarea proceselor de programare Pași în rezolvarea unei probleme

Enunț pentru definirea problemei

Cerințe

Scenariu de utilizare a aplicației

Stabilirea funcționalităților și împărțirea lor pe iterații

Identificarea de activităţi (ale fiecărei funcţionalităţi) şi descrierea lor



Enunț pentru definirea problemei

Surtă descriere a problemei

Un profesor (client) are nevoie de o aplicație pentru studenții (utilizatori) care învață să găsească cel mai mic număr prim mai mic decât un număr natural n dat.

Cerințe

Definesc în detaliu ceea ce este necesar din perspectiva clientului, respectiv ce trebuie să facă aplicația

Stabilirea informaților de intrare și ieșire ale aplicației

Date de intrare: n – număr natural

Date de ieşire: cel mai mic număr prim mai mare decât n

Scenariu de utilizare a aplicației


Rulare 1 2 3 4

Intrări 5 0 11 -3

Ieşiri 7 2 13 Daţi un număr natural


Stabilirea funcționalităților și planificarea iterațiilor Funcționalitatea

definită ca o funcție client

exprimată în forma acțiune rezultat obiect

Acțiunea – o funcție pe care aplicația trebuie să o furnizeze

Rezultatul – este obținut în urma execuției funcției

Obiect – o entitate în care aplicația implementează funcția

poate fi implementată în câteva ore – complexitate redusă

F1: găsirea celui mai mic număr prim mai mic decât un număr natural n dat.

Iterația

O perioadă de timp în cadrul căreia se realizează o versiune stabilă și executabilă a unui produs, împreună cu documentația suport

Ajută la planificarea temporală a ansamblului de funcționalități

I1 = F1


Problema este simplă şi nu are decât o singură

funcţionalitate!


Pași în rezolvarea unei probleme

Listă de activităţi (ale fiecărei funcţionalităţi) şi descrierea lor

Recomandări:

Definirea unei activități pentru fiecare operație

Definirea unei activități pentru interacțiunea Utilizator – Program (Interfața utilizator – user interface UI)

Definirea unei activități pentru operațiile UI

Determinarea dependențelor între activități

A1: verificarea calității de număr prim pentru o valoare dată

A2: găsirea celui mai mic număr prim mai mic decât un număr natural n dat

A3: implementarea inițializării unui număr, căutării celui mai mic nr prim mai mic decât n și furnizarea rezultatului

A4: implementarea UI





Cazuri de testare

Specifică un set de date de intrare de test, condiții de execuție și rezultate așteptate necesare pentru evaluarea unei părți de program



Intrări Ieşiri

2 True

6 False

3 True

-2 False

1 False




Implementare



# Description: verifies if the number n is prime # Data: n # Precondition:n - natural number # Results: res # Postcondition:res=FALSE, if n is not prime or res=TRUE, if n is prime if (n < 2): print("no ", n, " is not prime (is composed)") else: d = 2 isPrime = True while (d * d <= n) and (isPrime == True): if (n % d == 0): isPrime = False else: d = d + 1 if (isPrime == True): print("no ", n, " is prime") else: print("no ", n, " is not prime")

Recapitulare





Cursul următor

Programare procedurală

Funcții

Vizibilitatea variabilelor

Transmiterea parametrilor

Cazuri de testare


Materiale de citit şi legături utile

1. Limbajul Python http://docs.python.org/3/reference/index.html

2. Biblioteca standard Python http://docs.python.org/3/library/index.html

3. Tutorial Python http://docs.python.org/3/tutorial/index.html

4. Frentiu, M., H.F. Pop, Fundamentals of Programming, Cluj University Press, 2006, 220 pagini


http://docs.python.org/3/reference/index.html

http://docs.python.org/3/library/index.html

http://docs.python.org/3/tutorial/index.html

Informaţiile prezentate au fost colectate din diferite surse de pe internet, precum şi din cursurile de Fundamentele Programării ţinute în anii anteriori de către:

Lect. Dr. Adriana Guran – www.cs.ubbcluj.ro/~adriana

Lect. Dr. Istvan Czibula - www.cs.ubbcluj.ro/~istvanc

Lect. Dr. Andreea Vescan -www.cs.ubbcluj.ro/~avescan

Lect. Dr. Ioan Lazăr -www.cs.ubbcluj.ro/~ilazar

Octombrie, 2013 35 Fundamentele programării - Introducere

http://www.cs.ubbcluj.ro/~adriana



http://www.cs.ubbcluj.ro/~istvanc



http://www.cs.ubbcluj.ro/~avescan



http://www.cs.ubbcluj.ro/~ilazar



UNIVERSITATEA BABEŞ-BOLYAI Facultatea de …lauras/test/docs/school/FP/2013-2014/lectures/... ·...

Documents

Transcript of UNIVERSITATEA BABEŞ-BOLYAI Facultatea de …lauras/test/docs/school/FP/2013-2014/lectures/... ·...