programare, comunicare,

PROGRAMARE, COMUNICARE,

IMAGINAŢIE, DESIGN

Lucrările

Conferinţei Naţionale de Informatică

Ediţia a VI-a

Sibiu, 28 Martie 2020

Universitatea „Lucian Blaga” din Sibiu

Facultatea de Ştiinţe

Centrul de Cercetare în Informatică și

Tehnologia Informației

Lucrările Conferinţei Naţionale de Informatică

„Programare, Comunicare, Imaginaţie, Design”

Ediţia a VI-a, Sibiu, România

Editori

Dana Simian

Laura Florentina Stoica

Colectiv tehnoredactare

Dana Simian

Laura Florentina Stoica

Design copertă

Ralf Fabian

ISSN 2393 - 4956

Prefaţă

Prezentul volum reuneşte lucrările prezentate la a șasea ediţie a Conferinţei

Naţionale de Informatică “Programare, Comunicare, Imaginaţie, Design”,

desfăşurată la Universitatea „Lucian Blaga” din Sibiu, în 28 Martie 2020,

organizată de către Colectivul de Informatică din cadrul Departamentului de

Matematică şi Informatică, de la Facultatea de Ştiinţe. Scopul conferinţei este de a

reuni elevi din toate centrele pre-universitare din ţară pentru a prezenta şi a discuta

aplicații originale realizate în cadrul următoarelor arii tematice ale domeniului

informatică: structuri de date în aplicaţii software, metode de compresie a datelor,

algoritmi de sortare: metode şi aplicaţii, software educaţional, teoria grafurilor în

probleme şi aplicaţii, criptografie, securitatea sistemelor informatice, dezvoltarea

aplicaţiilor cu baze de date, procesarea imaginilor, proiectarea şi implementarea

site-urilor Web, aplicaţii multimedia în educaţie, divertisment, aplicaţii software

pentru dispozitive mobile, tehnici de programare, managementul proiectelor

informatice, etc. Mulţumim tuturor participanţilor, colectivului de organizare şi

colectivului ştiinţific, pentru contribuţia adusă la succesul acestei manifestări

ştiinţifice şi la realizarea prezentului volum.

Prof. univ. Dr. Dana Simian

Comitet Ştiinţific

Prof. Univ. Dr. Dana Simian – preşedinte(chair)

Prof. Univ. Dr. Valer Roşca

Conf. Univ. Dr. Nicolae Constantinescu

Conf. Univ. Dr. Florin Stoica

Conf. Univ. Dr. Laura Stoica

Lector Univ. Dr. Ralf Fabian

Lector Univ. Dr. Daniel Hunyadi

Lector Univ. Dr. Mircea Muşan

Lector Univ. Dr. Mircea Neamțu

Lector Univ. Dr. Alina Pitic

Cuprins:

API Utilizat pentru Studiul Mișcării, realizat în NodeJS ……………..……...

Andrei Constantin Dîrjan, Monica Avram

6

Garbage Collector ………………….…………………………………….……...

Răzvan Gheorghe Filea, Delilah Florea

15

Dynamic Computing 20. De la Formula 1 la Formula-Micro…………………

Christian Melchior, Nicolae Steavu

24

SmartH ………………………………………………………………………...…

Nicolae-Constantin Steavu, Nicolae Steavu, Cristina-Elena Steavu

32

Bibliotecă de Funcţii Calendaristice ………………...….………………………

Denis Benke, Raluca Bocotan, Costică Cîrjean

41

Modalități uzuale de implementare a teoriei grafurilor și aplicații ..…......…..

Oana-Maria Topan, Krisztina-Aliz Horvath, Mihaela Giurgea, Andreea Racolta

50

RESURSE MEDIA

API Utilizat pentru Studiul Mișcării, realizat în NodeJS ……………..……...


58

Garbage Collector ………………….…………………………………….……...


59

Dynamic Computing 20. De la Formula 1 la Formula-Micro…………………


60

SmartH ………………………………………………………………………...…


61

Lista autorilor …………………….………….…………………………….….…

62

Lista profesorilor coordonatori ….………….…………………………….….…

64

Sponsori ………………….…………………………………………….…....……

65

Conferinţa Naţională de Informatică

"Programare, Comunicare, Imaginaţie, Design"

PCID-2020, 28 Martie 2020

Sibiu, Romania

API Utilizat pentru Studiul Mișcării, realizat în NodeJS

Dîrjan Andrei Constantin, Avram Monica

Rezumat: Lucrarea reprezintă realizarea unui API în NodeJS cu conexiune la o bază de date cu stocare

în cloud, și anume MongoDB. Acest API reprezintă un modul complet funcțional ce poate fi integrat în

alte proiecte. A fost creat din necesitatea transmiterii datelor unui robot într-o manieră cât mai utilă și

cât mai ușor de implementat. API-ul utilizează HTTP request methods pentru a transmite sau primi

date spre și din baza de date. Acesta prezintă și câteva metode de securitate; pentru folosire utilizatorul

trebuie să creeze un cont și să se logheze pentru a efectua request-uri; email-urile sunt verificate pentru

validitate, iar parolele sunt hash-uite înainte de stocare.

Abstract: This project represents the realization of an API in NodeJS with a connection to a database

with cloud storage, namely MongoDB. This API is a fully functional module that can be integrated into

other projects. It was created out of the need to transmit data from a robot in a way that is as useful and

easy as possible to implement. The API uses HTTP request methods to transmit or receive data to and

from the database. It also presents some security methods; the user must create an account and then log

in, in order to make requests; emails are checked for validity and passwords are hashed before storage.

1 Introducere

Alegerea de a crea acest API provine dintr-un proiect realizat pentru ora de fizică, ce consta

într-un robot folosit pentru studiul mișcării rectilinie, mișcării circulare și mișcării neuniforme.

Datele înregistrate de robot trebuie salvate pentru a fi prelucrate ulterior; de aici provine motivația

de a dezvolta o modalitate de transmitere a datelor într-o manieră cât mai ușor de implementat odată

ce a fost realizată.

Pentru dezvoltarea API-ului a fost utilizat un nou limbaj de programarea și, de asemenea, au

fost folosite servicii precum MongoDB. Deoarece aceste lucruri nu se regăsesc în programa de

liceu, a fost necesar studiul individual pentru însușirea noțiunilor aplicate în realizare API-ului.

Proiectul este realizat in NodeJS, acesta fiind un JavaScript runtime environment,

reprezentând un API (Application Programming Interface). Acesta permite transmiterea anumitor

date către o baza de date cu stocare pe cloud pentru o prelucrare ulterioară. Pentru păstrarea unei cât

mai bune evidențe în baza de date este necesară crearea unui utilizator, de asemenea este necesară și

logarea pentru a transmite date.

Tehnologiile folosite pentru realizarea acestui API sunt:

JavaScript

NodeJS;

express;

nodemon;

mongoose;

dotenv;

@hapi/joi;

bcryptjs;

Conferinţa Naţională de Informatică „Programare, Comunicare, Imaginație, Design”

28 Martie 2020, Sibiu, Romania

jsonwebtoken;

MongoDB;

Postman.

Articolul este organizat pe 8 secțiuni astfel:

Prima secțiune prezintă motivarea alegerii temei;

Secțiunea 2 prezintă funcționalitatea API-ului;

Secțiunea 3 prezintă modalitatea prin care se efectuează validarea datelor;

Secțiunea 4 prezintă detalii de securitate;

Secțiunea 5 dezvolta alte părți ale API-ului;

Secțiunea 6 prezintă exemplificarea funcționalității;

Secțiunea 7 prezintă concluzia;

Secțiunea 8 prezintă elementele bibliografice.

2 Funcționalitate

API-ul prezintă trei POST HTTP request methods care îndeplinesc următoarele funcții:

/register primește trei parametri (email, utilizator și parolă) transmiși în format JSON

ce reprezintă datele necesare pentru înregistrarea unui utilizator nou;

/login primește doi parametri (email și parolă) transmiși în format JSON ce reprezintă

datele necesare pentru logarea în sistem;

/send primește doi parametri (un ID și un timp) transmiși în format JSON ce reprezintă

ID-ul robotului ce transmite datele și timpul ce trebuie înregistrat.

Datele de înregistrare fac parte dintr-o schemă de creare a unui nou utilizator. Schema conține

trei valori și anume: email, name și password. Fiecare dintre aceste valori sunt de tipul string, au un

număr minim și unul maxim de elemente și sunt absolut necesare pentru înregistrarea cu succes a

utilizatorului. Această schemă este implementată cu ajutorul funcției Schema() a librăriei

Mongoose. Schema cu datele necesare creării unui nou utilizator este următoarea:

const user = mongoose.Schema({

email: {

type: String,

required: true

},

name: {

type: String,

required: true,

min: 4,

max: 20

},

password: {

type: String,

required: true,

min: 6,

max: 1024

}

});

Datele de logare, precum și cele de înregistrare, fac parte din schema de mai sus, dar pentru

logare acestea sunt comparate cu datele existente în baza de date.

Transmiterea datelor de către un robot se face doar după încheierea procesului de înregistrare

și de logare. Aceste date care ne furnizează elementele necesare pentru evaluarea unei anumite

cerințe folosesc o alta schemă. Ele reprezintă un ID și un timp necesare analizei unui traseu (aceste

date se pot schimba în funcție de cerințele proiectului). Schema este următoarea:



response.send("User registered!");

}catch (e) {

response.status(400).send(e);

}

});

La logare, email-ul și parola vor fi verificate apoi utilizatorul cu email-ul respectiv va fi căutat

în baza de date. Dacă email-ul nu este găsit atunci va fi returnată o eroare, altfel parola transmisă va

fi comparată cu cea din baza de date. Dacă parola nu corespunde va fi returnată o eroare, iar dacă

aceasta corespunde se va genera un token (jsonwebtoken) ce trebuie prezentat și validat la

transmiterea datelor în baza de date.

Partea ce se ocupă cu validarea datelor este:

const login = data => {


email: hapiJoi.string()

.required()

.email(),

password: hapiJoi.string()

.required()

.min(6)

});

return analyse.validate(data);

}

Partea ce se ocupă cu verificarea datelor și cu generarea token-ului este:

router.post('/login', async (request, response) => {

const {error} = validationLogin(request.body);

if (error)


const exists = await user.findOne({email: request.body.email});

if (!exists)

response.status(400).send("This email is not registered!");

const passwordValidity = bcrypt.compare(request.body.password,

exists.password);

if (!passwordValidity)

response.status(400).send("Password or Email is wrong!");

const token = jsonWebToken.sign({_id: exists._id},

process.env.secrettoken);

response.header('authentication-token', token).send(token);

});

Validarea datelor este necesară și la transmiterea datelor. Token-ul generat la logare va fi

transmis în header-ul request-ului. Acest token va fi verificat înaintea validării datelor, iar în cazul

în care este valid API-ul va valida datele, apoi le va transmite bazei de date.

Partea care se ocupă cu verificarea token-ului este:

module.exports = function (request, response, next){

const token = request.header('authentication-token');



if (!token)

response.status(400).send("Access denied!");

try{

const verified = jsonWebToken.verify(token,

process.env.secrettoken);

request.user = verified;

next();

}catch (e) {

response.status(400).send("Invalid token!");

}

};

Partea care se ocupă cu validarea datelor este:

const roboData = data => {


robotID: hapiJoi.string()

.required(),

time: hapiJoi.string()

.required()

});

return analyse.validate(data);

}

Partea care folosește cele două coduri de mai sus și transmite date este:

router.post('/', verify, async (request, response) => {

const {error} = roboData(request.body);

if (error)


const data = new roboInput({

robotID: request.body.robotID,

time: request.body.time

});

try{

await data.save();

response.send("Data sent!");

}catch (e) {

response.status(400).send(e);

}

});

4 Securitate

Securitatea API-ului este realizată prin următoarele funcționlități: înregistrare, logare și

necesitatea prezentării unui token la transmiterea datelor spre baza de date.

Pentru validarea datelor de înregistrare și logare este folosită librăria @hapi/joi[1]; folosind

