WikiLabs - Contribuții utilizator [ro]

Tutorial Quartus II

2017-03-10T09:36:20Z

Ccioflan: /* 1. Crearea unui proiect */

'''Programarea plăcii experimentale DE1 cu ajutorul programului Quartus II (versiunea 13.0sp1)

Exemplu: sinteza unui sumator pe 4 biți.'''

Pentru a deschide aplicația Quartus II puteți folosi:

- shortcut-ul de pe ecran

- fișierul executabil din locația de instalare

- meniul de programe

Etapele:

=1. Crearea unui proiect=
Atunci când deschidem programul Quartus II apare un ecran de întâmpinare, unde avem opțiunea „Create new project”. Dacă nu vedem această fereastră, selectăm „New Project Wizard” din meniul File, sau selectăm File - New și apoi „New Quartus II Project”).
În ambele cazuri, se va deschide Wizard-ul care ne ajută să stabilim setările pentru noul proiect. Dacă apere un ecran de introducere, apăsăm Next (avem posibilitatea de a bifa “Don’t show this introduction again” pentru a trece peste acest pas pe viitor).

==1.1. Numele și locația proiectului==
Primul pas: setarea locației proiectului (working directory) și denumirea proiectului. Proiectul se va salva intr-un director nou, creat de noi in directorul /home/student. Proiectul trebuie să aibe un nume, care este de obicei același cu entitatea top-level design (care se completează automat când scriem numele proiectului). Dacă în locația proiectului mai sunt și alte proiecte Quartus II, apare un ecran de avertizare.
Proiectul din acest tutorial se numește Adder și entitatea top-level design se numește tot Adder.
Veți folosi nume adecvate pentru proiectul pe care îl implementați.

==1.2. Adăugarea unor fișiere==
Dacă în proiectul nostru vom folosi fișiere pe care le-am scris anterior, le putem adăuga de la început în proiect în această fereastră. Dacă nu doriți sa adăugați fișiere deja create proiectului vostru puteți apăsa Next pentru a trece la pasul următor. Se mai pot adăuga fișiere în proiect și ulterior din meniul Settings.

==1.3. Selectarea dispozitivului==
În pasul următor (al treilea ecran din wizard) se selectează dispozitivul care va fi folosit pentru implementare. Selectați Cyclone II la Device Family. Din lista de dispozitive specifice selectati EP2C20F484C7.
(La Target device trebuie sa fie selectată opțiunea „Specific device selected in Available devices list”).
Apăsați apoi Next pentru a trece la pasul următor.

==1.4. Selectarea simulatorului==
În pagina 4 din wizard vom menționa alte programe pe care le folosim în proiectare (pentru sinteză, simulare, verificare). De exemplu, dacă vrem să folosim ModelSim, selectăm la Simulation ModelSim pentru Verilog HDL. Putem de asemenea să ne bazăm pe ce pune la dispoziție software-ul Quartus II și să trecem peste acest pas apăsând Next.

După apăsarea butonului Next va apărea ultima fereastră din New Project Wizard în care este desfășurat un rezumat al opțiunilor alese pentru crearea proiectului. După apăsarea butonului Finish proiectul va fi creat.

=2. Elaborarea fișierului sursă (entitatea top-level design)=

Entitatea top-level design este un fișier Verilog sau o schemă.

Dacă ați scris deja fișierele și le-ați adăugat cu Add Files, treceți la etapa următoare. Dacă doriți să adăugați fișiere în această fază (și nu le-ați adăugat anterior), folosiți meniul Assignments -> Settings pentru a adăuga fișiere și apoi treceți la etapa următoare.

In continuare se va explica modul de utilizarea al editorului de text Quartus II.

Exemplu de implementare: vom implementa un sumator pentru numere binare pe 4 biți, care va fi numit Adder.v.

'''Atenție!''' Modulul top-level trebuie să aibă numele specificat anterior, când s-a creat proiectul.

Pentru a utiliza editorul Quartus II, selectați File -> New.

Se va deschide o fereastră în care veți selecta Verilog HDL File, apăsați OK. Se va deschide editorul de text.

Selectați File -> Save As pentru a putea alege numele fișierului. În fereastra care apare, veți scrie numele fișierului - pentru entitatea top level design este cel pe care l-ați ales anterior - și bifați “Add file to current project”. Apăsați Save. Fișierul va fi salvat în directorul proiectului.

Intrati in editor și continuați prin a scrie codul Verilog.

Exemplu:

<syntaxhighlight lang="verilog">

module Adder (

output [4:0] out,

input [3:0] in0,

input [3:0] in1);

assign out = in0 + in1;

endmodule

</syntaxhighlight>

Salvați fișierul folosind File -> Save sau combinația de taste Ctrl-s. Pentru mai multe opțiuni ale editorului puteți accesa Tools-> Options -> Text Editor.

=3. Compilarea=

Selectați Start Compilation în meniul Processing sau apăsați butonul de compilare Start Compilation (cu simbolul folosit de obicei pentru Play) și așteptați rezultatul compilării.

Ignorați mesajele de Warning (avertizări) care apar în timpul compilării - acestea se datorează faptului că nu am fixat anumiți parametri pentru implementare.

Erorile posibile în această fază sunt în principal erori de sintaxă Verilog sau erori datorate faptului că am ales greșit numele modulului top-level.

Pentru corectarea setărilor folositi meniul Settings. De exemplu, se poate modifica entitatea top-level design din meniul Assignments - Settings.

=4. Configurarea pinilor de intrare/ieșire=

'''Adăugarea fișierului de constrângeri (Pin Assignments)'''

În timpul compilării, compilatorul Quartus II alege pinii FPGA pe care vor fi conectate intrările și ieșirile circuitului nostru.
Placa DE1 are conexiunile deja făcute între pinii FPGA și alte componente de pe placă, prin urmare nu putem folosi decât anumiți pini, conform acestor conexiuni.
Pentru intrările circuitelor proiectate de noi putem folosi cele 10 comutatoare și cele butoane ale plăcii.
Pentru ieșiri putem folosi cele 18 leduri (10 leduri roșii și 8 leduri verzi) și afișajul 7 segmente.

De exemplu, vom lega intrarea in0 la switch-urile SW0 - SW3, intrarea in1 la switch-urile SW4 - SW7 și ieșirea out la ledurile LEDR0 - LEDR4.
Consultați tabelul din documentația plăcii pentru corespondența pinilor.

Asignarea pinilor se face folosind Assignment Editor sau Pin Planner. Selectați Assignments -> Assignment Editor. Se va deschide o fereastră ca cea din imaginea următoare:

În acest editor, trebuie să scriem toate porturile circuitului și pinii la care le conectăm.
Este mai simplu să facem această asociere în Pin Planner, unde trebuie să modificăm doar coloana „Location”. Observați că modificările făcute în Pin Planner se salveză automat în Assignement Editor.

Placa DE1 are asignări fixe de pini. Terminarea unui design poate ajuta utilizatorul prin folosirea acelorași asignări de pini pentru proiecte viitoare. Se poate încărca un fișieri de Pin Assignments selectând Assignments -> Import Assignments. (Se poate utiliza fișierul cu toate asignările pinilor de pe placa DE1 – DE1_pin_assignments.csv , editând denumirile). Salvați modificările.
După asignarea pinilor rezultatul va arăta ca în imaginea de mai jos:

Recompilați utilizând butonul Start Compilation și așteptați rezultatul compilării.

=5. Programarea plăcii=

Etapa de programare a plăcii FPGA se desfășoară în felul următor:

Porniți placa folosind butonul roșu.

Atenție: asigurați-vă în acest moment că placa este pornită (cablul de alimentare este conectat, cablul USB este conectat, butonul roșu apăsat, Switch-ul RUN/PROG este pe poziția RUN).

Selectați Tools -> Programmer (sau apăsați pe butonul Programmer) pentru a ajunge la fereastra din figura următoare:

În partea de sus, trebuie să aveți selectat USB-Blaster și Modul JTAG.

Dacă USB-Blaster nu este selectat automat, apăsați pe butonul Hardware Setup și selectați USB-Blaster în fereastra care apare.

Dacă nu apare nici un fișier în fereastră apăsați butonul Add File și selectați fișierul Adder.sof (Acest fișier este creat de compilator). Îl găsiți în folderul proiectului, în folderul Output Files.

Asigurați-vă ca device-ul selectat este EP2C20F484 (în jumătatea de jos a ecranului).

Acum puteți apăsa butonul Start și veți aștepta programarea plăcii. În colțul din dreapta sus al ferestrei aveți un indicator de progres.

