Fundamentele Programării notițe de curs

Formațiile de studiu: Matematică/Matematică-Informatică, an 1

Coordonator: Lect. Dr. Camelia ȘERBAN

Obiectivele Disciplinei

• Cunoasterea conceptelor de baza ale programarii

• Cunoasterea conceptelor de baza ale ingineriei software (proiectare, implementare, testare, intretinere)

• Invatarea limbajului de programare Python

• Intelegerea notiunii de algoritm

• Cunoasterea unor algoritmi pentru unele clase de probleme: operatiicu vectori, cautare, interclasare, sortare

• Cunoasterea principiilor de proiectare

Evaluarea

•30% activitatea de la laborator

•30% examen practic

•40% examen scris

Toate activitățile sunt obligatorii

Conținutul cursului1. Introducere în procesul de dezvoltare de soft

2. Programarea procedurală

3. Programarea modulară

4. Tipuri definite de utilizator – Programarea orientată obiect

5. Principii de proiectare și programare – Arhitecturi stratificate

6. Principii de proiectare și programare – Diagrame UML

7. Testarea și inspectarea programelor

8. Recursivitate

9. Complexitatea algoritmilor

10. Algoritmi de căutare și complexitatea lor

11. Algoritmi de sortare și complexitatea lor

12. Metoda Backtracking

13. Metoda Divizării

14. Recapitulare

Introducere în procesul de dezvoltare de soft

• Ce este programarea?

• Elementele de bază ale unui program Python

• Cum scriem programe?

Ce este programarea?•Hardware and software

• 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

• Interpretorul Python • Un program care permite rularea/interpretarea unor alte programe

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

Ce este programarea?

• Ce fac computerele? • Stochează informații și date în memoria internă si/sau 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. )

Elemente de bază ale unui program PythonExemplu

• 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

# Reads two integers and prints the sum of thema = input("Enter the first number: ")b = input("Enter the second number: ")c = int(a) + int(b)print("The sum of ", a, " + ", b, " is ", c)

Elemente 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 șioperaț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

Elementele de bază ale unui program Python• Tipuri de date standard

Tipurile clasifică valori. Un tip de dată este definit prin domeniu (un set de valori) si de operatiile pe acele valori

• Numerice (ne-mutabile)• int

• Domeniu: întregi pozitivi și negativi • Operații: +, -, *, /, //, **, % comparare:==,!=,<, > operații pe biți: |, ^,• &, <<, >>, ~• 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

Elemente de bază ale unui program Python• Tipuri de date standard – continuare

• Secvențiale - 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”]

• Stringuri – ne-mutabile• Domeniu: șiruri de caractere

• Operații: concatentare, căutare

• Literali: „abc”

• Liste – va urma

Elemente 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 – atribuire

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

Elemente de bază ale unui program Python

• Instrucțiuni - Operațiile de bază ale unui program (un program esteo secvență de instrucțiuni)• Atribuirea

• 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

• Identicate prin indentarea liniilor de cod

Elemente de bază ale unui program Python

def este_bisect(an):

"""

determina daca un an este bisect

Parametrii: a-nr natural

Returneaza: True, daca a este bisect

False, altfel

"""

if an % 400 == 0:

return 1

elif an % 100 == 0:

return 0

elif an % 4 == 0:

return True

else:

return False

print(este_bisect(2014))

def este_bisect_v2(an):

"""

determina daca un an este bisect

Parametrii: a-nr natural

Returneaza: True, daca a este bisect

False, altfel

"""

if (an%400==0) or (an % 4==0 and an%100!=0):

return True

else:

return False

print(este_bisect_v2(2014))

Instrucțiunea if

Elemente de bază ale unui program PythonInstrucțiunea while

def invers(n):

'''

returneaza inversul unui numar

parametrii: n-nr natural

returneaza: numarul obtinut cu cifrele lui n in ordine inversa

'''

n_inversat=0

while n>0: n_inversat=n_inversat*10+n%10

n=n//10

return n_inversat

print(invers(1234))

Instrucțiunea Forfor i in range(5):

print (i)

for i in range(10,50,5):

print (i)

for i in range(10,5,-1):

print (i)

for i in reversed(range(10,20)):

print (i)

for i in (4,6,9,11):

print (i)

for i in [1,2,4,5]:

print (i)

s = for i in "Aprogramatoarei":

print (i)

Cum scriem programe? • 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 de dezvoltare de soft• include construirea, lansarea și întreținerea unui soft

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

