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

Octombrie, 2013 Fundamentele programării - Introducere 3

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

Octombrie, 2013 Fundamentele programării - Introducere 4

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

Octombrie, 2013 Fundamentele programării - Introducere 5

Activități și evaluare

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

Octombrie, 2013 Fundamentele programării - Introducere 6

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

Octombrie, 2013 Fundamentele programării - Introducere 7

Activități și evaluare

Î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

Octombrie, 2013 Fundamentele programării - Introducere 8

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 9

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

Octombrie, 2013 Fundamentele programării - Introducere 10

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.

Octombrie, 2013 Fundamentele programării - Introducere 11

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

Octombrie, 2013 Fundamentele programării - Introducere 12

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

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

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

Octombrie, 2013 Fundamentele programării - Introducere 13

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

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”]

Octombrie, 2013 Fundamentele programării - Introducere 14

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

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

Octombrie, 2013 Fundamentele programării - Introducere 15

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

Tipuri de date secvențiale

Stringuri – ne-mutabile

Domeniu: șiruri de caractere

Operații: concatentare, căutare

Literali: „abc”

Octombrie, 2013 Fundamentele programării - Introducere 16

#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

Dezvoltarea proceselor de programare

Elementele de bază ale unui program Python

Tipuri de date secvențiale

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)

Octombrie, 2013 Fundamentele programării - Introducere 17

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

Tipuri de date secvențiale

Liste – mutabile

Octombrie, 2013 Fundamentele programării - Introducere 18

# 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)

Dezvoltarea proceselor de programare

Elementele de bază ale unui program Python

Tipuri de date secvențiale

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

Octombrie, 2013 Fundamentele programării - Introducere 19

# 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)

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

Tipuri de date secvențiale

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

Octombrie, 2013 Fundamentele programării - Introducere 20

#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'])

Dezvoltarea proceselor de programare

Elementele de bază ale unui program Python

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”

Octombrie, 2013 Fundamentele programării - Introducere 21

Dezvoltarea proceselor de programare

Elementele de bază ale unui program Python

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

Octombrie, 2013 Fundamentele programării - Introducere 22

Dezvoltarea proceselor de programare

Elementele de bază ale unui program Python

Instrucțiuni

Atribuiri (asignări)

Condiționale

Octombrie, 2013 Fundamentele programării - Introducere 23

# 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)

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

Instrucțiuni

De ciclare

for

while

Octombrie, 2013 Fundamentele programării - Introducere 24

# 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)

Dezvoltarea proceselor de programare

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

Octombrie, 2013 Fundamentele programării - Introducere 25

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

Octombrie, 2013 Fundamentele programării - Introducere 26

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

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

Octombrie, 2013 Fundamentele programării - Introducere 27

Rulare 1 2 3 4

Intrări 5 0 11 -3

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

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

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

Octombrie, 2013 Fundamentele programării - Introducere 28

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

funcţionalitate!

Dezvoltarea proceselor de programare

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

Octombrie, 2013 Fundamentele programării - Introducere 29

Dezvoltarea proceselor de programare

Pași în rezolvarea unei probleme

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

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

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

Octombrie, 2013 Fundamentele programării - Introducere 30

Intrări Ieşiri

2 True

6 False

3 True

-2 False

1 False

Dezvoltarea proceselor de programare

Pași în rezolvarea unei probleme

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

Implementare

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

Octombrie, 2013 Fundamentele programării - Introducere 31

# 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

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 32

Cursul următor

Programare procedurală

Funcții

Vizibilitatea variabilelor

Transmiterea parametrilor

Cazuri de testare

Octombrie, 2013 Fundamentele programării - Introducere 33

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

Octombrie, 2013 Fundamentele programării - Introducere 34

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