Erorile în această fază se pot datora faptului că nu ați setat corect dispozitul în proiect (se poate corecta această setare greșită în meniul Assignements/Device.

După ce programarea a fost finalizată puteți testa funcționarea corectă circuitului utilizând Switch-urile SW0-SW7 și observând rezultatele sumatorului pe ledurile roșii LEDR0-LEDR4.

SDA Lucrarea 5

2016-05-12T21:22:01Z

Ccioflan: /* Săptămâna 2 */

În acest laborator se vor implementa mulțimi cu funcții hash și arbori binari.

= Mulțimea =

Mulțimea este o structură de date abstractă care stochează o colecție de elemente unice în care ordinea nu contează.

[[Fișier:set.png]]

Mulțimea are următoarele proprietăți:
# Datele sunt plasate într-o ordine oarecare stabilită arbitrar de structură.
# Numărul de elemente ce poate fi stocat de structură este nelimitat.
# Elementele stocate în mulțime sunt de același fel.
# Mulțimea poate conține doar elemente unice, în baza unei funcții definite de egalitate. Altfel spus, dacă două elemente sunt egale din punctul de vedere al mulțimii, ele nu pot fi ambele conținute de mulțime.

Mulțimea suportă următoarele operații de bază:
# Interogarea numărului de elemente din mulțime.
# Verificarea dacă mulțimea este goală.
# Adăugarea unui element în mulțime (''put'').
# Verificarea dacă un element există în mulțime (''contains'').
# Eliminarea unui element din mulțime (''remove'').

Pentru a verifica egalitatea a două elemente vom defini o funcție <code>equals</code> care va întoarce 1 dacă cele două argumente sunt egale și 0 dacă nu. Această funcție trebuie să existe pentru orice implementare de mulțime, atunci când elementele nu sunt valori ce pot fi comparate cu operatorul implicit ==:

<syntaxhighlight lang="C">
/**
* Functia verifica daca valorile value1 si value2 sunt egale.
* @param value1 prima valoare de comparat.
* @param value2 a doua valoare de comparat.
* @return 1 daca cele doua valori sunt egale si 0 in rest.
*/
char equals(T value1, T value2);
</syntaxhighlight>

== Implementarea de mulțimi cu funcții hash ==

O funcție hash este o funcție care ia ca argument un șir de bytes de orice dimensiune și întoarce un șir de bytes
de dimensiune fixă ce poartă numele de valoare de hash, cod hash sau pur și simplu hash.

Definiția unei funcții hash este strâns legată de definiția funcției <code>equals</code> astfel încât dacă două elemente e1 și e2 sunt considerate egale (<code>equals(e1, e1) == 1</code>), atunci obligatoriu <code>hash(e1) == hash(e2)</code>.

=== Tipul de date și funcțiile de bază ===

În continuare vom prezenta un exemplu de mulțime pentru elemente de tip "persoană" implementată cu funcții hash. În primul rând vom defini structura ce memorează datele legate de o persoană:

<syntaxhighlight lang="C">
struct Person {
char firstName[30];
char lastName[30];
char idNumber[9]; // seria si numarul de buletin
char address[255];
char birthday[11];
char cnp[14];
};
</syntaxhighlight>

Pentru a implementa o funcție hash pentru variabilele de tip <code>struct Person</code>, avem întâi nevoie să definim operația de egalitate. O persoană își poate schimba numele, buletinul și adresa, și pot exista mai multe persoane cu aceeași dată de naștere, dar ceea ce identifică clar o persoană este codul numeric personal (CNP). Deci vom defini funcția <code>equals</code> să întoarcă 1 dacă cnp-urile celor două argumente de tip <code>struct Person</code> sunt identice:

<syntaxhighlight lang="C">
/**
* Functia intoarce 1 daca CNP-urile celor doua persoane sunt egale.
* @param person1 prima persoana de comparat.
* @param person2 a doua persoana de comparat.
* @return 1 daca CNP-urile celor doua persoane sunt identice.
*/
char equals(struct Person person1, struct Person person2);
</syntaxhighlight>

Mai departe definim funcția hash pentru o Persoană.

Pentru a putea implementa o mulțime cu funcții hash trebuie ca hash-ul maxim să fie o valoare rezonabilă pentru a putea aloca memorie cu dimensiunea valorii respective.

Din motivul de mai sus, și pentru a micșora posibilitatea unei coliziuni de hash ce va micșora performanța structurii, ieșirea funcției hash va fi un număr între 0 și 999999 obținut din ultimele 6 cifre ale CNP-ului convertite din text în număr (pentru conversie puteți folosi funcția [http://www.cplusplus.com/reference/cstdlib/atoi/ atoi]):

<syntaxhighlight lang="C">
/**
* Functie hash pentru structurile de tip Person.
* @param person peroana pentru care se doreste codul hash.
* @return codul hash al persoanei person
*/
unsigned hash(struct Person person);
</syntaxhighlight>

În continuare vom utiliza pentru implementarea unui Hash Set o structură de date de tip secvență împlementată cu liste (LinkedList) și vom folosi funcțiile deja definite de la laboratoarele anterioare:
* [[Fișier:linkedList.h]]
* [[Fișier:linkedList.c]]

=== Structura <code>HashSet</code> ===

Pentru stocarea datelor necesare mulțimii, definim următoarea structură:

<syntaxhighlight lang="C">

#define MAX_HASH 1000000
struct HashSet {
struct LinkedList array[MAX_HASH]; // un vector de liste, una pentru fiecare valoare posibila de hash
unsigned size; // numarul de elemente din multime
};
</syntaxhighlight>

=== Crearea unui <code>HashSet</code>===

Pentru crearea unui <code>HashSet</code>, se definește următoarea funcție:
<syntaxhighlight lang="C">
/**
* Functia creeaza un hashSet nou si intoarce adresa de memorie alocata.
* @return un pointer la o structura de tip HashSet.
*/
struct HashSet * createHashSet();
</syntaxhighlight>

Pentru crearea unui <code>HashSet</code> se urmează următorii pași:
# Se alocă memorie pentru un element de tip <code>struct HashSet</code> folosind funcția corectă pentru reseta memoria la alocare (scrierea ei cu 0).
# Se inițializează <code>size</code> cu 0.
# Se întoarce adresa elementului de tip <code>struct HashSet</code>.

* Complexitate în '''timp''': O(1)
* Complexitate în '''spațiu''': O(MAX_HASH)

=== Interogarea numărului de elemente din mulțime ===

Pentru interogarea numărului de elemente din mulțime definim:

<syntaxhighlight lang="C">
/**
* Functia intoarce numarul de elemente din multime.
* @param set multimea a carei dimensiuni este ceruta.
* @return numarul de elemente din multime.
*/
unsigned hashSetSize(struct HashSet * set);
</syntaxhighlight>

Funcția va întoarce valoarea din câmpul <code>size</code> din structură.

* Complexitate în '''timp''': O(1)
* Complexitate în '''spațiu''': O(1)

Pentru a afla dacă mulțimea este goală definim:

<syntaxhighlight lang="C">
/**
* Functia intoarce 1 dacă mulțimea nu conține nici un element.
* @param set multimea de interes.
* @return 1 dacă mulțimea este goală, 0 în rest.
*/
char hashSetIsEmpty(struct HashSet * set);
</syntaxhighlight>

Funcția va întoarce 1 dacă valoarea din câmpul <code>size</code> este 0.

* Complexitate în '''timp''': O(1)
* Complexitate în '''spațiu''': O(1)

=== Adăugarea unui element în mulțime ===

Pentru operația de adăugare se definește următoarea funcție:

<syntaxhighlight lang="C">
/**
* Functia adauga elementul dat in multime daca acesta nu exista. Daca
* exista deja, functia nu are nici un efect.
* @param set multimea in care trebuie adaugat elementul.
* @param person elementul ce trebuie adaugta.
*/
void hashSetPut(struct HashSet * set, struct Person person);
</syntaxhighlight>

Adăugarea se realizează în felul următor:
# Se aplică funcția hash pe variabila <code>person</code>.
# Folosind valoarea obținută se accesează lista de pe poziția hash-ului din <code>array</code>.
# Se folosește funcția <code>linkedListSearch</code> pentru a verifica dacă <code>person</code> există în listă (funcția <code>linkedListSearch</code> trebuie re-implementată pentru a se folosi de funcția <code>equals</code> pentru compararea elementelor).
# Dacă valoarea întoarsă este -1 atunci <code>person</code> se adaugă în listă și <code>size</code> se incrementează cu 1.

* Complexitate în '''timp''': O(1) best case (fără coliziuni), O(1) average case pentru număr mai mic de 1000000 de persoane, O(n) worst case (același hash pentru poate persoanele).
* Complexitate în '''spațiu''': O(1)

<div class="regula"><span style="color: red; font-weight: bold">Atenție:</span> Deoarece vectorul <code>array</code> conține variabile de tip <code>struct LinkedList</code> și nu pointeri, pentru a folosi funcțiile definite în '''linkedList.h''' e necesară obținerea adresei variabilei de tip <code>struct LinkedList</code> folosind operatorul &.</div>

=== Eliminarea unui element din mulțime ===

Pentru operația de eliminare se definește următoarea funcție:

<syntaxhighlight lang="C">
/**
* Functia elimina elementul dat din multime daca acesta exista. Daca
* nu exista, functia nu are nici un efect.
* @param set multimea din care trebuie eliminat elementul.
* @param person elementul ce trebuie eliminat.
*/
void hashSetRemove(struct HashSet * set, struct Person person);
</syntaxhighlight>

Eliminarea se realizează în felul următor:
# Se aplică funcția hash pe variabila <code>person</code>.
# Folosind valoarea obținută se accesează lista de pe poziția hash-ului din <code>array</code>.
# Se folosește funcția <code>linkedListSearch</code> pentru a verifica dacă <code>person</code> există în listă.
# Dacă valoarea întoarsă este diferită de -1 atunci se folosește funcția <code>linkedListDelete</code> pentru a șterge elementul de pe poziția respectivă și size se decrementează cu 1.

* Complexitate în '''timp''': O(1) best case (fără coliziuni), O(1) average case pentru număr mai mic de 1000000 de persoane, O(n) worst case (același hash pentru poate persoanele).
* Complexitate în '''spațiu''': O(1)

=== Verificarea dacă un element există în mulțime ===

Pentru a verifica dacă un element există în mulțime, se definește următoarea funcție:

<syntaxhighlight lang="C">
/**
* Functia intoarce 1 daca elementul specificat exista in multime.
* @param set multimea in care se cauta elementul.
* @param person elementul cautat.
* @return 1 daca elementul exista in multime, 0 daca nu.
*/
char hashSetContains(struct HashSet * set, struct Person person);
</syntaxhighlight>

Verificarea unui element dacă este sau nu în mulțime se realizează în felul următor:
# Se aplică funcția hash pe variabila <code>person</code>.
# Folosind valoarea obținută se accesează lista de pe poziția hash-ului din <code>array</code>.
# Se folosește funcția <code>linkedListSearch</code> pentru a verifica dacă <code>person</code> există în listă.
# Dacă valoarea întoarsă este diferită de -1 atunci se întoarce 1, altfel se întoarce 0.

* Complexitate în '''timp''': O(1) best case (fără coliziuni), O(1) average case pentru număr mai mic de 1000000 de persoane, O(n) worst case (același hash pentru poate persoanele).
* Complexitate în '''spațiu''': O(1)

=== Ștergerea unui <code>HashSet</code>===

Pentru dezalocarea unui <code>HashSet</code>, se definește următoarea funcție:
<syntaxhighlight lang="C">
/**
* Functia sterge hash set-ul specificat.
* @param set hash set-ul ce trebuie sters.
*/
void deleteHashSet(struct HashSet * set);
</syntaxhighlight>

Pentru ștergerea unui <code>HashSet</code> se urmează următorii pași:
# Se iterează peste tot <code>array</code>-ul, ștergându-se toate nodurile din toate listele.
# Se șterge memoria alocată pentru structura de tip <code>HashSet</code>.

* Complexitate în '''timp''': O(MAX_HASH)
* Complexitate în '''spațiu''': O(1)

== Implementarea mulțimilor cu arbori binari de căutare (Binary Search Trees - BST) ==

Pentru a putea plasa elemente într-o mulțime implementată cu arbori binari de căutare, pe mulțimea acestor elemente
trebuie să existe definită o relație de ordine.

Mulțimile implementate cu arbori binari de căutare, în plus față proprietățile mulțimilor definite mai sus, garantează
faptul că elementele sunt plasate în ordine în mulțime (Ordered Set).

Din acest motiv trebuie definită o funcție care să compare două elemente. Vom numi această funcție <code>compare</code> și se ca comporta similar cu funcția <code>strcmp</code>: va întoarce o valoare pozitivă dacă primul element e mai mare, o valoare negativă dacă al doilea element e mai mare și 0 dacă elementele sunt egale:

<syntaxhighlight lang="c">
/**
* Compara value1 cu value2 si intoarce o valoare corespunzătoare.
* @param value1 prima valoare de comparat.
* @param value2 a doua valoare de comparat.
* @return o valoare pozitivă dacă primul element e mai mare, o
* valoare negativă dacă al doilea element e mai mare și 0 dacă
* elementele sunt egale.
*/
int compare(T value1, T value2);
</syntaxhighlight>

=== Tipul de date și funcțiile de bază ===

În continuare vom prezenta un exemplu de mulțime pentru elemente de tip "server" implementată cu arbori binari de căutare. În primul rând vom defini structura ce memorează datele legate de un server:
<syntaxhighlight lang="c">
struct Server {
/* Numele server-ului in retea - sir de caractere */
char hostname[30];

/* Adresa IP a server-ului o secvență de 4 valori numerice între 0 și 255 (ex: 192.168.1.10) */
unsigned char ipv4[4];

/* Adresa hardware pentru adaptorul de retea - o secventa de 6 bytes, in hexa (ex: 60:57:18:6e:a8:e8). */
char hardwareAddress[6];

/* Tipul procesorului - sir de caractere. */
char cpuType[10];

/* Frecventa procesorului in Gigahertz. */
float cpuFrequencyGhz;

/* Cantitatea de memorie RAM, in Gigabytes. */
float ramMemoryGigaBytes;

/* Capacitatea discului, in Terabytes. */
float diskCapacityTeraBytes;
};
</syntaxhighlight>

Pentru a implementa o mulțime de servere folosind BST, avem întâi nevoie să definim funcția de comparare a două servere. Vom considera că din toate datele definite în structura de mai sus, cea care se schimbă cel mai greu este adresa fizică (hardware) a adaptorului de rețea care de cele mai multe ori este plasat pe placa de bază. Astfel, vom defini funcția compare astfel încât să compare cele două <code>hardwareAddress</code>:
<syntaxhighlight lang="c">
/**
* Compara server1 cu server2 si intoarce o valoare corespunzătoare.
* @param server1 primul server de comparat.
* @param server2 al doilea server de comparat.
* @return o valoare pozitivă dacă primul server are o adresa hardware mai mare, o
* valoare negativă dacă al doilea server are o adresa hardware mai mare și 0 dacă
* adresele hardware sunt egale.
*/
int compare(struct Server server1, struct Server server1);
</syntaxhighlight>

=== Structurile <code>TreeSet</code> și <code>TreeNode</code> ===

Pentru stocarea datelor necesare mulțimii, definim următoarele structuri:

<syntaxhighlight lang="C">
struct TreeNode {
struct TreeNode * parent;
struct TreeNode * left;
struct TreeNode * right;
struct Server value;
};

struct TreeSet {
struct TreeNode * root;
unsigned size;
};
</syntaxhighlight>

=== Crearea unui <code>TreeSet</code> ===

Pentru a crea un <code>TreeSet</code>, definim următoarea funcție:

<syntaxhighlight lang="C">
/**
* Functia aloca memorie si intoarce un pointer la un nou TreeSet.
* @return adresa noului TreeSet.
*/
struct TreeSet * createTreeSet();
</syntaxhighlight>

Funcția trebuie să realizeze următorii pași:
# Se alocă memorie pentru un nou <code>struct TreeSet</code> ce trebuie inițializată automat cu 0.
# Se întoarce adresa alocată.

* Complexitate în '''timp''': O(1)
* Complexitate în '''spațiu''': O(1)

=== Interogarea numărului de elemente din mulțime ===

Pentru interogarea numărului de elemente din mulțime definim:

<syntaxhighlight lang="C">
/**
* Functia intoarce numarul de elemente din multime.
* @param set multimea a carei dimensiuni este ceruta.
* @return numarul de elemente din multime.
*/
unsigned treeSetSize(struct TreeSet * set);
</syntaxhighlight>

Funcția va întoarce valoarea din câmpul <code>size</code> din structură.

* Complexitate în '''timp''': O(1)
* Complexitate în '''spațiu''': O(1)

Pentru a afla dacă mulțimea este goală definim:

<syntaxhighlight lang="C">
/**
* Functia intoarce 1 dacă mulțimea nu conține nici un element.
* @param set multimea de interes.
* @return 1 dacă mulțimea este goală, 0 în rest.
*/
char treeSetIsEmpty(struct TreeSet * set);
</syntaxhighlight>

Funcția va întoarce 1 dacă valoarea din câmpul <code>size</code> este 0.

* Complexitate în '''timp''': O(1)
* Complexitate în '''spațiu''': O(1)

=== Adăugarea unui element în mulțime ===

Pentru operația de adăugare se definește următoarea funcție:

<syntaxhighlight lang="C">
/**
* Functia adauga elementul dat in multime daca acesta nu exista. Daca
* exista deja, functia nu are nici un efect.
* @param set multimea in care trebuie adaugat elementul.
* @param server elementul ce trebuie adaugat.
*/
void treeSetPut(struct TreeSet * set, struct Server server);
</syntaxhighlight>

Adăugarea se realizează în felul următor:
# Dacă dimensiunea mulțimii este 0, se alocă memorie pentru un nod nou <code>newNode</code> în care:
#* <code>value</code> va lua valoarea lui <code>server</code>
#* <code>parent</code>, <code>left</code> și <code>right</code> vor lua valoarea <code>NULL</code>.
# Câmpul <code>root</code> ia valoarea <code>newNode</code>, <code>size</code> se incrementează și funcția se încheie.
# Altfel, se definește o variabilă de tip nod numită <code>tmpNode</code> care se inițializează cu valoarea câmpului <code>root</code>.
# Într-o buclă infinită se realizează următorii pași:
## Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->value</code> și <code>server</code> este 0 (elementele sunt egale), funcția se încheie.
## Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->value</code> și <code>server</code> este mai mare ca 0 și <code>tmpNode->left</code> este diferit de <code>NULL</code>, atunci <code>tmpNode</code> ia valoarea <code>tmpNode->left</code>.
## Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->value</code> și <code>server</code> este mai mare ca 0 și <code>tmpNode->left</code> este egal cu <code>NULL</code>, atunci se alocă memorie pentru un nod <code>newNode</code> nou după regula de la 1, <code>newNode->parent</code> ia valoarea lui <code>tmpNode</code>, <code>tmpNode->left</code> ia valoarea lui <code>newNode</code>, <code>size</code> se incrementează cu 1 și funcția se încheie.
## Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->value</code> și <code>server</code> este mai mică ca 0 și <code>tmpNode->right</code> este diferit de <code>NULL</code>, atunci <code>tmpNode</code> ia valoarea <code>tmpNode->right</code>.
## Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->value</code> și <code>server</code> este mai mică ca 0 și <code>tmpNode->right</code> este egal cu <code>NULL</code>, atunci se alocă memorie pentru un nod <code>newNode</code> nou după regula de la 1, <code>newNode->parent</code> ia valoarea lui <code>tmpNode</code>, <code>tmpNode->right</code> ia valoarea lui <code>newNode</code>, <code>size</code> se incrementează cu 1 și funcția se încheie.

* Complexitate în '''timp''': O(1) best case (element adăugat imediat sub rădăcină), O(log<sub>2</sub>n) average case (arbore echilibrat), O(n) worst case (arbore dezechilibrat).
* Complexitate în '''spațiu''': O(1)

=== Eliminarea unui element din mulțime ===

Pentru operația de eliminare se definește următoarea funcție:

<syntaxhighlight lang="C">
/**
* Functia elimina elementul dat din multime daca acesta exista. Daca
* nu exista, functia nu are nici un efect.
* @param set multimea din care trebuie eliminat elementul.
* @param server elementul ce trebuie eliminat.
*/
void treeSetRemove(struct TreeSet * set, struct Server server);
</syntaxhighlight>

Eliminarea se realizează în felul următor (o descriere în imagini poate fi găsită [http://www.algolist.net/Data_structures/Binary_search_tree/Removal aici] - nu încercați să folosiți codul de pe acea pagină deoarece structurile din platformă diferă și în plus limbajul este C++ și nu va compila):
# Folosind un pointer la nod <code>tmpNode</code>, se folosește tehnica de la căutarea unui element în mulțime pentru a identifica nodul care memorează serverul <code>server</code>. Dacă funcția ajunge la frunze fără a găsi server-ul căutat, funcția se încheie (server-ul nu există în mulțime). Altfel, <code>tmpNode</code> va fi pointer la nodul ce trebuie eliminat. În plus, se va defini o variabilă de tip char <code>direction</code> care la fiecare avansare în arbore va lua valoarea -1 dacă avansarea s-a făcut spre stânga și 1 dacă s-a făcut spre dreapta, astfel încât atunci când <code>tmpNode</code> este pointer la nodul ce trebuie șters, <code>direction</code> va fi 1 sau -1 în funcție de poziția nodului <code>tmpNode</code> față de nodul părinte.
# Dacă <code>tmpNode->left</code> și <code>tmpNode->right</code> sunt ambele <code>NULL</code> (nodul ce trebuie șters este frunză), atunci, dacă <code>direction</code> este -1, <code>tmpNode->parent->left</code> ia valoarea <code>NULL</code>, altfel <code>tmpNode->parent->right</code> ia valoarea <code>NULL</code>, nodul <code>tmpNode</code> este dezalocat, <code>size</code> se decrementează și funcția se încheie.
# Dacă <code>tmpNode->left</code> este <code>NULL</code> și <code>tmpNode->right</code> este diferit de <code>NULL</code> (nodul are un singur copil), atunci, dacă <code>direction</code> este -1, <code>tmpNode->parent->left</code> ia valoarea <code>tmpNode->right</code>, altfel <code>tmpNode->parent->right</code> ia valoarea <code>tmpNode->right</code>, nodul <code>tmpNode</code> este dezalocat, <code>size</code> se decrementează și funcția se încheie.
# Dacă <code>tmpNode->left</code> este diferit de <code>NULL</code> și <code>tmpNode->right</code> este <code>NULL</code> (nodul are un singur copil), atunci, dacă <code>direction</code> este -1, <code>tmpNode->parent->left</code> ia valoarea <code>tmpNode->left</code>, altfel <code>tmpNode->parent->right</code> ia valoarea <code>tmpNode->left</code>, nodul <code>tmpNode</code> este dezalocat, <code>size</code> se decrementează și funcția se încheie.
# Dacă <code>tmpNode->left</code> și <code>tmpNode->right</code> sunt ambele diferite de <code>NULL</code> (nodul ce trebuie șters are doi copii), atunci:
#* Se foloște un al doilea pointer la nod numit <code>minSubtreeNode</code> cu care se caută cea mai mică valoare din subarborele din dreapta nodului <code>tmpNode</code>.
#* <code>tmpNode->value</code> ia valoarea <code>minSubtreeNode->value</code> apoi se șterge <code>minSubtreeNode</code> după aceleași reguli de mai sus.

* Complexitate în '''timp''': O(1) best case (element găsit imediat sub rădăcină), O(log<sub>2</sub>n) average case (arbore echilibrat), O(n) worst case (arbore dezechilibrat).
* Complexitate în '''spațiu''': O(1)

=== Verificarea dacă un element există în mulțime ===

Pentru a verifica dacă un element există în mulțime, se definește următoarea funcție:

<syntaxhighlight lang="C">
/**
* Functia intoarce 1 daca elementul specificat exista in multime.
* @param set multimea in care se cauta elementul.
* @param server elementul cautat.
* @return 1 daca elementul exista in multime, 0 daca nu.
*/
char treeSetContains(struct TreeSet * set, struct Server server);
</syntaxhighlight>

Verificarea unui element dacă este sau nu în mulțime se realizează în felul următor:
# Se definește un pointer la nod numit <code>tmpNode</code> care se inițializează cu valoarea lui <code>root</code>.
# Cât timp <code>tmpNode</code> este diferit de <code>NULL</code>:
#* Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->value</code> și <code>server</code> este 0, se întoarce valoarea 1 (elementul a fost găsit).
#* Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->value</code> și <code>server</code> este pozitiv, <code>tmpNode</code> ia valoarea lui <code>tmpNode->left</code>.
#* Dacă rezultatul funcției <code>compare</code> cu argumentele <code>tmpNode->value</code> și <code>server</code> este negativ, <code>tmpNode</code> ia valoarea lui <code>tmpNode->right</code>.
# Când s-a ieșit din buclă, se întoarce 0 (elementul nu a fost găsit).

* Complexitate în '''timp''': O(1) best case (element găsit în rădăcină), O(log<sub>2</sub>n) average case (arbore echilibrat), O(n) worst case (arbore dezechilibrat).
* Complexitate în '''spațiu''': O(1)

=== Ștergerea unui <code>TreeSet</code>===

Pentru dezalocarea unui <code>TreeSet</code>, se definește următoarea funcție:
<syntaxhighlight lang="C">
/**
* Functia sterge tree set-ul specificat.
* @param set tree set-ul ce trebuie sters.
*/
void deleteTreeSet(struct TreeSet * set);
</syntaxhighlight>

Pentru ștergerea unui <code>TreeSet</code> se urmează următorii pași:
# Se realizează o parcurgere în post-ordine (stânga-dreapta-rădăcină) și se șterg toate nodurile din arbore.
# Se șterge memoria alocată pentru structura de tip <code>TreeSet</code>.

* Complexitate în '''timp''': O(n)
* Complexitate în '''spațiu''': O(1)

= Exerciții =

== Săptămâna 1 ==

<ol>
<li> Dându-se fișierele [[Fișier:linkedList.h]], [[Fișier:linkedList.c]] și header-ele <code>hashSet.h</code> și <code>person.h</code> de mai jos, implementați toate funcțiile definite în două fișiere sursă numite <code>person.c</code> și <code>hashSet.c</code>:
<ul><li> <code>person.h</code>:
<syntaxhighlight lang="C">
#ifndef PERSON_H
#define PERSON_H

struct Person {
char firstName[30];
char lastName[30];
char idNumber[9]; // seria si numarul de buletin
char address[255];
char birthday[11];
char cnp[14];
};

/**
* Functia intoarce 1 daca CNP-urile celor doua persoane sunt egale.
* @param person1 prima persoana de comparat.
* @param person2 a doua persoana de comparat.
* @return 1 daca CNP-urile celor doua persoane sunt identice.
*/
char equals(struct Person person1, struct Person person2);

/**
* Functie hash pentru structurile de tip Person.
* @param person peroana pentru care se doreste codul hash.
* @return codul hash al persoanei person
*/
unsigned hash(struct Person person);

#define T struct Person

#endif
</syntaxhighlight>
</li>
<li> <code>hashset.h</code>:
<syntaxhighlight lang="C">
#ifndef HASH_SET_H
#define HASH_SET_H

#include "linkedList.h"
#include "person.h"

#define MAX_HASH 1000000

struct HashSet {
struct LinkedList array[MAX_HASH]; // un vector de liste, una pentru fiecare valoare posibila de hash
unsigned size; // numarul de elemente din multime
};

/**
* Functia creeaza un hashSet nou si intoarce adresa de memorie alocata.
* @return un pointer la o structura de tip HashSet.
*/
struct HashSet * createHashSet();

/**
* Functia intoarce numarul de elemente din multime.
* @param set multimea a carei dimensiuni este ceruta.
* @return numarul de elemente din multime.
*/
unsigned hashSetSize(struct HashSet * set);

/**
* Functia intoarce 1 dacă mulțimea nu conține nici un element.
* @param set multimea de interes.
* @return 1 dacă mulțimea este goală, 0 în rest.
*/
char hashSetIsEmpty(struct HashSet * set);

/**
* Functia adauga elementul dat in multime daca acesta nu exista. Daca
* exista deja, functia nu are nici un efect.
* @param set multimea in care trebuie adaugat elementul.
* @param person elementul ce trebuie adaugta.
*/
void hashSetPut(struct HashSet * set, struct Person person);

/**
* Functia elimina elementul dat din multime daca acesta exista. Daca
* nu exista, functia nu are nici un efect.
* @param set multimea din care trebuie eliminat elementul.
* @param person elementul ce trebuie eliminat.
*/
void hashSetRemove(struct HashSet * set, struct Person person);

/**
* Functia intoarce 1 daca elementul specificat exista in multime.
* @param set multimea in care se cauta elementul.
* @param person elementul cautat.
* @return 1 daca elementul exista in multime, 0 daca nu.
*/
char hashSetContains(struct HashSet * set, struct Person person);

/**
* Functia sterge hash set-ul specificat.
* @param set hash set-ul ce trebuie sters.
*/
void deleteHashSet(struct HashSet * set);

#endif
</syntaxhighlight>
</li>
</ul>
</li>
<li> Scrieți o altă sursă <code>main.c</code> în care să definiți o funcție <code>struct Person readFromKeyboard()</code> și o altă funcție <code>main</code> care să citească persoane de la tastatură până când numele introdus este egal cu "-" și care să afișeze câte persoane diferite au fost introduse.</li>
</ol>

== Săptămâna 2 ==

<ol>
<li> Dându-se header-ele <code>treeSet.h</code> și <code>server.h</code> de mai jos, implementați toate funcțiile definite în două fișiere sursă numite <code>server.c</code> și <code>treeSet.c</code>:
<ul><li> <code>server.h</code>:
<syntaxhighlight lang="C">
#ifndef SERVER_H
#define SERVER_H

struct Server {
/* Numele server-ului in retea - sir de caractere */
char hostname[30];

/* Adresa IP a server-ului o secvență de 4 valori numerice între 0 și 255 (ex: 192.168.1.10) */
unsigned char ipv4[4];

/* Adresa hardware pentru adaptorul de retea - o secventa de 6 bytes, in hexa (ex: 60:57:18:6e:a8:e8). */
char hardwareAddress[6];

/* Tipul procesorului - sir de caractere. */
char cpuType[10];

/* Frecventa procesorului in Gigahertz. */
float cpuFrequencyGhz;

/* Cantitatea de memorie RAM, in Gigabytes. */
float ramMemoryGigaBytes;

/* Capacitatea discului, in Terabytes. */
float diskCapacityTeraBytes;
};

/**
* Compara server1 cu server2 si intoarce o valoare corespunzătoare.
* @param server1 primul server de comparat.
* @param server2 al doilea server de comparat.
* @return o valoare pozitivă dacă primul server are o adresa hardware mai mare, o
* valoare negativă dacă al doilea server are o adresa hardware mai mare și 0 dacă
* adresele hardware sunt egale.
*/
int compare(struct Server server1, struct Server server2);

#endif
</syntaxhighlight>
</li>
<li> <code>treeSet.h</code>:
<syntaxhighlight lang="C">
#ifndef TREE_SET_H
#define TREE_SET_H

#include "server.h"

struct TreeNode {
struct TreeNode * parent;
struct TreeNode * left;
struct TreeNode * right;
struct Server value;
};

struct TreeSet {
struct TreeNode * root;
unsigned size;
};

/**
* Functia aloca memorie si intoarce un pointer la un nou TreeSet.
* @return adresa noului TreeSet.
*/
struct TreeSet * createTreeSet();

/**
* Functia intoarce numarul de elemente din multime.
* @param set multimea a carei dimensiuni este ceruta.
* @return numarul de elemente din multime.
*/
unsigned treeSetSize(struct TreeSet * set);

/**
* Functia intoarce 1 dacă mulțimea nu conține nici un element.
* @param set multimea de interes.
* @return 1 dacă mulțimea este goală, 0 în rest.
*/
char treeSetIsEmpty(struct TreeSet * set);

/**
* Functia adauga elementul dat in multime daca acesta nu exista. Daca
* exista deja, functia nu are nici un efect.
* @param set multimea in care trebuie adaugat elementul.
* @param server elementul ce trebuie adaugat.
*/
void treeSetPut(struct TreeSet * set, struct Server server);

/**
* Functia elimina elementul dat din multime daca acesta exista. Daca
* nu exista, functia nu are nici un efect.
* @param set multimea din care trebuie eliminat elementul.
* @param server elementul ce trebuie eliminat.
*/
void treeSetRemove(struct TreeSet * set, struct Server server);

/**
* Functia intoarce 1 daca elementul specificat exista in multime.
* @param set multimea in care se cauta elementul.
* @param server elementul cautat.
* @return 1 daca elementul exista in multime, 0 daca nu.
*/
char treeSetContains(struct TreeSet * set, struct Server server);

/**
* Functia sterge tree set-ul specificat.
* @param set tree set-ul ce trebuie sters.
*/
void deleteTreeSet(struct TreeSet * set);

#endif
</syntaxhighlight>
</li>
</ul>
</li>
<li> Scrieți o altă sursă <code>main.c</code> în care să definiți o funcție <code>struct Server readFromKeyboard()</code> și o altă funcție <code>main</code> care să citească informații legate de servere de la tastatură până când ''hostname''-ul introdus este egal cu "-" și care să afișeze câte servere diferite au fost introduse.</li>
</ol>

CID Seminar 5

2016-04-21T05:11:43Z

Ccioflan: /* Exerciţiul 1 */

În acest seminar veţi învăţa să descrieţi memorii de tip Random Access (RAM) și Read Only (ROM) folosind vectori de date în Verilog.

'''Cuvinte cheie''': memorie, vector, RAM, ROM

'''Sintaxă Verilog''': ''$readmemh'', ''$readmemb'', ''parameter''

Memoriile reprezintă structuri fizice de stocare de date, caracterizate prin două măsuri:
* numărul de cuvinte N;
* numărul de biți ai fiecărui cuvânt stocat, W;
Capacitatea de stocare este NxW biți.

Astfel, veți întâlni deseori terminologia de memorie 1024x8b, ceea ce descrie o memorie cu o capacitate de 1024 de cuvinte a 8 biți fiecare.

Memoriile pot fi clasificate în funcție de capacitatea lor de a suprascrie valorile stocate cu valori noi:
* memoriile Random-Access (RAM) permit și operații de suprascriere a conținutului cuvintelor stocate;
* memoriile Read-Only (ROM) permit doar citirea.

De asemenea, memoriile pot fi clasificate în funcție de caracterul lor sincron sau asincron:
* asincron – citirea se face imediat ce se prezintă comanda;
* sincrone – toate operațiile sunt sincronizate de unul din fronturile semnalului de ceas.
Din considerente de implementare fizică, scrierea este întotdeauna sincronă.

Orice memorie RAM are următorul set de semnale de interfață, care formează un '''port''' al memoriei:
* adresa – intrare – specifică indexul cuvântului pe care îl dorim accesat, pentru scriere sau citire;
* datele pentru scriere – intrare – datele care vor fi scrise la indexul specificat de adresă;
* datele citite – ieșire – datele care au fost citite de la indexul specificat de adresă;
* comanda de scriere – intrare – specifică dacă se dorește scriere sau citire;
* semnalul de ceas.

În funcție de configurația portului de memorie, unele din aceste semnale pot lipsi. De exemplu, un port Write-Only nu va avea date citite. Asemănător, un port Read-Only nu va avea date pentru scriere. Un port Read-Write va avea toate aceste semnale. Adresa este semnalul care definește portul memorie, și nu poate lipsi.

'''Observații''': A nu se face confuzia între porturi ale unui modul Verilog și porturile unei memorii.

==Exerciţiul 1==

Să se descrie în Verilog o memorie RAM cu citire asincronă, de 128 de cuvinte de 8 biți, cu un singur port Read-Write. Se va simula funcționarea memoriei scriind în trei locații de memorie, apoi citind din cele trei locații de memorie și comparând valorile citite cu valorile scrise anterior.

<u>Explicaţie suplimentară</u>

Se va folosi un vector de date în Verilog:

<syntaxhighlight lang="verilog">
reg [W-1:0] memory[0:N-1];
</syntaxhighlight>

În acest exemplu am declarat un vector de date numit memory, care este format din cuvinte de W biți, și are N elemente. Elementele vectorului sunt accesate în următorul fel:
* memory[3] reprezintă elementul 4 al vectorului memory, element care are W biți;
* memory[3][0] reprezintă bitul zero al elementului 4 al vectorului memory.

==Exerciţiul 2==
Să se implementeze o memorie RAM de 128 de cuvinte de 8 biţi cu două porturi: un port de scriere şi un port de citire sincronă. Să se testeze această memorie.

<u>Explicaţie suplimentară</u>

Pentru a putea modifica dimensiunile unei memorii şi a refolosi codul Verilog putem declara ca parametri numărul de biţi de adresă, numărul de locaţii şi dimensiunea cuvântului.
Sintaxa este, de exemplu:
<syntaxhighlight lang="verilog">
parameter adr_size = 7;
</syntaxhighlight>

==Exerciţiul 3==

Să se implementeze o memorie FIFO cu 32 locaţii a câte 4 biţi folosind memoria de la exerciţiul 2. Să se testeze funcţionarea acestei memorii, scriind şi citind succesiv diferite valori.

<u>Explicaţie suplimentară</u>

Memoria FIFO (first-in-first-out) permite citirea datelor numai în ordinea în care au fost scrise. Operaţiile de scriere şi citire nu se fac la orice adresă, prin urmare o memorie FIFO nu are intrare de adresă.

Porturile acestei memorii sunt:

<syntaxhighlight lang="verilog">
module memorie_fifo(
input clock, rst, // semnal de ceas si reset
input write_enable, // comanda de scriere
read_enable, // comanda de citire
input [word_width-1 : 0] data_in, // date de intrare, aici pe 4 biti
output [word_width-1 : 0] data_out, // date de iesire, aici pe 4 biti
output reg empty, // semnal de iesire care este activ cand memoria este goala
full, // semnal de iesire care este activ cand memoria este plina
output reg [adr_size:0] fifo_counter //nr locatii folosite, maxim 32

);
</syntaxhighlight>

==Exerciţiul 4==

Să se iniţializeze conţinutul memoriei de la exerciţiul 3 cu ajutorul funcţiilor de sistem ''$readmemh()'' și ''$readmemb()''.

<u>Explicatii suplimentare</u>

Funcțiile se folosesc conform următorului șablon:
<syntaxhighlight lang="verilog">
$readmem[hb]("fișier de inițializare",numele vectorului,adr1,adr2)
</syntaxhighlight>

Funcțiile citesc date în format hexazecimal sau binar din fisierul specificat, și le încarcă în vectorul specificat din modulul Verilog, începând de la adresa adr1 până la adresa adr2.

Conținutul fișierului ''memorie.txt'' (32 de valori de 4 biți, in hexazecimal, una sub alta):

<syntaxhighlight lang="bash">
1
2
a
f
...
b
</syntaxhighlight>

==TEMA==

1. Să se modifice codul de la exerciţiul 1 pentru a implementa o memorie cu citire sincronă.

2. Să se adauge memoriei descrise anterior (TEMA 1) un al doilea port de citire sincronă (Read-Only), şi să se simuleze citirea simultană din două locaţii diferite ale memoriei, prin cele două porturi, cât şi situaţia în care unul din porturi scrie în o locaţie de memorie în timp ce al doilea port citeşte din aceeaşi locaţie de memorie.

3. Să se implementeze o memorie 512x8b folosind patru memorii 128x8b, conectate corespunzător.

4. Să se implementeze o memorie 128x16b folosind două memorii 128x8b, conectate corespunzător.

==Reguli de bună practică==

Se vor grupa semnalele de interfață ale porturilor, și se vor denumi astfel încât să fie ușor identificabile ca fiind parte din portul respectiv (e.g., addrA, dataA, weA, addrB, dataB, weB)

2015-09-24T17:05:55Z

Ccioflan: /* Operandul */

== Obiective ==

în urma acestui laborator, studentul va fi capabil să:
* înțeleagă cum funcționează o structură decizională;
* scrie programe în C folosind construcții decizionale.

== Structura decizionala ==

Se întâmplă adesea ca evoluția unui program să depindă de un moment prezent. Acel moment prezent poate lua însă diverse forme, rolul programatorului fiind să conducă execuția programului pe calea corectă, pe baza unor condiții. Apare astfel structura decizionala if, care ramifică evoluția programului în funcție de valoarea de adevăr a condiției testate.

=== Schema logică ===
Prima etapă din parcurgerea unei structuri decizionale de tipul if-else o reprezintă testarea condiției logice. în cazul în care aceasta este evaluată ca adevărată se execută instructiunea1, cea asociată ramurii if. în cazul în care condiția logică este evaluată ca falsă se execută instructiunea2, cea asociată ramurii else. După executarea instrucțiunii asociate, structura if-else se încheie și programul se continuă cu linia următoare corpului decizional.

[[Fișier:structura_decizionala.png]]

=== Sintaxă generală ===
a) <syntaxhighlight lang="C">
if (conditie) instructiune;
</syntaxhighlight>
b)<syntaxhighlight lang="C">
if (conditie)
instructiune1;
else
instructiune2;
</syntaxhighlight>
c) <syntaxhighlight lang="C">
if (conditie1)
instructiune 1;
else if (conditie2)
instructiune 2;
else if (conditie 3)
instructiune3;
................................
else
instructiune;
</syntaxhighlight>

=== Asocierea ramurilor if-else===

<div class="regula"> ''' Observație: ''' în cazul în care un if are mai multe ramuri, un else se asociază celui mai apropiat if.</div>
Această observație ne conduce la următoarele două cazuri:

* dacă nu există corpuri de instrucțiuni, un else este legat de if-ul imediat anterior;
<syntaxhighlight lang="C">
if (a > 5)
if (b > a)
printf ("b este mai mare ca 5");
else
printf ("b este intre 5 si a");
</syntaxhighlight>
* dacă există corpuri de instrucțiuni, un else este legat de ultimul if fără pereche.
<syntaxhighlight lang="C">
if (a > 5) {
if (b > a)
printf ("b este mai mare ca 5");
}
else
printf ("a nu este mai mare ca 5");
</syntaxhighlight>

'''Exemplu:'''

Ce va afișa acest program prost indentat?
<syntaxhighlight lang="C">
int number = 4;
double alpha = -1.0;
if (number > 0)
if (alpha > 0)
printf( "Here I am!\n");
else
printf( "No, I’m here!\n");
printf("No, actually, I’m here!\n");
</syntaxhighlight>

== Condiția logică ==

Am stabilit deja că o condiție logică, prin valoarea ei de adevăr, ramifică evoluția programului.

<div class="regula">'''<font color="red"> Atenție:</font>''' Adevărat în C înseamnă orice rezultat diferit de 0 (nul) al unei evaluări, în timp ce despre fals vorbim când o expresie este evaluată la 0 ( nul).
</div>

În C, condiția poate avea mai multe reprezentări, după cum urmează

=== Operandul ===

'''Exemplu:'''
Verificați că un număr citit de la tastatură poate fi numitorul unei fracții.

=== Operația cu operatori relaționali (==, !=, <=, <, >, >=) ===

'''Exemplu:'''
Asociați o valoare variabilei cost funcție de valoarea variabilei distance după cum urmează:
{| class="wikitable"
! colspan="2" |
|-
| style="text-align: center;" |distance
| style="text-align: center;" |cost

|-
| style="text-align: center;" | Intre 0 si 100
| style="text-align: center;" | 5.50
|-
| style="text-align: center" | Peste 100, dar mai putin de 500
| style="text-align: center;" | 8.00
|-
| style="text-align: center;" | Peste 500, dar nu mai mult de 1000
| style="text-align: center;" | 10.50
|-
| style="text-align: center;" | 1000 sau mai mult
| style="text-align: center;" | 13.00

|}

=== Operația cu operatori logici (&&, ||, !, ^) ===

'''Exemplu:'''
Folosind operatori logici, aduceți următoarea structură decizională la forma cea mai simplă:
<syntaxhighlight lang="C">
if (doesSignificantWork) {
if (makesBreakthrough)
nobelPrizeCandidate = true;
else
nobelPrizeCandidate = false;
}
else if (!doesSignificantWork)
nobelPrizeCandidate = false;
</syntaxhighlight>

<div class="regula"> '''Observație:'''Pentru a putea lucra cu operatorii logici, este necesar să ne reamintim modul în care aceștia operează.
{| class="wikitable"
! colspan="5" | Tabelul operatorilor logici
|-
| style="text-align: center;" | a
| style="text-align: center;" | b
| style="text-align: center;" | !a
| style="text-align: center" | a && b
| style="text-align: center" | a ll b
|-
| style="text-align: center" | 1
| style="text-align: center;" | 1
| style="text-align: center;" | 0
| style="text-align: center" | 1
| style="text-align: center" | 1
|-
| style="text-align: center" | 0
| style="text-align: center" | 0
| style="text-align: center;" | 1
| style="text-align: center" | 0
| style="text-align: center" | 0
|-
| style="text-align: center" | 0
| style="text-align: center;" | 1
| style="text-align: center;" | 1
| style="text-align: center" | 0
| style="text-align: center" | 1

|}

</div>
== Alternative la if-else ==

=== Operatorul condițional ( ? : ) ===
Singurul operator ternar din C, operatorul condițional funcționează asemenea unui if cu o singură ramură de tip else if. Sintaxa operatorului condițional este următoarea:
<syntaxhighlight lang="C">
(conditie) ? (instructiune1) : (instructiune2)
</syntaxhighlight>

Aşadar, blocul decizional
<syntaxhighlight lang="C">
if (a>b)
printf ("a este mai mare decat b");
else
printf ("a este mai mic sau egal cu b");
</syntaxhighlight>
poate fi înlocuit astfel:
<syntaxhighlight lang="C">
(a>b) ? ( printf ("a este mai mare decat b")) : ( printf ("a este mai mic sau egal cu b"));
</syntaxhighlight>

=== Structura decizională switch-case ===
Această instrucțiune de decizie este similară unui if cu mai multe ramuri de tip else-if. Sintaxa este următoarea:
<syntaxhighlight lang="C">
switch (variabilaTestata) {
case valoare1: { instructiune1;
[break;]
}
case valoare2: { instructiune2;
[break;]
}
case valoare3: { instructiune3;
[break;]
}
.........................................................................
default: {instructiune;
}
}
</syntaxhighlight>
Valorile ''valoare1'', ''valoare2'' etc. sunt proprii tipului de dată întreg, la fel ca ''variabilaTestata''. Ne reamintim însă că întreg nu înseamnă doar variabile de tip '''int''', astfel că ''variabilaTestata'' poate fi de tip '''char'''.
<div class="regula">'''Observație:''' instrucțiunea ''break'' este opțională. Modul care switch-case funcționează este următorul:

a) se compară valoarea variabilei ''variabilaTestata'' cu ''valoarea1'';

b) dacă cele două sunt egale, se execută ''instructiune1''. Apoi există două cazuri:

i. dacă există ''break;'' structura switch-case se încheie și se sare pe linia urmatoare întregului corp decizional;

ii. dacă nu există ''break;'' execuția se continuă până se întalnește un ''break;'' sau până când se încheie structura switch-case. Până la acel moment se vor executa toate instrucțiunile întâlnite pe parcurs (''instructiune2, instructiune3'' etc.);

c) dacă valoarea variabilei ''variabilaTestata'' nu este egală cu niciuna dintre valorile ''valoare1, valoare2'' etc atunci se execută ''instructiune'', asociată etichetei default.
</div>

Pentru a verifica echivalența dintre if-else și switch-case, rezolvați folosind ambele structuri decizionale următoarea problemă:

'''Exemplu:'''
Un microbist vrea să afle situația Grupei F de calificare la EURO2016. Astfel, el va introduce o cifră pentru a vedea ce "națională" ocupă acel loc. Folosind următoarea listă, informați-l corect pe suporter.

1. Irlanda de Nord
2. România
3. Ungaria
4. Finlanda
5. Insulele Feroe
6. Grecia

== Exerciții ==

1. Ce va afișa următorul program?
<syntaxhighlight lang="C">
void main(){
int a=100;
if(a>10)
printf("Tiberiu Soare\n");
else if(a>20)
printf("Horia Andreescu\n");
else if(a>30)
printf("Iosif Ion Prunner\n");
}
</syntaxhighlight>
a) Tiberiu Soare
b) Horia Andreescu
c) Tiberiu Soare
Horia Andreescu
Iosif Ion Prunner
d) Compilation error: More than one conditions are true
e) Niciuna dintre cele de mai sus.