Proces incremental de dezvoltare, bazat pefunctionalități(A simple Features driven development process)

• Definirea problemei• Un profesor de matematică (client) are nevoie de o aplicație pentru elevi (utilizatori) care învață numerele raționale.

Programul va ajuta elevii să facă operații aritmetice de bază.

• Stabilirea cerințelor/funcționalități• Definesc în detaliu ceea ce este necesar din perspectiva clientului, respectiv ce trebuie să facă aplicația

• Principii in stabilirea cerintelor/Requirements guidelines

• Cerințele bine definite conduc la dezvoltarea unui sistem soft conform asteptarilor clientului.

• Identifică funcționalitățile pe care aplicația le oferă

• Funcționalitățile trebuie să clarifice ambiguitățile din enunțul problemei.

Funcționalitatea (feature) - definită ca o funcție client, este exprimată în forma

<acțiune> <rezultat> <obiect > ex. Calculate [action] the total [result] of a sale [object]. • 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 cadrul aplicației ce implementează funcția

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

Proces incremental de dezvoltare, bazat pe functionalități

• Planificarea funcționalităților pe iterații

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

La terminarea iterației avem o versiune funcțională care face ceva util clientului.

Iteration Planned features

I1 F1. Add a number to calculator

I2 F2. Clear calculator

I3 F3. Undo the last operation (user may repeat this operation)

Proces incremental de dezvoltare, bazat pe functionalități

• Modelarea iterațiilor• Definirea sarcinilor/activităților (tasks) pentru fiecare funcționalitate

• Principii pentru definirea sarcinilor

• Definirea unei activități pentru fiecare operație care nu este deja oferiră de platforma(Python) T1, T2

• Definirea unei activități pentru interacțiunea Utilizator – Program (user interface UI) T4

• Definirea unei activități pentru operațiile UI – T3

• Determinarea dependențelor între activități T4 --> T3 --> T2 -->T1

• Planifică sarcinile în funcție de dependențele dintre acestea

T1 Compute the greatest common divisor of two integers

T2 Add two rational numbers

T3 Implement calculator: init, add, and total

T4 Implement user interface

Proces incremental de dezvoltare, bazat pe functionalități• Modelarea iterațiilor - cont

• Scenarii de utilizare –ajută programatorul să înțeleagă mai bine ce trebuie implementat. Un scenariu de utilizare afișează posibile interacțiuni între program și utilizator

User Program Description

a 0 Shows total

b 1/2 Add number to calculator

c 1/2 Shows total

d 2/3 Add number to calculator

e 5/6 Shows total

f 1/6 Add number to calculator

g 1 Shows total

h -6/6 Add number to calculator

i 0 Shows total

Proces incremental de dezvoltare, bazat pe functionalități• Modelarea iterațiilor - cont

• Cazuri de testare (Test Case) - Specifică un set de date de test, condiții de execuție șirezultatele așteptate necesare pentru evaluarea unei părți de program

• Cazuri de testare pentru sarcina/task T1 (cel mai mare divizor comun a două numere)

Input params: a, b gcd(a, b): c, where c is the greatest common divisor of a and b

2 3 1

2 4 2

6 4 2

0 2 2

2 0 2

24 9 3

-2 0 ValueError

0 -2 ValueError

Un process simplu de dezvoltare bazat pe functionalitățiModelarea iterațiilor continuare - Implementare T1

def gcd(a, b):"""returneaza cel mai mare divizor comun a doua numere

naturaleArunca: ValueError daca parametrii sunt numere negative

sau ambele nule"""if a < 0 or b < 0:

raise ValueError("a and b must be greater than 0")if a == 0 and b == 0:

raise ValueError("gcd(0, 0) is undefined")if a == 0:

return belse:

if b == 0:return a

else:while a != b:

if a > b:a = a - b

else:b = b - a

return a

def test_gcd():

assert gcd(0, 2) == 2

assert gcd(2, 0) == 2

assert gcd(2, 3) == 1

assert gcd(2, 4) == 2

assert gcd(6, 4) == 2

assert gcd(24, 9) == 3

try:

gcd(-2, 0)

gcd(0, -2)

gcd(0, 0)

assert False

except ValueError:

assert True

test_gcd()

Referinte bibliografice

• The Python language reference. http://docs.python.org/py3k/reference/index.html

• The Python standard library. http://docs.python.org/py3k/library/index.html

• The Python tutorial. http://docs.python.org/tutorial/index.html