această librărie se creează o schemă de date ce conține tipul de date și constrângerile necesare. La

trimiterea request-ului datele sunt verificate folosind schema de date definită.

La înregistrare parola va fi hash-uită înainte de stocare folosind librăria bcryptjs[2]. Tipurile

de hash-uri folosite de această librărie sunt $2a$ și $2b$. Realizarea acestei criptări se face prin

generarea unui șir aleatoriu de 15 caractere, apoi funcția hash folosește acest șir aleatoriu pentru a



cripta parola. API-ul folosește modul asincron de criptare a datelor oferit de această librărie, ceea ce

permite răspunderea la mai multe request-uri chiar dacă procesul de hash-uire nu a fost terminat.

După efectuarea autentificării este furnizat un token folosind librăria jsonwebtoken[3]. Acest

token trebuie inclus în header-ul requestului de transmitere a datelor generate de către robot ca

acestea să fie trimise spre baza de date. Acest token este valabil pentru aproximativ 15 minute.

5 Alte părți ale API-ului

În această fază incipientă API-ul rulează local, accesul putând fi realizat din aceeași rețea.

Acesta deschide un anumit port prin care va primi toate aceste date. La pornire se realizează

conexiunea cu baza de date, respectiv MongoDB.

const express = require('express');

const mongoose = require('mongoose');

const dotenv = require('dotenv').config();

const app = express();

const authenticationRoute = require('./Routes/authentication');

const sendDataRoute = require('./Routes/postData');

app.use(express.json());

app.use('/api/user', authenticationRoute);

app.use('/api/send', sendDataRoute);

app.get('/', (request, response) => {

response.send("hello world");

})

mongoose.connect( process.env.database,

{ useNewUrlParser: true, useUnifiedTopology: true },

() => console.log("Connected to DB!"));

app.listen(3000, () => console.log("API started successfully!"));

6 Exemplificare

Trimiterea de date API-ului se face folosind aplicația Postman, aceasta permite includerea

informațiilor de tip JSON la folosirea HTTP request methods.

În Fig. 1 este prezentat un request de tipul POST pentru înregistrarea unui utilizator nou.

După trimiterea acestor date este returnat mesajul “User registered!”, arătând că utilizatorul a fost

creat cu succes. Datele sunt scrise în format JSON.



Fig. 1: Date înregistrare

În Fig. 2 este prezentată intrarea din Fig. 1 în baza de date. Se poate observa și parola obținută

prin hash-uire, folosind tipul de hash $2a$.

Fig. 2: Date înregistrare în baza de date

În Fig. 3 este prezentat un request de tipul POST pentru autentificare. Șirul returnat reprezintă

token-ul de securitate.



Fig. 3: Autentificare

În Fig. 4 este prezentat un request de tipul POST prin care un robot ar putea trimite date API-

ului. Token-ul din Fig. 3 se află in header-ul request-ului.

Fig. 4: Date robot

În Fig. 5 este prezentată intrarea din Fig. 4 în baza de date.



Fig. 5: Date robot în baza de date

7 Concluzie

Acest API este un modul complet funcțional ce poate fi configurat și integrat în alte proiecte

pentru avantajele pe care le aduce.

În ceea ce privește posibilele dezvoltări viitoare, API-ul poate fi lansat pe platforma ZEIT

Now, eliminând necesitatea rulării într-o rețea locală. Totodată, este posibilă integrarea unei părți de

front-end, mărind utilitatea acestuia.

8 Bibliografie

[1] Algoritmul pentru crearea unui obiect de tipul Joi și validarea datelor cu ajutorul acestuia,

https://hapi.dev/module/joi/ (data accesării 08.03.2020)

[2] Algoritmii de la Usage – Async pentru realizarea hash-ului parolei și de verificare a parolei la

autentificare https://www.npmjs.com/package/bcryptjs (data accesării 08.03.2020)

[3] Algoritmul pentru implementarea token-ului de securitate, minutul 57:25,

https://www.youtube.com/watch?v=2jqok-WgelI&t=3460s (data accesării 08.03.2020)

Dîrjan Andrei Constantin

Liceul Teoretic “Onisifor Ghibu” Sibiu

Matematică-Informatică

Sibiu, România

E-mail: [email protected]

Prof. Avram Monica

Liceul Teoretic “Onisifor Ghibu” Sibiu

Informatică

Sibiu, România


https://hapi.dev/module/joi/

https://www.npmjs.com/package/bcryptjs

https://www.youtube.com/watch?v=2jqok-WgelI&t=3460s

mailto:[email protected]





Sibiu, Romania

Garbage Collector

Filea Răzvan Gheorghe, Florea Delilah

Rezumat: Lucrarea descrie implementarea unui algoritm cross-platform de Garbage Collection pentru C++ și îmbunătățiri aduse acestuia relativ la modul de eliberare a memoriei alocate dinamic. Algoritmul este dezvoltat sub forma unei biblioteci de cod pentru C++17, putând fi folosit de orice program pentru identificarea și eliberarea zonelor de memorie nefolosite. Biblioteca este foarte ușor de utilizat, având un API intuitiv.

Abstract: This paper describes the implementation of a cross-platform Garbage Collection algorithm for C++ and its improvements regarding the release the dynamically allocated memory. The algorithm is developed in the form of a code library for C++17, which can be used by any program to identify and release unused memory areas. The library is very easy to use, having an intuitive API.

1 Introducere

Programul este implementat ca o biblioteca de cod cross-platform și a fost dezvoltată și testată în Visual Studio Community 2019 pe Windows, CLion pe Linux și Android Studio pentru Android.

Numărul foarte mare de sisteme de calcul implementate si apărute pe piață datorită lui Gordon Moore, care a prezis încă din anii 60 dublarea la fiecare 18 luni a numărului de tranzistori din cipurile electronice și în special din procesoare, a condus la necesitatea implementării de aplicații care trebuie să ruleze eficient pe mai multe tipuri de platforme (cross-platform) caracterizate de ISA de procesoare diferite si sisteme de operare diferite [1].

Odată cu explozia dispozitivelor mobile necesitatea aplicațiilor cross-platform a devenit obligatorie pentru dezvoltatori pentru a nu pierde piața de consum. Utilizatorii aplicațiilor mobile se așteaptă acum de la companii ale căror servicii le consumă să aibă deja o aplicație care să ofere serviciile și în versiunea mobilă nu doar Desktop, cu toate că pentru dezvoltatori acest lucru nu este întotdeauna simplu, ușor sau ieftin [2].

Această lucrare este structurată după cum urmează. Secțiunea 2 prezintă problema principală a memoriei în programele C++, necesitatea implementării unui Garbage Collector în C++, alegerea algoritmilor potriviți și importanța implementării multithreadead în vederea creșterii eficienței aplicației. Secțiunea 3 descrie soluția propusă insistând pe implementarea algoritmului de eliberare a memoriei alocate dinamic și clasele folosite. Secțiunea 4 ilustrează rezultatele obținute și optimizările aplicate. În final secțiunea 5 evidențiază principalele concluzii, contribuțiile aduse și propune unele direcții de dezvoltare ulterioară a aplicației.



2 Garbage Collector în C++. Necesitate. Algoritmi. Avantaje

2.1. Crearea unui Garbage Collector în C++

Deoarece C++ este un limbaj bogat și puternic, există multe moduri de a implementa un Garbage Collector. O abordare evidentă, dar limitată, este crearea unei clase de bază, care este moștenită apoi de clasele care doresc să folosească Garbage Collection. Acest lucru permite implementarea unui Garbage Collection de la o clasă la fiecare clasă. Această soluție este, din păcate, prea restrânsă pentru a fi satisfăcătoare.

O soluție mai bună este cea în care Garbage Collector-ul poate fi utilizat cu orice tip de obiect alocat dinamic [3]. Pentru a oferi o astfel de soluție, Garbage Collector-ul trebuie să:

1. Coexiste cu metoda manuală oferită de C++. 2. NU creeze nici un fel de impact asupra codului deja existent. 3. Funcționeze cu toate tipurile de date, cum ar fi cele definite de utilizator cât și

primitivele sau cele oferite de librăria standard C++. 4. Fie ușor de folosit.

2.2. Problema principală a memoriei în C++

Provocarea cheie cu care se confruntă cineva atunci când creează un Garbage Collector este cum să știe când o parte de memorie este neutilizată. Pentru a înțelege problema, poate fi luată în considerare următoarea secvență: int *p; p = new int{1}; p = new int{2};

Aici avem doua obiecte de tip int alocate dinamic. Primul conține valoarea 1 și pointerul către această valoare este salvat în p. Apoi, un alt obiect cu valoarea 2 este alocat și pointerul către valoarea acestuia este stocat tot în p, suprascriind prima adresă. În acest moment, memoria pentru int{1} nu este indicată de p, sau de orice alt obiect, și poate fi eliberată. Întrebarea este: cum știe Garbage Collector-ul când nici un obiect nu mai conține un pointer către memoria lui int{1}? Modul precis de răspuns la aceste întrebări este determinat de algoritmul de Garbage Collection utilizat.

2.3. Alegerea unui tip de algoritm

Înainte de a implementa unui Garbage Collector-ul, este necesar să se decidă ce algoritm de Garbage Collection trebuie utilizat. Deoarece subiectul Garbage Collector prezintă o problemă interesantă pentru care există o varietate de soluții, au fost concepute o multitudine de algoritmi de Garbage Collection. Dintre aceștia există trei abordări de bază: Mark and Sweep, Copying și Reference Counting [4]. Înainte de a alege o abordare, acești trei algoritmi au fost revizuiți.

a) Mark and Sweep

Mark and sweep implică două faze. În prima fază, toate obiectele din Heap sunt setate la starea lor nemarcată. Apoi, toate obiectele accesibile direct sau indirect din variabilele programului sunt marcate ca folosite. În faza a doua, toată memoria alocată este scanată și toate elementele care nu au fost marcate sunt eliberate.



Există două avantaje principale ale Mark and Sweep. În primul rând, se rezolvă cu ușurință problema referințelor circulare. În al doilea rând, nu adaugă practic niciun fel de cost de rulare în afară de colectare. Dar are două dezavantaje principale. În primul rând, este necesară o perioada îndelungată de timp pentru Garbage Collector, deoarece întregul Heap trebuie scanat în timpul colectării. Astfel, Garbage Collector-ul poate cauza caracteristici de rulare inacceptabile pentru unele programe. În al doilea rând, deși conceptele de marcare și scanare sunt simple, pot fi dificil de implementat eficient.

b) Copying

Algoritmul de copiere organizează memoria liberă în două spații. Unul este activ (ținând memoria Heap curentă), iar celălalt este inactiv. În timpul procedurii de Garbage Collection, obiectele utilizate în spațiul activ sunt identificate și copiate în spațiul inactiv. Apoi, rolurile celor două spații sunt inversate, spațiul inactiv devenind activ și spațiul activ devine inactiv. Copierea oferă avantajul compactării memoriei Heap în procesul de copiere. Dar dezavantajul acestuia este că permite ca doar jumătate din întreaga memorie Heap să fie folosită.

c) Reference Counting

În numărarea de referință, fiecărei bucată de memorie alocată dinamic îi este asociată un număr de referință. Acest număr este incrementat când este creată o nouă referință la memorie și este decrementată de fiecare dată când referință la memorie este eliminată. Iar când numărul de referință scade la zero, memoria este considerată neutilizată și poate fi eliberată. Principalul avantaj al numărării de referințe este simplitatea - este ușor de înțeles și de implementat. În plus, nu pune nici o restricție la organizarea obiectului, deoarece numărul de referințe este independent de locația fizică a unui obiect. Numerotarea de referințe adaugă cheltuieli generale pentru fiecare operațiune indicatoare, dar faza de colectare are un cost relativ redus. Dezavantajul principal este că referințele circulare împiedică eliberarea memoriei care altfel nu este folosită. O referință circulară apare atunci când două obiecte au fiecare o referință una către cealaltă, direct sau indirect. În această situație, numărul de referințe al niciunui obiect nu scade la zero. S-au conceput câteva soluții pentru problema de referință circulară, dar toate adaugă multă complexitate și costuri ridicate la colectare.