2. Ştiind că un student primește 350 lei/lună dacă are media cel puțin 8.50, 450 lei/lună pentru o medie mai mare sau egală cu 9.50 și 600 lei/lună dacă are media cel puțin 9.70, scrieți un program prin care studentul să afle ce bursă urmează să primească (media va fi citită de la tastatură).

3. Ce va afișa următorul program?
<syntaxhighlight lang="C">
#include<stdio.h>
void main(){
int m=5,n=10,q=20;
if(q/n*m)
printf("Bill Gates\n");
else
printf("Amancio Ortega\n");
printf("Carlos Slim Helu\n");
}
</syntaxhighlight>
a) Bill Gates
b) Amancio Ortega
Carlos Slim Helu
c) Run time error
d) Compilation error
e) Niciuna din cele de mai sus

4. Ce va afișa următorul program?
<syntaxhighlight lang="C">
#include<stdio.h>
void main(){
int a=5,b=10;
if(++a||++b)
printf("%d %d",a,b);
else
printf("Wayne Rooney");
}
</syntaxhighlight>
a) 5 10
b) 6 11
c) 6 10
d) 5 11
e) Wayne Rooney

5. Scrieți un program care citește de la tastatură notele unui elev la limba română, matematică și informatică și afișează dacă elevul a promovat sau nu bacalaureatul.