d) Multithreading

Altă considerare la implementarea unui algoritm de Garbage Collection este dacă algoritmul ar trebui să fie single threaded sau multithreaded. Deoarece afectează fundamental modul de execuție a algoritmului, dacă este un fir de execuție în fundal sau rulează când anumite condiții sunt îndeplinite. Avantajul principal a folosirii unui algoritm multithreaded este eficiența. Gunoiul poate fi colectat când procesorul este inactiv. Dar are dezavantajul ca programul sa trebuiasca sa fie oprit uneori în timp ce colectarea are loc. În proiectul descris este folosită abordarea de multithreading pentru a atinge o eficiență crescută. De asemenea au fost construite structuri de date eficiente pentru a scurta timpul de blocare a programului la rularea colectării.



3 Soluția propusă

3.1. Implementarea algoritmului

Pentru a implementa un Garbage Collector cu algoritmul de numărare a referințelor, este necesar mod de a urmări numărul de obiecte care au o referință către o locație din memorie alocată dinamic. Problema este că C++ nu are un mecanism încorporat care să permită unui obiect să știe când un alt obiect îl are ca o referință. Din fericire, există o soluție: se poate crea un nou tip de referintă care facilitează eliberarea memoriei. Aceasta este și abordarea folosită de Garbage Collector-ul implementat. Pentru a sprijini Garbage Collection-ul, noul tip de referință trebuie să facă trei lucruri. În primul rând, trebuie să mențină o listă de numere de referință pentru obiectele active alocate dinamic. În al doilea rând, trebuie să țină evidența tuturor operațiunilor de pointer, crescând numărul de referință al unui obiect de fiecare dată când este creată o nouă referință către acel obiect și scăzând numărul de fiecare dată când o referintă este eliminată. În al treilea rând, trebuie să recicleze acele obiecte ale căror numere de referință scad la zero. În afară de facillitarea Garbage Collection-ului, noul tip de referintă va funcționa la fel ca un pointer din C++ normal. De exemplu, toate operațiile de dereferențiere, cum ar fi * și ->, sunt acceptate. Pe lângă faptul că este o modalitate convenabilă de a implementa un Garbage Collector, crearea unui tip de pointer de Garbage Collection ce satisface constrângerea că sistemul original de alocare dinamic C++ trebuie să nu fie afectat. Când este dorit Garbage Collector-ul, se folosesc referințele special create pentru acesta. Atunci când nu este dorit, sunt disponibili pointerii C++ normali. Astfel, ambele tipuri de pointeri pot fi utilizate în cadrul aceluiași program.

3.2. Explicarea claselor algoritmului

Colectorul de gunoi implementat conține cinci clase: gc::pointer, gc::page, gc::ref, gc::ref_array, și gc::internal. Toate aflându-se în namespace-ul „gc”. gc::pointer contine pointerul către memoria gestionata și numărul de referințe către aceasta. Această clasă se ocupă cu alocarea memoriei obiectului, păstrarea unui pointer către memoria alocată și cu distrugerea obiectului și eliberarea memoriei când este nevoie. Din cauză că această clasă trebuie să poată fi stocată în șiruri împreună cu alți gc::pointer ce conțin pointeri către tipuri diferite de date, această clasă nu poate fi transformată intr-un template. gc::page este un container de date, ce stochează un număr fix de obiecte gc::pointer. A fost gândit în așa fel încât complexitatea adăugării și eliminării unui obiect din șir să fie mereu constante ( O(1) ) și de a evita alocările dinamice de memorie. gc::ref este cea mai importantă clasa a bibliotecii din punctul de vedere al utilizatorului. Aceasta este o clasa template ce supraîncarcă operatorii de pointeri * și ->. Mai exact aceasta clasa este un wrapper pentru gc::pointer ce face API-ul ușor de folosit. gc::ref_array este un simplu șir de elemente ce este eliberat de Garbage Collector atunci când nu mai este folosit. Practic este echivatentul unui șir de elemente într-un gc::ref. gc::internal este o clasă statică cu majoritatea funcțiilor private, deoarece conține majoritatea codului ce reprezintă Garbage Collector-ul și nu ar trebui accesate direct de către utilizator. Relația dintre aceste clase poate fi observată și în diagrama din Figura 1.



Fig. 1: Diagrama claselor din algoritm

3.3. Explicarea implementării

Una dintre cele mai mari probleme de la bun început a fost crearea unui container eficient pentru orice tip de obiect fără ca această clasă să fie template, deoarece fără a ști tipul clasei la compilare, un program C++ nu poate crea un obiect. Pentru acest motiv a fost găsită o soluție foarte specifică. În primul rând, clasa gc::pointer are o funcție template numită init care știe cum să construiască obiectul fără a interfera cu restul clasei. Iar pentru eliberarea memoriei/distrugerea obiectului, a fost creată o clasă privată statică template, numită manager, ce conține o singură funcție numită object_deleter și primește ca parametru un void*. Această funcție știe cum să distrugă specific obiectul stocat de gc::pointer. Așa că pe lângă numărul de referințe și pointerul pentru obiect în gc::pointer mai avem și un Function Pointer declarat în felul următor: void (*_deleter)(void *). Acesta este apelat în funcția destroy din gc::pointer cu pointerul în acesta ca argument. Clasa gc::ref conține două pointere, unul către gc::pointer-ul ce conține numărul de referințe iar al doilea către memoria obiectului gestionat de acel gc::pointer, pentru a elimina un nivel de indirecție de fiecare dată când este dorită accesarea obiectului gestionat. La crearea sau copierea unui gc::ref numărul de referințe din gc::pointer este incrementat, iar la distrugerea



acestuia numărul este decrementat. În acest fel, la sfârșit numărul de referințe rămâne mereu 0 și Garbage Collector-ul știe că poate elibera memoria nefolosită. Cele mai importante funcții din clasa gc::internal sunt run() și new_pointer(), dar conține și un șir cu toate obiectele gc::page pe lângă alte variabile statice cum ar fi thread-ul pe care rulează Garbage Collector-ul sau mutex-ul folosit pentru sincronizarea elementelor șirului. Această împărțire pe “pagini” a fost aleasă deoarece, în acest fel Collector-ul poate curăța listele independent fără a bloca alocarea noilor obiecte.

Funcția new_pointer() returnează un gc::pointer unde poate fi inițializat un nou obiect. Dar mai întâi trebuie găsit un obiect gc::page care sa nu fie plin, iar pentru asta este apelată o altă funcție get_available_page() descrisă în secvența de cod următoare:

//Parcurgem șirul să vedem dacă e vreo pagină liberă std::shared_lock shared_lock{ pages_list_mutex }; for (gc::page &page : pages_list) { if (!page.get_mutex().try_lock()) continue; if (!page.full()) return page; page.get_mutex().unlock(); } // Dacă nu, creăm o pagină nouă și o adăugăm la șir auto *new_page = new gc::page{}; new_page->get_mutex().lock(); { std::lock_guard lock{ pages_list_mutex }; pages_list.emplace(pages_list.begin(), new_page); } // De asemenea notificăm collector-ul că ar trebui să ruleze: condition_variable.notify_all(); return *new_page;

4 Rezultate obținute și optimizări implementate

Pentru testarea performanței algoritmului a fost realizat un test cât mai extrem pentru a scoate în evidentă orice fel de bottleneck ce ar putea apărea într-o aplicație ce necesită performanță sporită. În acest test sunt create 128 de fire de execuție, fiecare creând 216 obiecte gc::ref. Dintre care jumătate din ele sunt stocate într-un std::vector până la finalizarea alocării tuturor obiectelor, pentru a crea atât obiecte cu durată scurtă de viață cât și obiecte ce există pentru o perioadă îndelungată. Iar pentru obținerea unui grafic al memoriei cât și aflarea timpului efectiv de rulare au fost folosite instrumentele de depanare din Visual Studio. După rularea mai multor teste s-a observat că este folosit foarte mult timp căutând un gc::page liber pentru a se putea realiza alocarea unui obiect. Uneori trebuie traversat tot șirul ce conține paginile pentru a aloca un obiect. Acest lucru poate fi observat și în Figura 2. La început utilizarea memoriei crește oarecum linear dar apoi stagnează chiar dacă procesorul este folosit în continuare.



Fig. 2: Rezumtatul primelor teste ale algoritmului

Pentru a remedia această problemă de performanță s-a aplicat o soluție simplă dar foarte eficientă. Înainte de a traversa șirul de pagini pentru a elibera obiectele gc::page nefolosite, algoritmul sortează aceste obiecte în funcție de cât de pline sunt. Altfel, de fiecare dată când se dorește realizarea unei alocări, funcția de alocare are o probabilitate foarte mare să găsească o pagină care nu e plină încă din primele încercări. După această optimizare și altele mai mici, la rularea algoritmului se poate observa o reducere majoră în timpul de execuție a testului, de la 23 de secunde la aproximativ 9 secunde. În același timp în Figura 3 se observă și o mică reducere în cantitatea de memorie folosită.

Fig. 3: Rezultatul testului după primul rând de optimizări

Apoi s-a observat că și în situația în care este găsit un gc::page liber toate firele de execuție trebuie să aștepte unul după celălalt pentru ca alocarea să fie realizată. Din nou rezolvarea acestei probleme de performanță a fost ușor de remediat. În funcția de găsire a unui gc::page disponibil, când iterăm prin șirul de obiecte, în loc ca mutexul să fie blocat, să se verifice dacă pagina este plină și apoi să se deblocheze mutexul, se va încerca mai întâi blocarea mutexului cu funcția try_lock(), iar dacă această încercare eșuează, se trece automat la următorul obiect din șir pentru a nu aștepta după alte fire de execuție sau după Garbage Collector. Mai sus am explicat cum Collector-ul ordonează paginile în funcție de cât de pline sunt. Știind acest lucru, în loc să se parcurgă tot șirul de pagini, dacă după 5 obiecte gc::page pline nu s-a găsit o pagină disponibilă, o nouă pagină este creată direct.



O altă optimizare, mai neconvențională aplicată, este evitarea alocărilor pentru obiecte mici. În caz că se dorește alocarea unui obiect mai mic sau egal cu mărimea unui void*, adică tipul de date folosit pentru stocarea obiectului alocat într-un obiect gc::pointer, folosim acea variabilă pentru stocarea obiectului dorit. Pentru a se realiza acest lucru a fost creată încă o funcție în clasa manager care nu eliberează memoria ci doar îl distruge dacă acel obiect nu este destructibil în mod trivial:

if constexpr (!std::is_trivially_destructible_v<T>) {

auto object = reinterpret_cast<T*>(void_ptr); object->~T();

}

Pentru a reduce memoria folosită de Garbage Collector, în primul rând schimbarea tipului variabilei care conține numărul de referințe de la std::atomic_size_t la std::atomic_uint16_t, în urma unei observații făcute în articolul "Getting Reference Counting Back in the Ring"[5]. În acesta este observat că aproximativ 95% din toate obiectele au un număr maxim de trei referințe, iar în medie 99% din obiecte au un număr maxim de șase referințe sau mai puțin.

După toate aceste îmbunătățiri timpul de execuție a testului descris a fost de doar 3 secunde și în același timp s-a observat înjumătățirea memoriei folosite, acest lucru poate fi remarcat în Figura 4.

Fig. 4: Rezultatul testului după aplicarea tuturor optimizărilor

5 Concluzii și dezvoltări viitoare

Subiectul Garbage Collector-ului este o problema foarte veche și complicată. Nu există un singur mod perfect de a implementa unul. Fiecare Collector are avantajele și dezavantajele proprii așa cum a fost discutat și în acest articol, iar implementarea unui Collector depinde în cea mai mare parte de ce caracteristici sunt dorite de la acesta. Lucrarea de față îmbunătățește Garbage Collector-ul existent în C++ implementând un algoritm de numărare a referințelor la obiecte care să permită unui obiect să știe când un alt obiect îl are ca o referință. Pentru a facilita procesul de cross-platform, algoritmul este implementat sub forma unei biblioteci de cod pentru C++17, simple, ușor de folosit, apelabilă de orice program pentru identificarea și eliberarea zonelor de memorie nefolosite.