6. Scrieți un program care afișează toate numerele pare de la 1 la un număr citit de la tastatură.

PC Laborator 5

2015-09-24T17:03:58Z

Ccioflan: Pagină nouă: == Obiective == în urma acestui laborator, studentul va fi capabil să: * înțeleagă cum funcționează o structură decizională; * scrie programe în C folosind cons...

== Obiective ==

în urma acestui laborator, studentul va fi capabil să:
* înțeleagă cum funcționează o structură decizională;
* scrie programe în C folosind construcții decizionale.

== Structura decizionala ==

Se întâmplă adesea ca evoluția unui program să depindă de un moment prezent. Acel moment prezent poate lua însă diverse forme, rolul programatorului fiind să conducă execuția programului pe calea corectă, pe baza unor condiții. Apare astfel structura decizionala if, care ramifică evoluția programului în funcție de valoarea de adevăr a condiției testate.

=== Schema logică ===
Prima etapă din parcurgerea unei structuri decizionale de tipul if-else o reprezintă testarea condiției logice. în cazul în care aceasta este evaluată ca adevărată se execută instructiunea1, cea asociată ramurii if. în cazul în care condiția logică este evaluată ca falsă se execută instructiunea2, cea asociată ramurii else. După executarea instrucțiunii asociate, structura if-else se încheie și programul se continuă cu linia următoare corpului decizional.