Algoritmul de Garbage Collection cross-platform implementat și descris în acest articol poate fi îmbunătățit în continuare prin implementarea unui algoritm de detecție a referințelor circulare, care va crește eficiența algoritmului deja implementat.

6 Bibliografie [1] G. E. Moore, "Cramming more components onto integrated circuits, Reprinted from Electronics,

volume 38, number 8, April 19, 1965, pp.114 ff.", in IEEE Solid-State Circuits Society Newsletter, vol. 11, no. 3, pp. 33-35, Sept. 2006.

[2] Andrade, Paulo Roberto Martins de & Frota, Otavio & Silva, Fátima & Albuquerque, Adriano & Silveira, Robson. (2015). Cross Platform App: A Comparative Study. Journal of Computer Science and Technology. 10.5121/ijcsit.2015.7104.

[3] Garbage colllection, explicarea conceptului de colectare a gunoiului - https://en.wikipedia.org/wiki/Garbage_collection_(computer_science)

[4] Automatic Garbage Collection, explicarea a mai multor tipuri algoritmi - https://caml.inria.fr/pub/docs/oreilly-book/html/book-ora086.html

[5] Rifat Shahriyar & Stephen M. Blackburn & Daniel Frampton, “Getting Reference Counting Back in the Ring” - https://rifatshahriyar.github.io/files/others/rc-ismm-2012.pdf

Filea Răzvan Gheorghe Științe ale Naturii Colegiul Național “Samuel von Brukenthal” Sibiu, România E-mail: [email protected] Prof. Florea Delilah Colegiul Național “Samuel von Brukenthal” Sibiu, România E-mail: [email protected]

about:blank

about:blank

about:blank






Sibiu, Romania

Dynamic Computing 20. De la Formula 1 la Formula-Micro

Melchior Christian, Steavu Nicolae

Rezumat: Omenirea a încercat dintotdeauna să își depășeaopulă limitele, una dintre acestea fiind viteza.

Acest lucru a dus la apariția sportului cu motor, în special a competițiilor de mare viteză, precum

Formula 1. Dynamic Computing 20 (DC 20 2WD) exprimă armonia dintre acest sport cu motor și

ingineria electrică. Bazat pe microcontrolere Arduino[1] și modulele de radio-comunicație NRF24L01,

Dynamic Computing 20 reprezintă o emulare cât mai realistă a unei mașini de Formula 1[2], simulând

cât mai multe funcții ale unei astfel de minunății inginerești, precum: sistem de transmisie diferențială,

sistem DRS, frâne pe disc, sensibilitatea direcției și a frânelor putând fi modificate de „pilot” în timp

real. Radio-comunicația bidirecțională reprezintă una dintre cele mai importante funcționalități ale

proiectului, transmițând comenzile pilotului către mașină, dar și date analitice ale mașini înapoi către

pilot, în timp real.

Abstract: The humanity has always tried to exceed its limits, one of them being the speed. This led to

the emergence of motosports, especially the high-speed competitions, like Formula 1. Dynamic

Computing 20 (DC 20 2WD) express the harmony between this motosport and electrical engineering.

Based on Arduinos microcontrollers and on NRF24L01 radio communication modules, Dynamic

Computing 20 represents a quite realistic emulation of a Formula 1 car, simulating as many functions

as possible of such an engineering wonder, like: differential transmission, Drag Reduction System, disc

brakes, steering and brake sensitivity being able to be changed by the " Pilot " in real time. The two

way communication is one of the most important function of the project, transmitting pilot controls to

the car, but also sending back analytical data of the car to the pilot, in real time.

1 Introducere

O mașină de Formula 1 este o minunăție din punct de vedere ingineresc, mecanic și

electronic. Designul aerodinamic, componentele și culorile vehiculelor diferă de la o echipă

competitoare la alta, dar principiul de bază și funcțiile sunt atent ținute în limita regulilor stricte ale

acestui moto sport. Formula 1 nu are numai un scop de divertisment, competiția dintre echipe

ducând la dezvoltarea eficienței, a performanței, și a siguranței din domeniul auto motiv. Scopul

acestei lucrări a fost de a prezenta un fragment din ingeniozitatea depusă pentru fiecare cursă, dar și

a rezolvării provocării tehnologice de a simula cât mai mult acest moto sport.

În această lucrare o vom prezenta pe Dynamic Computing 20, un automodel cu tehnologii

bazate pe inovațiile din Formula 1. Scopul realizării acestui proiect a fost rezolvarea provocării

tehnologice de a simula cât mai mult acest moto sport și pur divertisment. Pentru construirea

acesteia am folosit o caroserie cu o formă aerodinamică, modelată dintr-un material compozit,

acesta fiind în același timp ușor, maleabil, și foarte rezistent din punct de vedere structural.

Caroseria mașinilor de Formula 1 sunt construite din fibră de carbon, aceste două materiale

asemănându-se destul de mult. Platforma de bază, la fel ca și în Formula 1, este formată dintr-o

placă pe bază de material fibros lemnos. Spre deosebire de Formula 1 motorul lui Dynamic

Computing 20 este unul electric și cutia de viteze are o singură treaptă. Sistemul de transmisie este

unul diferențial, ajutând la viraje. Motorul este controlat cu ajutorul modulului L298N. Dynamic



Computing 20 este dotată cu servo direcție. Ansamblul este controlat cu ajutorul microcontrolerului

Arduino Mega. Servo direcția, sistemul de frânare și sistemul DRS sunt acționate cu ajutorul

servomotoarelor.

2 Componenta fizică

Arduino Mega este un microcontroler (MCU – MicroController Unit), fiind o interfață între

lumea virtuală și cea reală. Acest microcontroler este „creierul” mașinii, asimilând datele primite,

procesându-le, punându-le în practică dar și trimițând datele analitice înapoi la pilot. Arduino Mega

a fost alegerea perfectă pentru această mașină, dispunând de peste 50 de intrări și ieșiri analogice și

digitale, lucru necesar unui proiect așa de complex. Microcontroler-ul este bazat pe chipul

ATmega2560. Partea software a acestui microcontroler se bazează pe un limbaj de programare

similar lui C++.

Fig.1: Placa Arduino Mega

Arduino Nano este versiunea mai mică a lui Arduino Mega. Acesta este bazat pe chipul

ATmega328p, dispunând de mai puțini pini de intrare/ieșire. Nano-ul este centrul de procesare a

datelor primite de la pilot prin intermediul a diferitor componente electronice, cum ar fi butoane,

întrerupătoare, potențiometre, etc. El le transmite mașini, dar pe lângă acestea el mai și primește

date în timp real de la mașină, ca de exemplu temperatura motorului sau numărul de rotați a roților.

Fig.2: Placa Arduino Mega

NRF24L01 este un modul de emisie recepție ce transmite datele în mod wireless. Folosirea

benzii de 2.4GHz aduce după sine mai multe avantaje, ca de exemplu transmisia pe o distanță de

până la 1 Km sau transferul de date la o rată de până la 2Mbps. Acest modul utilizează o antena

externa, lineara cu un câștig de 2dB.



Fig.3: Modulul NRF24L01 cu antena externă

L298N este un driver de control al motoarelor DC cu tensiunea între 5 și 35V. Cu ajutorul

acestui modul se poate controla atât viteza cât și sensul de rotație al motoarelor. Sensul de rotație

este controlat cu ajutorul unei punți H, iar viteza este controlată cu ajutorul unui MOSFET, acesta

întrerupând curentul electric cu o viteză deosebit de rapidă prin intermediul semnalului PWM

(Pulse Width Modulaion) primit de la microcontroler.

Fig.4: Driverul L298N

Fig.5: Modelul de oscilare al semnalului PWM



Fig.6: O schema pentru o punte H

Servomotoarele sunt niște motoare a căror poziție poate fi controlată cu o precizie la nivelul

gradelor. Majoritatea servomotoarelor au o cursă de 180 de grade. Servomotorul este format dintr-

un motor DC, un sistem de reducție a vitezei motorului (crescând puterea de lucru a

servomotorului) un potențiometru atașat de acest sistem de reducție și un circuit electric.

Servomotoarele funcționează în regim de buclă închisă (closed loop), fiindcă poziția motorului,

analizată cu ajutorul potențiometrului, este tot timpul comparată cu comanda care vine de la

microcontroler, sesizând orice diferență, încercând să o corecteze.

Fig.7:Servomotor

Mașina este capabilă să vireze cu ajutorul unui servomotor, aceasta fiind în adevăratul sens

al cuvântului „Servodirecție”. Gradul de viraj al servodirecției este de cca. 10 grade de la stânga la

dreapta. Brațul servomotorului mișcă axa frontală, efectuând un viraj.

Sistemul DRS (Drag Reduction System) după cum spune și acronimul, are rolul de a reduce

forța de frecare cu aerul. Pe partea posterior-superioară a mașini, pe „coada” acesteia, se află un

ansamblu aerodinamic (un stabilizator vertical sau o „aripă” ) cu rolul de a crește coeficientul de

frecare cu aerul schimbându-și poziția dintr-una care se opune curentului de aer în una care lasă

curenți de aer să treacă mai ușor, coeficientul de frecare cu asfaltul pistei scăzând, dar pilotul putând

să ajungă la viteze mult mai mari decât în momentul în care sistemul DRS este inactiv, ajutându-l să

depășească restul competitorilor săi. Sistemul DRS al lui DC20 este acționat de un servomotor,

schimbându-și poziția, aceasta fiind controlată de un buton amplasat pe suprafața de control a

pilotului.



Fig.8: Sistem DRS

Mașinile de Formula 1 trebuie să reducă viteza de la cca. 260-320 Km/h (viteza nominală de

competiție) până la maxim 60Km/h (viteza de virare în siguranță) utilizând un sistem de frânare pe

disc[3]. Avantajul acestei modalități de frânare este ventilarea mai bună a suprafețelor de frecare,

care ajung până la o temperatură de cca. 550 °C. Dynamic Computing 20 se folosește de același

concept. Sistemul de frânare este acționat cu ajutorul unui servomotor, brațele acestuia punând în

mișcare două tije metalice, la extremitatea cărora se află un material cu un coeficient de frecare

ridicat. Acest material intră în contact, la momentul frânării, cu un disc aflat în interiorul jantelor.

Fig.9: Un disc de frâna înroșit datorita forței de frecare

Rotațiile roții sunt monitorizate de un tahometru format dintr-un disc amplasat pe axul roții

și un senzor infraroșu. Pe suprafața discului se află o bandă reflectorizantă, care reprezintă o

revoluție a axei. De fiecare dată când discul se învârte, este măsurată durata de timp de la o trecere a

benzii la alta. Cu ajutorul senzorului și cu un simplu algoritm putem afla RPM-ul ( Rotați Pe Minut)

mașini. Pe suprafața de control a pilotului RPM-ul este reprezentat cu ajutorul a două leduri (1 led

verde și 1 led roșu ).



Fig.10: Senzor infraroșu

Temperatura motorului este analizată cu ajutorul unui termistor NTC. Termistorul este un

tip de rezistor variabil, rezistența căruia variază pe baza temperaturi ambiante. NTC provine de la

Negative Temperature Coefficient, rezistența acestuia fiind invers proporțională cu temperatura,

rezistența crescând o dată cu scăderea temperaturi. Pe suprafața de control, temperatura este

monitorizată cu ajutorul a 2 leduri (1 led verde și 1 led roșu ).

Fig.11: Termistor NTC

3 Componenta logică

Programul acestui proiect a fost realizat majoritar din implementare proprie, dar și cu ajutorul

unor algoritmi open source, cum ar fi algoritmul calculării temperaturi[4] dar și cel pentru

calcularea RPM-ului[5]. Principiul de funcționare a programului este următorul: va parcurge funcția

setup o singură dată, configurând pini de ieșire sau intrare.

void setup()

{

//configurăm starea pinilor driverului ca și OUTPUT

pinMode(enA, OUTPUT);

pinMode(in1, OUTPUT);

pinMode(in2, OUTPUT);

//configurăm pinii servomotoarelor

steering.attach(9);

brake.attach(10);

DRS.attach(11);

}

Apoi va parcurge funcția loop la nesfârșit, sau până când placa nu va mai fi alimentată.

void loop()

{

//se verifică dacă se primește vreun mesaj radio

if (radio.available())

{

//se citește mesajul radio



radio.read(&mesajDePrimit, sizeof(mesajDePrimit));

/*se prelucrează mesajul primind, adaptând valorile brute în valorile care

vor controla viteza, direcția, sistemul DRS și frânele*/

speed = map(mesajDePrimit.Sensor_1, 0, 1023, 0, 255);

Steering = map(mesajDePrimit.Sensor_2, 0, 1023, 70, 95) ;

drs = map(mesajDePrimit.Sensor_3, 0, 1023, 40, 91);

Brakes = map(mesajDePrimit.Sensor_4, 0, 800, 32, 85);

/*creăm o interfața grafică „user-friendly” pentru afișarea valorilor, dar

și pentru sesizarea eventualelor probleme*/

Serial.print("Viteza: ");

Serial.print(speed);

Serial.print(" Directie: ");

Serial.print(Steering);

Serial.print(" DRS: ");

Serial.print(drs);

Serial.print(" Frana: ");

Serial.print(Brakes);

Serial.print(" Marsarier: ");

Serial.print(!mesajDePrimit.Button_1);

Serial.print(" Neutru: ");

Serial.println(!mesajDePrimit.Button_2);

//punem servomotoarele cu diferite roluri în funcțiune

steering.write(Steering);

DRS.write(drs);

brake.write(Brakes);

//condiția butonului de marșarier

if (mesajDePrimit.Button_1)

{

move_forward(speed);

}

else

{

move_backward();

}

//condiția butonului de frânare

if (Brakes > 90 || !mesajDePrimit.Button_2)

{

brakes();

}

}

else

{

//mesaj de afișat în cazul în care conexiunea a eșuat

Serial.println ("EROARE de conexiune");

}

}

De asemenea, pe lângă cele două funcții elementare, au mai fost folosite și altele create

special pentru a nu „îngreuna” codul principal, putând fii mai ușor schimbate, nemaifiind nevoie de

parcurgerea întregului cod de fiecare dată când se identifică o nouă problemă .

//funcție pentru mișcarea înainte, incluzând viteza ca variabila

void move_forward (int speed)

{

digitalWrite(in1, HIGH);

digitalWrite(in2, LOW);

analogWrite(enA, speed);

}

// funcție pentru mișcarea înapoi

void move_backward ()

{

digitalWrite(in1, LOW);




analogWrite(enA, 100);

}

// funcție pentru oprirea motoarelor în cazul frânarii

void brakes ()

{



}

4 Concluzie

Automodelul prezentat simulează un număr considerabil de calități pe care trebuie să

le aibă orice mașină de Formula 1. Caracterul aerodinamic, asemănător cu cel folosit în

prezent de fiecare mașină de Formula 1 aduce un aspect estetic elegant, atrăgând fiecare

privire.

5 Dezvoltări viitoare

Pe lângă aceste funcții mai sunt și multe altele care mai pot fi puse în practică, cum ar fi

sistemul ERS (Energy Recovery System)[6] sau în domeniul auto motive KERS (Kinetic Energy

Recovery System); un balast mobil pentru stabilirea balansului automodelului; frânare diferențială;

diferite moduri de operare a motorului; o cutie de viteze cu mai multe trepte; limitator de viteză

pentru intrarea la boxe; un sistem de limitare a vitezei pe pistă în cazul unei VSC (Virtual Saftey

Car) și altele.

6 Bibliografie

[1] Arduino, https://store.arduino.cc/

[2] Site oficial Formula 1, https://www.formula1.com/

[3] Frânarea în Formula 1https://motorsport.tech/formula-1/formula-one-brakes-explained

[4] Algoritm pentru calcularea temperaturii, https://www.circuitbasics.com/arduino-thermistor-

temperature-sensor-tutorial/

[5] Algoritm pentru calcularea RPM-ului, https://forum.arduino.cc/index.php?topic=634139.0

[6] Glosar cu termeni specificii, https://www.formula1.com/en/championship/inside-f1/glossary.html

Melchior Christian

Colegiul Național “Doamna Stanca”

Informatică

Făgăraș, România


Prof. Steavu Nicolae


Informatică



https://store.arduino.cc/

https://www.formula1.com/

https://motorsport.tech/formula-1/formula-one-brakes-explained

https://www.circuitbasics.com/arduino-thermistor-temperature-sensor-tutorial/

https://www.circuitbasics.com/arduino-thermistor-temperature-sensor-tutorial/

https://forum.arduino.cc/index.php?topic=634139.0

https://www.formula1.com/en/championship/inside-f1/glossary.html






Sibiu, Romania

SmartH

Steavu Nicolae-Constantin, Steavu Nicolae, Steavu Cristina-Elena

Rezumat: Una din cele mai populare și fascinante proiecte care denotă cât de mult a avansat tehnologia

îl reprezintă așa-numitele case inteligente. Exact asta reprezintă și acest proiect. Bazat pe arduino și

modulul cu WiFi Nodemcu esp8266, SmartH reprezintă un concept de casă automată care, folosindu-se

de mai multe piese de profil electric cum ar fi senzori fotosensibili sau de gaz, servomotoare sau LED-

uri este capabilă să controleze lumina din casă în funcție de anumite ore, să deschidă automat uși,

perdele sau să monitorizeze puritatea aerului, totul putând fi controlat și prin intermediul smartphone-

ului.

Abstract: The so-called smart homes are probably one of the most popular and fascinating projects,

showing how much technology has advanced. This is exactly what this project represents.Based on the

Arduino and the Nodemcu esp8266 WiFi module, SmartH is a concept that represents a concept for an

automated home that, using multiple electrical parts such as photosensitive or gas sensors, servomotors

or LEDs, is capable of controlling the lighting in the house depending on the time of the day,

automatically open doors, curtains or to monitor the purity of the air, everything being able to be

controlled via a smartphone.

1 Introducere

Casa inteligentă, dotată cu sisteme smart, a trecut stadiul de concept și a ajuns realitate. Este

deja la îndemâna noastră și nu ține doar de comoditate. O casă inteligentă (smart home) este

locuința în care se automatizează și se controlează de la distanță aspecte ce țin de confortul

ambiental și nu numai. Unele echipamente pot lua decizii în funcție de anumiți parametri, pentru a

crește confortul locatarilor sau pentru a economisi energie.

Pot, de exemplu, să schimbe lumina ambientală în funcție de momentul zilei, pot să

pregătească ceașca de cafea la o oră presetată, pot să descuie și să încuie ușile când plecăm și când

ajungem acasă, să aprindă lumina, să pornească sistemul de încălzire sau de răcire, dar și să tragă

draperiile.

Primul aspect ce ține de confortul nostru și pe care am reușit să-l controlăm de la distanță este

iluminarea casei. Stingerea și aprinderea luminii la o simplă bătaie din palme este posibilă încă din

1985, odată cu apariția sistemului Clapper și cu toții am văzut în diverse filme sau serii animate un

personaj stingând lumina în acest fel. Astăzi pare un sistem rudimentar, însă el poate fi privit ca un

prim mod de a ne conecta iluminarea la propriile gesturi, un adevărat precursor al sistemelor ce nu

ne obligă să ne mai dăm jos din pat când vrem să stingem lumina.

SmartH reprezintă o machetă a unei case inteligente, care cu ajutorul plăcilor de dezvoltare

Arduino Uno și Arduino Nano și a modului ESP8266 incorporează mai multe aspecte ale unei case

inteligente. În partea doua vor fi prezentate piesele folosite, iar în partea a treia se va vorbi despre

cum sunt interconectate piesele și ce feature-uri are ansamblul.



2 Componenta fizică

Arduino UNO este o platformă de procesare open-source, bazată pe software și hardware

flexibil și simplu de folosit. Constă într-o platformă de mici dimensiuni construită în jurul unui

procesor de semnal și este capabilă de a prelua date din mediul înconjurător printr-o serie de senzori

și de a efectua acțiuni asupra mediului prin intermediul luminilor, motoarelor, servomotoare, și altor

tipuri de dispozitive mecanice. Procesorul este capabil sa ruleze cod scris într-un limbaj de

programare foarte similar cu limbajul C++. Placa Arduino nano este foarte similară cu aceasta,

diferența cheie fiind faptul că este mult mai mică..

Fig 1: Placa Arduino Uno

Fig 2: Placa Arduino Nano

Senzorii ultrasonici [1] se bazează pe un princiu similar radarului sau sonarului, care

evaluează poziția unui obiect interpretând ecourile undelor radio respectiv sonore. Senzorii

ultrasonici activi generează sunete cu frecvență înaltă, primind înapoi ecoul, măsurând intervalul de

timp dintre trimiterea și primirea semnalului. Astfel determină distanța la care se află față de un

obiect. Senzorii ultrasonici pasivi sunt practic microfoane care captează sunete în anumite condiții.



Fig. 3: Modul de funcționare al senzorului HC-SR04

Rezistoarele fotorezistente reprezintă o bază electronică. Dacă este nevoie de o modalitate de

a simți nivelul luminii ambientale, atunci nu există un mod mai eficient de a face acest lucru decât

cu ajutorul unui fotorezistor. Fotorezistorul este fabricat dintr-un material semiconductor, iar

conductivitatea se modifică odată cu variația luminanței.

Fig. 4: Fotorezistorul 5528 LDR

Modulul ESP8266 oferă o soluție completă și autonomă de rețea Wi-Fi, permițându-i să

găzduiască aplicația sau să descarce toate funcțiile de rețea Wi-Fi de la un alt procesor de aplicații.

ESP8266 dispune de capacități puternice de procesare și stocare la bord care îi permit să fie integrat

cu senzorii și alte dispozitive specifice aplicației prin GPIO-urile (general purpose input/output)

sale, cu o dezvoltare minimă în față și o încărcare minimă în timpul funcționării. Gradul ridicat de

integrare pe cip permite circuite externe minime, iar întreaga soluție, inclusiv modulul frontal, este

proiectată să ocupe zona minimă de PCB.



Fig.5: Modulul WiFi ESP8266

Senzorul MQ135 [2] este senzibil la amoniac, benzen, hidrogen la o concentrație de la 10

până la 10.000 ppm. Senzorul are o conductivitate scăzută în aerul curat, iar când în aer există

gazele țintă, conductivitatea senzorului este mai mare, împreună cu creșterea concentrației de gaz.

Este recomandat să se convertească schimbarea conductivității pentru a obține concentrația de gaz

din atmosferă. Senzorul MQ135 are o sensibilitate ridicată la aburul de amoniac, sulf și benzen, este

sensibil la fum și alte gaze nocive.

Fig. 6: Senzorul de gaz MQ-135



Alte piese folosite sunt servomotoare, LED-uri, un LED RGB și mai multe cabluri.

Fig. 7: Servomotoare și mai multe tipuri de LED-uri

3 Modul de organizare al pieselor și funcțiile acestora

La fel ca orice calculator, Arduino [3] funcționează într-o buclă infinită. Când este alimentat

(sau după ce un program nou a fost uploadat), se execută o secțiune de setări după care se intră

automat într-o zonă denumită loop. Modulul WiFi se bazează tot pe Arduino.

Piesele vor fi organizate după scopul pe care îl îndplinesc. De modulul WiFi vor fi legate

fotorezistorul și LED-ul, deoarece acestea vor avea nevoie de WiFi pentru a-și îndplini funcțiile.

LED-ul are două moduri: cel automat, în care LED-ul se aprinde/stinge în funcție de valoarea

returnată de fotorezistor, și cel manual, unde utilizatorul controlează LED-ul. Pentru ca utilizatorul