[[Fișier:structura_decizionala.png]]

=== Sintaxă generală ===
a) <syntaxhighlight lang="C">
if (conditie) instructiune;
</syntaxhighlight>
b)<syntaxhighlight lang="C">
if (conditie)
instructiune1;
else
instructiune2;
</syntaxhighlight>
c) <syntaxhighlight lang="C">
if (conditie1)
instructiune 1;
else if (conditie2)
instructiune 2;
else if (conditie 3)
instructiune3;
................................
else
instructiune;
</syntaxhighlight>

=== Asocierea ramurilor if-else===

<div class="regula"> ''' Observație: ''' în cazul în care un if are mai multe ramuri, un else se asociază celui mai apropiat if.</div>
Această observație ne conduce la următoarele două cazuri:

* dacă nu există corpuri de instrucțiuni, un else este legat de if-ul imediat anterior;
<syntaxhighlight lang="C">
if (a > 5)
if (b > a)
printf ("b este mai mare ca 5");
else
printf ("b este intre 5 si a");
</syntaxhighlight>
* dacă există corpuri de instrucțiuni, un else este legat de ultimul if fără pereche.
<syntaxhighlight lang="C">
if (a > 5) {
if (b > a)
printf ("b este mai mare ca 5");
}
else
printf ("a nu este mai mare ca 5");
</syntaxhighlight>