să comunice cu placa ESP, va fi folosită aplicația Blynk [4], care prin intermediul widgeturilor

transmite informații de pe smartphone. Mai precis, ne vom folosi de butoane, care pot modifica

starea unui pin digital de la LOW la HIGH sau invers și de funcția digitalRead(pin) din librăria

standard Arduino, care citește valoarea pinului.



Fig. 8: Codul de pe ESP

Fig. 9: Modulul WiFi ESP8266 de care sunt legat fotorezistorul și un LED

Fig. 10: Interfața aplicației Blynk



De placa Arduino Nano vor fi legate senzorul de gaz și LED-ul RGB care se va colora în

funcție de calitatea aerului din cameră: verde dacă aerul este curat, albastru dacă se află puțin gaz în

atmosferă, și roșu dacă nivelul de gaze este periculos și camera trebuie evacuată.

Fig. 11: Placa Arduino Nano de care sunt conectate senzorul de gaz și LED-ul RGB

De placa Arduino vor fi legate celelalte piese, adică cele două servomotoare și senzorii

ultrasonici. Acestea vor funcționa separat, necomunicând cu modulul ESP. Servomotorul va

deschide, respectiv închide ușa casei. Senzorul HC-SR04 va fi așezat în fața casei, putând detecta

dacă cineva se află sau nu în fața casei. În caz afirmativ, ușa se va deschide pentru o scurtă perioadă

de timp.

Pentru a implementa această funcție s-au folosit librăriile Servo.h și NewPing.h, ce ne permit

să controlăm servomotoarele respectiv senzorii ultrasonici. Librăria NewPing ne permite să îi setăm

senzorului o distanță maximă pe care o poate returna în momentul declarării acestuia, iar funcția

ping_cm returnează distanța în centimetri a celui mai apropiat obiect detectat de senzor, sau 0, dacă

nu se află nimic în raza acestuia. La fel ca și în cazul luminilor, utilizatorul poate controla când se

poate deschide ușa prin intermediul aplicației Blynk. Pinul 7 al plăcii Arduino este conectat la pinul

1 al modulului WiFi, ce poate fi controlat de utilizator via Blynk.



Fig. 12: Codul de pe Arduino UNO alături de explicații

Fig. 13: Placa Arduino Uno de care sunt legați senzorul ultrasonic și servomotorul

4 Concluzii și dezvoltări viitoare

Conceptul de casă inteligentă prezentat este deosebit de eficient, neavând nevoie de resurse

umane sau de instalator. Reprezintă o modalitate foarte ieftină de a automatiza elemente dintr-o

casă modernă, cum ar fi luminile sau ușa. Acestea ar ușura viață utilizatorilor. De asemena, senzorul

de gaz și ușile automatizate ce pot fi dezactivate contribuie la securizarea casei, utilizatorul putând

fi avertizat în cazul anumitor pericole. Există o multitudine de piese ce pot fi adăugate pentru a

îmbunătăți ansamblul. Însă probabil cel mai mult impact l-ar avea trecerea de la o placă arduino la o



placă raspberry pi, care ne-ar permite să dezvoltăm proiectul adăugând o multitudine de alte funcții

și putând dezvolta pe cele existente. De exemplu, folosind limbajul python am putea crea o aplicație

de web scraping, care preia informații legate de vreme sau anotimp și va putea seta temperatura

optimă, nemaifiind nevoie de un fotorezisor.

5 Bibliografie

[1] Specificații tehnice și modul de funcționare ale senzorului ultrasonic HC-SR04,

https://www.acmesystems.it/HC-SR04

[2] Specificații tehnice ale senzorului de gaz MQ-135, https://components101.com/sensors/mq135-gas-

sensor-for-air-quality

[3] Site-ul oficial Arduino, de unde am preluat diverse funcții/librării, https://www.arduino.cc/

[4] Site-ul Blynk, ce prezintă cum se folosește aplicația, https://blynk.io/en/getting-started

Steavu Nicolae-Constantin





Prof. Steavu Nicolae


Informatică



Prof. Steavu Cristina-Elena


Informatică/Matematică



https://www.acmesystems.it/HC-SR04

https://components101.com/sensors/mq135-gas-sensor-for-air-quality

https://components101.com/sensors/mq135-gas-sensor-for-air-quality

https://www.arduino.cc/

https://blynk.io/en/getting-started







Sibiu, Romania

Bibliotecă de Funcţii Calendaristice

Benke Denis, Bocotan Raluca, Cîrjean Costică

Rezumat: Lucrarea prezintă o bibliotecă de funcţii scrisă în limbajul C++. Funcţiile din bibliotecă

implementeaza un grup de operatii pentru date calendaristice. Operatiile folosesc in comun date si

subprograme reunite in două fisiere antet.Validarea rezultatelor a fost realizata prin compararea cu

funcţii similare din aplicaţia MS Office Excel si prin testarea cu date din calendarul Gregorian.

Abstract: The paper presents a library of functions written in C ++ language. Library functions

implement a set of operations for calendar data. The operations share data and subprograms together in

two header files. The validation of the results was done by comparing with similar functions in the MS

Office Excel application and by testing with data from the Gregorian calendar.

1 Introducere

La nivelul clasei a X-a, cu specializarea matematică-informatică intensiv informatică, o

cerinţă este realizarea de proiecte în care subprogramele sa fie organizate in biblioteci.

Tema lucrării este “Biblioteca pentru date calendaristice”, numele provenind de la domeniul

de date abordat în lucrare precum si de la modul de organizare a lucrării.

Subiectul lucrării ne-a fost sugerat de două probleme propuse, din manual [1], la capitolul de

structuri de date. O problemă se referă la diferenţa în număr de zile între două date calendaristice şi

a doua problemă se referă la data calendaristică obţinută prin adunarea unui număr de zile la data

indicată. Numele programelor, “pb3pag88cls10” şi “pb4pag88cls10”, care rezolvă cele două

probleme, indică numărul problemei propuse şi pagina din manual unde se găseşte enunţul

problemei.

De la disciplina TIC, tot în clasa a X-a, am luat cunoştinţă cu biblioteca de funcţii pentru date

calendaristice si timp, din aplicaţia MS Office Excel, fata de care ne-am raportat rezultatele noastre.

Cu ocazia aceastei lucrări am întâlnit preocuparea marelui matematician german Gauss,

pentru calcule calendaristice si am implementat formula sa de calcul a zilei din săptămână pentru

data de 1 ianuarie a unui an precizat ca variabilă [2].

Tot cu ocazia acestei lucrări am ajuns la cunoştinţa existenţei în limbajul C++, a altor

biblioteci pentru dată şi timp [3, 4].

Originalitatea lucrării constă în modul de abordare a subiectului prin rezolvarea celor două

probleme şi extinderea şi la o altă problemă înrudită, în care trebuie calculată ziua din săptămână

în care cade o anumită dată.

Calculul diferenţei în zile între două date calendaristice efectuat în programul din aplicaţie

este exact în raport cu cel similar din categoria de funcţii pentru dată calendaristică, Day360,din

aplicaţia Excel, unde se aproximează anul la 360 de zile (30 de zile pe lună ).

Subprogramele si datele specifice prelucrărilor cu date calendaristice, sunt memorate în două

fişiere antet , care prin directiva “include” au fost incluse în fiecare din programele de testare pentru

biblioteca realizată în această lucrare.



2 Descrierea bibliotecii de functii calendaristice

2.1 Datele

data, tip structurat cu campurile pentru zi, luna, an

luna, tablou unidimensional cu numărul de zile al fiecărei luni

ziuas, tablou unidimensional cu numarul zilei din săptămână, pentru o zi din luna,

aceeaşi pentru fiecare dintre lunile unui an

denziua, tablou unidimensional cu denumirile celor şapte zile ale săptămânii

2.2 Subprogramele

an bisect returnează 1 sau 0, după cum anul este sau nu este bisect

are ca parametru valoarea numerică a anului

este apelat înaintea utilizării unui nou an

necesar pentru stabilirea numărului de zile ale lunii februarie

gauss_1ian returnează numărul zilei din săptămână al zilei de 1 ianuarie

are ca parametru anul pentru care se consideră data de 1 ianuarie

este varianta prin care se obţine automat un reper

reperul poate fi folosit în alt subprogram pentru calculul zilei din săptămână

ziua1 este o procedură care pentru fiecare lună din an depune o valoare în poziţia

corespunzătoare din vectorul ziuas

are ca parametri anul şi ziua săptămânii din luna ianuarie

calculează ziua din săptămână pentru fiecare din celelalte 11 luni

datacmp compară două date calendaristice x şi y şi returnează 1, 0 sau -1

are ca parametri cele două date calendaristice, x şi y

dacă x > y returnează 1

dacă x = y returnează 0

dacă x < y returnează -1

necesar pentru operaţia de scădere a două date calendaristice

suma_luni returnează suma zilelor, de la începutul anului până la data indicată

are ca parametru data indicată

necesar pentru operaţia de scădere a două date calendaristice

incdata returnează o dată calendaristică obţinută ca suma dintre o dată şi un număr

natural

are ca parametri o dată calendaristică şi un număr natural

calculează o dată viitoare

decdata returnează o dată calendaristică obţinută ca diferenţa dintre o dată şi un număr

natural

are ca parametri o dată calendaristică şi număr natural

calculează o dată precedentă

3 Implementare

3.1 calendar.h

int luna[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};

int ziuas[13]={0};

const char *denziua[]={" ",

"Luni",

"Marti",

"Miercuri",



"Joi",

"Vineri",

"Sambata",

"Duminica"};

struct data{int z,l,an;};

void ziua1(int an,int zs);

int an_bisect(int an);

int datacmp(data x,data y);

int suma_luni(data x);

void incdata(data &d,int n);

void decdata(data &d,int n);

int gauss_1ian(int an);

3.2 calendar.cpp

int an_bisect(int an)

{

return (an%100!=0 && an%4==0) or (an%400==0);

}

int gauss_1ian(int an)

{

int s=1;

s+=5*((an-1)%4)+4*((an-1)%100)+6*((an-1)%400);

return (s%7);

}

void ziua1(int an,int z1)

{

int i;

if (z1==0) z1=7;

ziuas[1]=z1;

for(i=2;i<=12;i++)

{

z1=(z1+luna[i-1]%7)%7;

if (z1==0) z1=7;

ziuas[i]=z1;

}

}

int datacmp(data x,data y)

{

//compara doua date calendaristice

if (x.an>y.an) return 1;

if (x.an==y.an)

{

if (x.l>y.l) return 1;

else

{

if(x.l==y.l)

{

if (x.z==y.z) return 0;

else if (x.z>y.z) return 1;

}

else if(x.l>y.l) return 1;

}

}

return -1;

}



int suma_luni(data x)

{

int s=0,i;

if (an_bisect(x.an)&& x.l>2) s=1;

for(i=1;i<x.l;i++)

s+=luna[i];

return s;

}

void incdata(data &d,int n)

{

int i;

// data este incrementata zi cu zi pana la n zile

i=0;

luna[2]+=an_bisect(d.an);

while (i<=n)

{

while ((++i<=n)&& (++d.z<=luna[d.l]));

if (i<=n)

{

d.z=1; d.l++;//luna urmatoare

if (d.l>12) {d.l=1;

d.an++;luna[2]=28;//anul urmator

luna[2]+=an_bisect(d.an);}

}

}

}

void decdata(data &d,int n)

{

int i;

// data este decrementata zi cu zi pana la n zile

i=0;

luna[2]=28+an_bisect(d.an);

while (i<=n)

{

while ((++i<=n)&& (--d.z>0));

if (i<=n)

{

d.l--;//luna precedenta

if (d.l==0) {d.l=12;

d.an--;//anul urmator

luna[2]=28+an_bisect(d.an);}

d.z=luna[d.l];

}

}

}

3.3 Programe de testare a funcţiilor din biblioteci

Programul “ziua1”

#include <iostream>

#include <iomanip>

#include <fstream>

#include "calendar.h"

#include "calendar.cpp"

using namespace std;



int main()

{

cout<<"Calculez ziua din saptamana,pentru fiecare luna a aceluiasi

an,in care cade aceeasi zi din luna"<<endl;

int an;

cout<<"Introduceti anul : "; cin>>an;

if (an_bisect(an))luna[2]=29;

int nrzl;

cout<<"Introduceti numarul zilei din luna :"; cin>>nrzl;

int z1,i;

cout<<"calculez ziua din saptamana pentru 1 ianuarie "<<an<<endl;

z1=gauss_1ian(an);cout<<z1<<endl;

cout<<"calculez ziua din saptamana pentru "<<nrzl<<" ianuarie

"<<an<<endl;

z1=((nrzl-1)%7+z1)%7; cout<<z1<<endl;

cout<<" Ziua de "<<nrzl<<" in fiecare luna a anului "<<an<<endl;

ziua1(an,z1);

for(i=1;i<=12;i++)

cout<<"luna "<<setfill('0')<<setw(2)<<i<<" ziua :

"<<denziua[ziuas[i]]<<endl;

//========================================

char c; cout<<" Salvati in fisierul calendar.out ?(d/n):";

cin>>c;

if (c=='d'|| c=='D')

{

ofstream fout("calendar.out");

fout<<" Ziua de "<<nrzl<<" in fiecare luna a anului "<<an<<endl;

for(i=1;i<=12;i++)

fout<<"luna "<<setfill('0')<<setw(2)<<i<<" ziua :

"<<denziua[ziuas[i]]<<endl;

fout.close();

}

return 0;

}

Programul “pb3pag88cls10”

#include <iostream>




int main()

{

data d; int n;

cout<<" Calculez suma dintre o data calendaristica si un numar de

zile"<<endl;

cout<<"Introdu data calendaristica zi luna an : ";

cin>>d.z>>d.l>>d.an;

cout<<"Introdu numarul de zile : ";

cin>>n;

incdata(d,n);

cout<<"data incrementata cu "<<n<<" zile= "<<d.z<<"."<<d.l<<"."<<d.an;

}

Programul “pb3pag88cls10ext”

#include <iostream>






int main()

{

data d; int n;

cout<<" Calculez diferenta dintre o data calendaristica si un numar de

zile"<<endl;

cout<<"Introdu data calendaristica zi luna an : ";

cin>>d.z>>d.l>>d.an;

cout<<"Introdu numarul de zile : ";

cin>>n;

decdata(d,n);

cout<<"data decrementata cu "<<n<<" zile= "<<d.z<<"."<<d.l<<"."<<d.an;

}

Programul “pb4pag88cls10”

#include <iostream>




int main()

{

// diferenta in zile intre doua date calendaristice

data d1,d2,d;

cout<<"Introducet data1 prin zi luna an ";

cin>>d1.z>>d1.l>>d1.an;

cout<<"Introducet data2 prin zi luna an ";

cin>>d2.z>>d2.l>>d2.an;

// ordonarea celor doua date

if (datacmp(d1,d2)==1)

{

d=d1; d1=d2; d2=d;

cout<<d1.z<<" "<<d1.l<<" "<<d1.an;

}

// diferenta dintre cele doua date, in numar de zile

int z1, z2=0;

z1=suma_luni(d1)+d1.z;

int i;

if (d1.an==d2.an) z2=suma_luni(d2)+d2.z;

else

{

for(i=d1.an;i<d2.an;i++)//suma zilelor din ani

{z2+=365+an_bisect(i);cout<<i<<":"<<z2<<endl;}

z2+=suma_luni(d2)+d2.z;

}

cout<<"Diferenta in zile intre cele doua date = "<<z2-z1;

return 0;

}



4 Testare

4.1 Testarea subprogramelor gauss_1ian si ziua1 din biblioteca

Rezultatele programului de testare ziua1

Error!

Calculez ziua din săptămână pentru ziua 17, pentru fiecare luna a anului 2020

EXCEL

year month day date weekday

2020 1 17 17.01.2020 5

2020 2 17 17.02.2020 1

2020 3 17 17.03.2020 2

2020 4 17 17.04.2020 5

2020 5 17 17.05.2020 7

2020 6 17 17.06.2020 3

2020 7 17 17.07.2020 5

2020 8 17 17.08.2020 1

2020 9 17 17.09.2020 4

2020 10 17 17.10.2020 6

2020 11 17 17.11.2020 2

2020 12 17 17.12.2020 4

Confruntarea rezultatelor obţinute in cele două rulări cu aceleaşi date şi acelaşi tip de

prelucrare arată rezultate identice !

4.2 Testarea subprogramelor incdata şi decdata

Rezultatele programului de testare pb3pag88cls10



Excel Calcularea expresiei datay=datax+n

datax n zile datay

31.12.2020 60 01.03.2021

Rezultatele programului de testare pb3pag88cls10ext

Excel Calcularea expresiei datay =datax-n

datax n zile datay

01.03.2021 60 31.12.2020

Confruntarea rezultatelor obţinute in cele două perechi de rulări, C++ si Excel, cu aceleaşi

date şi acelaşi tip de prelucrare arată rezultate identice !

4.3 Testarea subprogramelor datacmp si suma_luni

Cu această ocazie am aflat că aplicaţia Excel codifică datele calendaristice printr-un număr

de zile socotite de la 1.1.1900 până la data respectivă şi astfel am ajuns să interpretăm corect unul

dintre rezultatele de mai jos obţinute de Excel.

Rezultatele obţinute la rularea programului de testare difdata

Mesajul 2020:366 arata că totalul zilelor din anul 2020 este 366 (s-a detectat an bisect prin

functia din bibliotecă an_bisect). Scăderea a două date, cu rezultat în număr zile l-am realizat

luând ca reper începutul anului mai vechi.

Anul mai vechi l-am determinat cu subprogramul datacmp.

Totalul zilelor, începand cu data primei zile din anul mai vechi, l- a realizat subprogramul

suma_luni.

Excel Calculez diferenta datax -datay

datax datay n

01.03.2021 31.12.2020 29.02.1900



Rezultatul în număr de zile, apare de fapt ca o data calendaristică. Practic, în loc de 0 ani Excel scrie

anul 1900, pe care îl consideră un moment 0. În schimb 29.02 .1900 mai înseamnă şi primele 60 de

zile din data rest, deci se confirmă rezultatul corect furnizat de subprogramele de bibliotecă !

5 Concluzie

Biblioteca de funcţii pentru date calendaristice, în stadiul prezentat în acest articol, permite

realizarea unei părţi dintr-o mulţime de operaţii care pot fi executate cu datele calendaristice.

Ne punem speranţa şi în bibliotecile cu funcţii pentru date calendaristice, aflate în limbajul

C++, enumerate la bibliografie , pentru a creşte eficacitatea utilizării bibliotecii prezentate aici.

6 Bibliografie

[1] MILOŞESCU Mariana, Informatică, Profilul real, Specializarea matematică-informatică, intensiv

informatică, manual pentru clasa a X-a, Editura Didactică şi Pedagogică, R.A., Bucureşti, 2005

[2] Determination of the day of the week,

https://en.wikipedia.org/wiki/Determination_of_the_day_of_the_week

[3] C Time Library, http://cplusplus.com/reference/ctime/

[4] Date and time utilities, https://en.cppreference.com/w/cpp/chrono

Benke Denis

Colegiul “Nicolae Titulescu” Braşov

Matematică-informatică, Informatică intensiv

Braşov, România

Bocotan Raluca


Matematică-informatică, Informatică intensiv

Braşov, România

Prof. Cîrjean Costică


Informatică

Braşov, România


https://en.wikipedia.org/wiki/Determination_of_the_day_of_the_week

http://cplusplus.com/reference/ctime/

https://en.cppreference.com/w/cpp/chrono





Sibiu, Romania

Modalități Uzuale de Implementare a Teoriei Grafurilor și Aplicații

Topan Oana-Maria, Horvath Krisztina-Aliz, Giurgea Mihaela, Racolta Andreea

Rezumat: Această lucrare face o sinteză a proiectelor unei clase de elevi. Aceștia au avut de realizat o

aplicație în care să folosească noțiunile de teoria grafurilor studiate la ora de informatică. Nu au avut

restricții sau condiționări, doar li s-a impus să utilizeze ca noduri în graf un număr de 10-15 obiective

turistice din Cluj-Napoca. Proiectele realizate au fost originale, realizate în c++/c#. Elevii și-au dat seama

că în viața cotidiană sunt aplicați mulți dintre algoritmii învățați.

Abstract: This paper is an integration of a class of student’s projects. They had to build an application

that operated using concepts from the theory of graphs studied at our programming class. There were no

restrictions, nor conditions, all they were asked to implement was the usage of 10-15 tourist attractions

in Cluj-Napoca for the nodes of the graph. The projects that were presented were creatively thought-out

and programmed in c++ or c#. The students realised that all the algorithms they had learned surrounded

them in the real world.

1 Introducere

Aplicațiile create de elevi din clasa a XI-a au avut în vedere crearea unor programe eficiente,

care să returneze drumurile cele mai scurte dintre anumite obiective turistice clujene, având în

vedere anumite condiții impuse pentru un turist venit în Cluj-Napoca. În implementarea proiectelor

s-au utilizat algoritmi studiați la școală: algoritmul lui Dijkstra, Roy-Floyd, Roy-Warshall, Kruskal

și de asemenea diverse metode de programare: greedy, backtracking și Divide et Impera. Algoritmii

au fost implementați în C++ și C#. În acest proiect vor fi prezentate teoria (grafuri, backtracking,

Divide et Impera etc.) pe care colegii noștri au învățat-o la clasă și proiectele concepute și realizate

de către elevii clasei a XI-a. În acest fel, colegii au învățat să lucreze împreună la un proiect de

informatică și au aprofundat ceea ce au învățat la școală.

2 Capitol Teoria grafurilor. Metode de programare.

În realizarea proiectelor, au fost utilizate noțiuni ale teoriei grafurilor. În primul rând, s-au

identificat cele două categorii mari de grafuri, cele orientate, care se referă la sensul arcelor,

respectiv neorientate, care se referă la muchii (care nu țin cont de sens). [1],[4]

Gradul unui nod este dat de numărul de muchii care intră/ies din acesta [4]. În figura 1 sunt

prezentate muchiile adiacente unui nod central.



Fig. 1: Reprezentarea unui nod central

Matricea de adiacență este metoda cea mai frecvent folosită în memorarea

muchiilor/arcelor unui graf. [1]

Un graf neorientat este complet dacă are un număr maxim de muchii. (Fiecare nod este

conectat cu toate celelalte). [1]

Se numește lanț o succesiune de noduri cu proprietatea că oricare două noduri consecutive

sunt adiacente. [4] Echivalentul lanțului într-un graf orientat este drumul, doar că arcele au un sens

ce trebuie respectat. În figura 2 sunt prezentate muchiile ce fac legătura între nodurile consecutive

ale lanțului.

Fig.2: Reprezentarea unui lanț

Un ciclu este un lanț simplu, unde primul nod este egal cu ultimul. Circuitul este echivalentul

ciclului în grafurile orientate. Figura 3 reprezintă un ciclu în graful format din puncte turistice din

Cluj-Napoca.

Fig.3: Reprezentarea unui circuit

O componentă conexă este o mulțime de noduri, toate conectate prin lanțuri. Un graf conex

este unul pentru care în oricare două noduri există un lanț. [1]



În proiecte, deseori s-a construit matricea drumurilor folosind algoritmul Roy-Warshall, care

determină existența unui drum între oricare două noduri. În figura 4 am ilustrat un graf care are

drumuri care trec prin toate nodurile. [4]

Fig. 4: Reprezentarea unui graf

Algoritmul Roy-Floyd s-a implementat în multe proiecte, pentru a determina drumul de cost

minim între oricare două noduri. [5]

Algoritmul lui Dijkstra determină costul minim de la un nod dat la toate celelalte.

În figura 5 s-a reprezentat un graf în care toate muchiile sunt incidente cu un nod. [6]

Fig. 5: Reprezentarea muchiilor dintr-un nod dat

Unele proiecte au folosit metoda Divide et Impera, împărțirea problemei în mai multe

subprobleme, ajungând la soluții simple pe care le combină pentru a găsi soluția finală. [3]

3 Descrierea proiectelor

Au fost multe proiecte făcute de elevi care au pornit de la aceeași idee. Elevii s-au gândit la o

poveste care să îi ajute să facă aplicația interactivă și interesantă. Mulți au decis să folosească ideea

că un prieten vine din altă țară și dorește să facă un tur al orașului, să vadă obiective cât mai

interesante într-un timp scurt, pentru că e limitat. Unele proiecte au decis să găsească drumul cel

mai scurt de la un obiectiv turistic ca și obiectiv central, până la toate celelalte, folosind algoritmul

lui Dijkstra.

Algoritmul lui Dijkstra determină drumul minim de la un nod dat la toate celelalte. Se

folosește un vector pentru a marca nodurile pe care le-am vizitat, un vector care reține distanțele

minime de la nodul de pornire la toate celelalte și un ultim vector pentru predecesorii nodurilor, util

pentru reconstituirea traseului unui drum minim. În figura 6 este prezentat algoritmul lui Dijkstra



folosit de colegii noștri pentru determinarea drumului minim. Folosind un algoritm de tip Greedy

(optim local) se determină valorile minime ale drumurilor.

Fig. 6: Algoritmul lui Dijkstra folosit într-un proiect

O altă aplicație generează cu ajutorul unui meniu în consolă drumul minim dintr-un nod în

altul, verificarea dacă un drum dat este circuit, determinarea nodului central, calcularea drumului de

distanță maximă. Meniul se apelează odată ce este deschis programul sau odată ce a fost completată

o instrucțiune pe care o apelezi prin tastarea numărului dorit. În figura 7 este codul care face posibil

meniul în consolă. Funcția Display() afișează un meniu, prima dată se afișează titlul. Apoi se face o

listă a obiectivelor turistice pe hartă, folosind o repetitivă și structuri. Apoi se afișează ceea ce poate

să facă programul respectiv, lăsând câte-un rând liber pentru a fi mai ușor de citit. Funcția

DisplayInstructiuni() este folosită ca să se afișeze instrucțiunile de la începutul programului.



Fig. 7: Codul folosit pentru crearea unui meniu în consolă

Algoritmul Roy-Floyd a fost folosit în calcularea matricei de distanțe minime. Unul dintre

proiectele în care a folosit acest algoritm a ilustrat graful distanțelor. În figura 9 este reprezentat un

graf folosit de colegi pentru a ilustra cu exactitate distanțele între obiectivele turistice și plasarea lor

pe harta Clujului.

Fig.9: Reprezentare grafică a unui graf folosit în proiectul unor elevi.

Algoritmul Roy-Floyd calculează distanțele minime dintre fiecare nod, având complexitate

cubică. În figura 10 am prezentat algoritmul lui Roy-Floyd, care este comentat în codul sursă.

Fig. 10: Algoritmul lui Roy-Floyd folosit într-un program



Metoda Backtracking a fost folosită în găsirea drumului minim, unde s-a impus restricția să se

treacă de maxim două ori printr-un nod al grafului. Figura 11 este o exemplificare a algoritmului de

backtracking folosit într-un proiect al colegilor.

Fig. 11: Funcția de backtracking folosită

Un proiect care a realizat reconstituirea traseului parcurs după utilizarea unei metode de

calculare a drumului minim, s-a făcut folosind metoda Divide et Impera. În figura 12 este o parte

din programul colegilor care folosește metoda Divide et Impera. Funcția divide_et_impera()

determină traseul de la un punct la alt punct, găsind punctele intermediare.

Fig. 12: Funcția de divide et impera folosită

Un alt proiect a fost realizat în Scratch și a constat într-o animație, o călătorie virtuală la

obiectivele orașului.

4 Literature Review

În această secțiune, vor fi prezentate pe scurt alte proiecte unde s-au folosit algoritmii pe care

i-am învățat la clasă. „An Investigation of Dijkstra and Floyd Algorithms in National City Traffic



Advisory Procedures” 7 este o lucrare care studiază traficul și cum se pot folosi algoritmii lui

Dijkstra și a lui Floyd pentru a remedia sistemul de avertisment pentru zonele congestionate.

Lucrarea “Transitive closure according to Roy-Floyd-Warshall” cercetează cum metoda

matematică prin care se verifică tranzitivitatea matricelor poate fi scrisă sub forma unui limbaj de

programare. De asemenea, multe studii în care s-au folosit noțiuni și algoritmi de grafuri sunt în

domeniul Social Media [9]. “Grafurile circuitelor electrice” sunt o metodă de analiză în domeniul

circuitelor electrice complexe [10].

5 Concluzie

Scopul proiectelor a fost identificarea utilizărilor teoriei grafurilor în viața cotidiană. Elevii au

aprofundat noțiunile învățate la clasă și au descoperit utilitatea acestora. Proiectele au fost foarte

creative. Toate au avut la bază câte o poveste imaginară, care le-a dat un scop bine definit.

Prezentarea proiectelor s-a realizat în Microsoft Powerpoint. Elevii și-au împărțit munca. Ei au

lucrat 2-3 la un proiect. Unii s-au ocupat mai mult de partea de implementare, alții de selectarea

obiectivelor, calcularea distanțelor la scară, determinarea coordonatelor. (Google Maps)

Pe parcursul celor 2 săptămâni de muncă, elevii au fost entuziaști de la început și până la

sfârșit. Ei au dobândit calități de lucru în echipă, managementul timpului, învățare activă, întregul

proiect fiind o experiență benefică.

6 Bibliografie

[1] Grafuri neorientate, https://www.pbinfo.ro/articole/810/grafuri-neorientate

[2] Metoda backtracking, https://www.pbinfo.ro/articole/16597/metoda-backtracking

[3] Divide et Impera, https://www.pbinfo.ro/articole/7651/divide-et-impera

[4] Grafuri orientate, https://www.pbinfo.ro/articole/509/grafuri-orientate

[5] Algoritmul Roy-Floyd-Warshall, https://www.pbinfo.ro/articole/5887/algoritmul-roy-warshall-

floyd

[6] Algoritmul lui Dijkstra, https://www.pbinfo.ro/articole/6135/algoritmul-lui-dijkstra

[7] An Investigation of Dijkstra and Floyd Algorithms in National City Traffic Advisory Procedures,

https://ijcsmc.com/docs/papers/February2014/V3I2201442.pdf

[8] Transitive closure according to Roy-Floyd-Warshall, https://www.isa-

afp.org/browser_info/devel/AFP/Roy_Floyd_Warshall/document.pdf

[9] Application of Graph Theory in Social Media,

https://www.researchgate.net/publication/328954103_Application_of_Graph_Theory_in_Social_Med

ia

[10] Grafuri i matrice de inciden ă,

http://www.automation.ucv.ro/Romana/cursuri/beAB12/2%20Grafuri%20si%20matrice%20

de%20incidenta.pdf

Topan Oana-Maria

Liceul de Informatică „Tiberiu Popoviciu”


Cluj-Napoca, România

Email: [email protected]

Horvath Krisztina-Aliz





Prof. Giurgea Mihaela

Liceul de Informatică Tiberiu Popoviciu

Informatică



Prof. Racolța Andreea


Informatică



https://www.isa-afp.org/browser_info/devel/AFP/Roy_Floyd_Warshall/document.pdf

https://www.isa-afp.org/browser_info/devel/AFP/Roy_Floyd_Warshall/document.pdf

https://www.researchgate.net/publication/328954103_Application_of_Graph_Theory_in_Social_Media

https://www.researchgate.net/publication/328954103_Application_of_Graph_Theory_in_Social_Media





ANEXĂ

RESURSE MEDIA



API utilizat pentru studiul mișcării, realizat în NodeJS


Prezentare PowerPoint

Prezentare Video

https://drive.google.com/open?id=1TLqS9rpBKAKbaweeAjAttfJZLbvpCCds

https://drive.google.com/open?id=1Ha9HDsyXXEs2dWI2yleoAlYD74W2w0lL







Garbage Collector



Prezentare Video

https://drive.google.com/open?id=1aeTUPA6sExlM66WxgpsCovUwGiCUOF3N

https://drive.google.com/open?id=1JQGfYOiL9xAN_48cCwciDhXXcYiyl-Gy







Dynamic Computing 20. De la Formula 1 la Formula-Micro



Prezentare Video

https://drive.google.com/open?id=1pmEU-bbP429KbOqBlwVarDXit78DHO7Z

https://drive.google.com/open?id=1lFKF-EuOKP1GYo_op_PQH2U4CUK5FqX2







SmartH



Prezentare Video

https://drive.google.com/open?id=1rHnAlLCFG20qoHWniAbmaX0V3XGdpWWr

https://drive.google.com/open?id=1Bxk-zFKl53dxECxTTrXInGX4csH1ijxw





Lista autorilor:

Monica AVRAM

Liceul Teoretic “Onisifor Ghibu” Sibiu Informatică Sibiu, România E-mail: [email protected]

Denis BENKE

Colegiul “Nicolae Titulescu” Braşov Matematică-informatică informatică intensiv Braşov, România

Raluca BOCOTAN

Colegiul “Nicolae Titulescu” Braşov Matematică-informatică informatică intensiv Braşov, România

Costică CÎRJEAN

Colegiul “Nicolae Titulescu” Braşov Informatică Braşov, România E-mail: [email protected]

Andrei Constantin DÎRJAN Liceul Teoretic “Onisifor Ghibu” Sibiu Matematică-Informatică Sibiu, România E-mail: [email protected]

Răzvan Gheorghe FILEA Colegiul Național “Samuel von Brukenthal” Științe ale Naturii Sibiu, România E-mail: [email protected]

Delilah FLOREA Colegiul Național “Samuel von Brukenthal” Sibiu, România E-mail: [email protected]

Mihaela GIURGEA

Liceul de Informatică “Tiberiu Popoviciu” Informatică Cluj-Napoca, România Email: [email protected]

Krisztina-Aliz HORVATH

Liceul de Informatică “Tiberiu Popoviciu” Matematică-Informatică Cluj-Napoca, România Email: [email protected]

Christian MELCHIOR

Colegiul Național “Doamna Stanca” Informatică Făgăraș, România E-mail: [email protected]









Andreea RACOLȚA

Liceul de Informatică “Tiberiu Popoviciu” Informatică Cluj-Napoca, România Email: [email protected]

Cristina-Elena STEAVU Colegiul Național “Doamna Stanca” Informatică/Matematică Făgăraș, România E-mail: [email protected]

Nicolae STEAVU Colegiul Național “Doamna Stanca” Informatică Făgăraș, România E-mail: [email protected]

Nicolae-Constantin STEAVU

Colegiul Național “Doamna Stanca” Matematică-Informatică Făgăraș, România E-mail: [email protected]

Oana-Maria TOPAN

Liceul de Informatică “Tiberiu Popoviciu” Matematică-Informatică Cluj-Napoca, România Email: [email protected]






Lista profesorilor coordonatori: Avram Monica Liceul Teoretic “Onisifor Ghibu”, Sibiu


Cîrjean Costică Colegiul “Nicolae Titulescu”, Braşov E-mail: [email protected]

Florea Delilah Colegiul Național „Samuel von Brukenthal”, Sibiu E-mail: [email protected]

Giurgea Mihaela Liceul de Informatică “Tiberiu Popoviciu”, Cluj-Napoca E-mail: [email protected]

Racolța Andreea Liceul de Informatică “Tiberiu Popoviciu”, Cluj-Napoca E-mail: [email protected]

Steavu Cristina-Elena Colegiul Național ,,Doamna Stanca”, Făgăraș E-mail: [email protected]

Steavu Nicolae Colegiul Național ,,Doamna Stanca”, Făgăraș E-mail: [email protected]







Sponsori (în ordine alfabetică):

programare, comunicare,

Documents