'''Exemplu:'''

Ce va afișa acest program prost indentat?
<syntaxhighlight lang="C">
int number = 4;
double alpha = -1.0;
if (number > 0)
if (alpha > 0)
printf( "Here I am!\n");
else
printf( "No, I’m here!\n");
printf("No, actually, I’m here!\n");
</syntaxhighlight>

== Condiția logică ==

Am stabilit deja că o condiție logică, prin valoarea ei de adevăr, ramifică evoluția programului.

<div class="regula">'''<font color="red"> Atenție:</font>''' Adevărat în C înseamnă orice rezultat diferit de 0 (nul) al unei evaluări, în timp ce despre fals vorbim când o expresie este evaluată la 0 ( nul).
</div>

În C, condiția poate avea mai multe reprezentări, după cum urmează

=== Operandul ===

'''Exemplu:'''
Verificați un număr citit de la poate numitorul unei fracții.

=== Operația cu operatori relaționali (==, !=, <=, <, >, >=) ===

'''Exemplu:'''
Asociați o valoare variabilei cost funcție de valoarea variabilei distance după cum urmează:
{| class="wikitable"
! colspan="2" |
|-
| style="text-align: center;" |distance
| style="text-align: center;" |cost

|-
| style="text-align: center;" | Intre 0 si 100
| style="text-align: center;" | 5.50
|-
| style="text-align: center" | Peste 100, dar mai putin de 500
| style="text-align: center;" | 8.00
|-
| style="text-align: center;" | Peste 500, dar nu mai mult de 1000
| style="text-align: center;" | 10.50
|-
| style="text-align: center;" | 1000 sau mai mult
| style="text-align: center;" | 13.00

|}

=== Operația cu operatori logici (&&, ||, !, ^) ===

'''Exemplu:'''
Folosind operatori logici, aduceți următoarea structură decizională la forma cea mai simplă:
<syntaxhighlight lang="C">
if (doesSignificantWork) {
if (makesBreakthrough)
nobelPrizeCandidate = true;
else
nobelPrizeCandidate = false;
}
else if (!doesSignificantWork)
nobelPrizeCandidate = false;
</syntaxhighlight>

<div class="regula"> '''Observație:'''Pentru a putea lucra cu operatorii logici, este necesar să ne reamintim modul în care aceștia operează.
{| class="wikitable"
! colspan="5" | Tabelul operatorilor logici
|-
| style="text-align: center;" | a
| style="text-align: center;" | b
| style="text-align: center;" | !a
| style="text-align: center" | a && b
| style="text-align: center" | a ll b
|-
| style="text-align: center" | 1
| style="text-align: center;" | 1
| style="text-align: center;" | 0
| style="text-align: center" | 1
| style="text-align: center" | 1
|-
| style="text-align: center" | 0
| style="text-align: center" | 0
| style="text-align: center;" | 1
| style="text-align: center" | 0
| style="text-align: center" | 0
|-
| style="text-align: center" | 0
| style="text-align: center;" | 1
| style="text-align: center;" | 1
| style="text-align: center" | 0
| style="text-align: center" | 1

|}

</div>
== Alternative la if-else ==

=== Operatorul condițional ( ? : ) ===
Singurul operator ternar din C, operatorul condițional funcționează asemenea unui if cu o singură ramură de tip else if. Sintaxa operatorului condițional este următoarea:
<syntaxhighlight lang="C">
(conditie) ? (instructiune1) : (instructiune2)
</syntaxhighlight>

Aşadar, blocul decizional
<syntaxhighlight lang="C">
if (a>b)
printf ("a este mai mare decat b");
else
printf ("a este mai mic sau egal cu b");
</syntaxhighlight>
poate fi înlocuit astfel:
<syntaxhighlight lang="C">
(a>b) ? ( printf ("a este mai mare decat b")) : ( printf ("a este mai mic sau egal cu b"));
</syntaxhighlight>

=== Structura decizională switch-case ===
Această instrucțiune de decizie este similară unui if cu mai multe ramuri de tip else-if. Sintaxa este următoarea:
<syntaxhighlight lang="C">
switch (variabilaTestata) {
case valoare1: { instructiune1;
[break;]
}
case valoare2: { instructiune2;
[break;]
}
case valoare3: { instructiune3;
[break;]
}
.........................................................................
default: {instructiune;
}
}
</syntaxhighlight>
Valorile ''valoare1'', ''valoare2'' etc. sunt proprii tipului de dată întreg, la fel ca ''variabilaTestata''. Ne reamintim însă că întreg nu înseamnă doar variabile de tip '''int''', astfel că ''variabilaTestata'' poate fi de tip '''char'''.
<div class="regula">'''Observație:''' instrucțiunea ''break'' este opțională. Modul care switch-case funcționează este următorul:

a) se compară valoarea variabilei ''variabilaTestata'' cu ''valoarea1'';

b) dacă cele două sunt egale, se execută ''instructiune1''. Apoi există două cazuri:

i. dacă există ''break;'' structura switch-case se încheie și se sare pe linia urmatoare întregului corp decizional;

ii. dacă nu există ''break;'' execuția se continuă până se întalnește un ''break;'' sau până când se încheie structura switch-case. Până la acel moment se vor executa toate instrucțiunile întâlnite pe parcurs (''instructiune2, instructiune3'' etc.);

c) dacă valoarea variabilei ''variabilaTestata'' nu este egală cu niciuna dintre valorile ''valoare1, valoare2'' etc atunci se execută ''instructiune'', asociată etichetei default.
</div>

Pentru a verifica echivalența dintre if-else și switch-case, rezolvați folosind ambele structuri decizionale următoarea problemă:

'''Exemplu:'''
Un microbist vrea să afle situația Grupei F de calificare la EURO2016. Astfel, el va introduce o cifră pentru a vedea ce "națională" ocupă acel loc. Folosind următoarea listă, informați-l corect pe suporter.

1. Irlanda de Nord
2. România
3. Ungaria
4. Finlanda
5. Insulele Feroe
6. Grecia

== Exerciții ==

1. Ce va afișa următorul program?
<syntaxhighlight lang="C">
void main(){
int a=100;
if(a>10)
printf("Tiberiu Soare\n");
else if(a>20)
printf("Horia Andreescu\n");
else if(a>30)
printf("Iosif Ion Prunner\n");
}
</syntaxhighlight>
a) Tiberiu Soare
b) Horia Andreescu
c) Tiberiu Soare
Horia Andreescu
Iosif Ion Prunner
d) Compilation error: More than one conditions are true
e) Niciuna dintre cele de mai sus.

2. Ştiind că un student primește 350 lei/lună dacă are media cel puțin 8.50, 450 lei/lună pentru o medie mai mare sau egală cu 9.50 și 600 lei/lună dacă are media cel puțin 9.70, scrieți un program prin care studentul să afle ce bursă urmează să primească (media va fi citită de la tastatură).

3. Ce va afișa următorul program?
<syntaxhighlight lang="C">
#include<stdio.h>
void main(){
int m=5,n=10,q=20;
if(q/n*m)
printf("Bill Gates\n");
else
printf("Amancio Ortega\n");
printf("Carlos Slim Helu\n");
}
</syntaxhighlight>
a) Bill Gates
b) Amancio Ortega
Carlos Slim Helu
c) Run time error
d) Compilation error
e) Niciuna din cele de mai sus

4. Ce va afișa următorul program?
<syntaxhighlight lang="C">
#include<stdio.h>
void main(){
int a=5,b=10;
if(++a||++b)
printf("%d %d",a,b);
else
printf("Wayne Rooney");
}
</syntaxhighlight>
a) 5 10
b) 6 11
c) 6 10
d) 5 11
e) Wayne Rooney

5. Scrieți un program care citește de la tastatură notele unui elev la limba română, matematică și informatică și afișează dacă elevul a promovat sau nu bacalaureatul.

6. Scrieți un program care afișează toate numerele pare de la 1 la un număr citit de la tastatură.

Fișier:Structura decizionala.png

2015-09-24T15:30:15Z

Ccioflan: