Alegere tema
Are foarte mare legatura cu preocuparile fiecaruia, pentru ca articolul trebuie sa fie o constructie solida, documentata si toate afirmatiile trebuie demonstrate si exemplificate prin ceea ce experienta fiecaruia permite.
Daca am elaborat programe de sortare sau am lucrat cu programe de sortare, ma gandesc sa scriu un articol despre acestea.
|
|
Stabilire cuvinte cheie
Trebuie alese 5,6 cuvinte chee care sa defineasca ceea ce vreti sa faceti.
Cuvintele cheie vor fi:
sortare
performanta
analiza
testare
algoritmi.
|
|
Elaborare abstract
Este necesar sa aveti in minte 7-10 propozitii din care sa rezulte clar pasii pe care ii parcurgeti in dezvoltarea articolului.
Este o constructie logica.
Nimeni nu a coborat din tren la Brasov daca nu s-a urcat in el intr-o gara.
Se descriu algoritmi de sortare.
Se prezinta proceduri care implementeaza acesti algoritmi.,br>
Se constituie un set de date de test.
Se efectueaza masuratori.
Se calculeaza durate si se estimeaza performante.
Se ierarhizeaza procedurile in raport cu stabilitatea.
|
|
Stabilire titlu
titlul trebuie sa fie cat mai scurt sa nun contina cuvinte inutile.
Trebuie sa precizeze ce faceti si despre ce vorbiti.
ANALIZA COMPARATA A ALGORITMILOR DE SORTARE.
|
|
Elaborare articol
Se construieste mai intai un schelet al articolului pornind de la abstract.
ANALIZA COMPARATA A ALGORITMILOR DE SORTARE
(abstract)
Se descriu algoritmi de sortare.
Se prezinta proceduri care implementeaza acesti algoritmi.,br>
Se constituie un set de date de test.
Se efectueaza masuratori.
Se calculeaza durate si se estimeaza performante.
Se ierarhizeaza procedurile in raport cu stabilitatea.
1. Algoritmi de sortare
...........algoritmul 1.........
...........algoritmul 2.........
.................
...........algoritmul i.........
........................
...........algoritmul n.........
Se va face o diagrama.
Se vor descrie pasii.
Se ia un exemplu si se arata cum se face sortarea pentru a vedea diferentele.
Se dau elemente de performanta pentru a face diferenta dintre algoritmi.
Se spune cand e bine si cand nu e bine sa se foloseasca un algoritm.
2. Proceduri de sortare
Procedurile implemenetaza toti algoritmii de sortare.
Ele sunt realizate respectand cerintele:
- toate sunt scrise in limbajul C++
- toate procedurile executa atat sortare crescatoare cat si sortare descrescatoare, avand acelasi mecanism de selectie a tipoului de sortare implementat
- au ca parametri de intrare nr componente, sirul de sortat, iar ca rezultat sirul sortat
- returneaza numarul de interschimburi.
textul procedurii de sortare care implementeaza algoritmul i este:
int procedura_i (int numar, int sir_initial[], int sir_sortat[])
{
.........................
...........textul sursa..
.........................
return(numar_interschimburi);
}
se scriu toate procedurile si se face o analiza a lor referitoare la ce executa secventele si cum s-a asigurat ca prin program nu se altereaxza performanta algoritmului
Complexitatea procedurilor este data in tabelul 1.
...............se face un tabel cu coloane si n linii.
- coloana 1 contine nume algoritm
- coloana 2 contine numar linii text sursa
- coloana 3 contine complexitatea ciclomatica
- coloana 4 contine complexitatea Halstead.
se fac comentarii legate de diferentele care apar.
se calculeaza coeficientii de corelatie intre coloanele 2 si 3 , 2 si 4, respectiv 3si 4 si se analizeaza valorile obtinute.
3. Testarea procedurilor de sortare
Pentru a vedea performanta algoritmilor se procedeaza astfel:
- se constituie K seturi de date de test
- se definesc ipoteze de trestare
- folosind aceleasi seturi de date de test se inregistreaza comportamentul procedurilor care implementeaza algoritmii.
Analiza comparata presupune ca toate procedurile sa se execute in aceleasi conditii si datele de intrare sa fie identice.
Seturile de date de test includ ipotezele urmatoare:
- se construiesc siruri de date pentru a vedea dependenta duratei de sortare de lungimea sirurilor
- se construiesc siruri pentru a analiza dependenta duratei de volumul de interschimburi
- se construiesc siruri pentru a vedea comportamentul atat fata de lungime cat si fata de volumul de interschimburi
- se iau in considerare cazurile particulare.
SET_1: contine 50 de siruri de numere fiecare avand lungimea de 20,30,40,50,60,70...termeni, fiecare dintre siruri continand termenii progreisiei aritmetice cu primul termen 10 si ratia 3, toate sirurile fiind deci sortate crescator.
SET_2: contine 50 de siruri de numere fiecare avand lungimea de 20,30,40,50,60,70...termeni, fiecare dintre siruri continand termenii unei progreisii aritmetice descrescatoare cu ultimul termen 10 si ratia 3, toate sirurile fiind deci sortate descrescator.
SET_3: contine 50 de siruri de numere fiecare avand lungimea de 20,30,40,50,60,70...termeni, fiecare dintre siruri continand termenii egali cu ZERO .
SET_4: contine 50 de siruri de numere fiecare avand lungimea 100 dar continutul fiind diferit ( siruri deja sortate, siruri cu valori diferite dar controlat aranjate).
SET_3: contine 50 de siruri de numere fiecare avand lungimea de 20,30,40,50,60,70...termeni, fiecare dintre siruri fiind impartit in doua incat prima jumatate contine elemente sortate crescator iar a doua jumatate, contine aceleasi valori ,elemente fiind sortate descrestator.
1,2,3,4,5,5,4,3,2,1
1,2,3,4,5,6,7,8,9,10,10,9,8,7,6,5,4,3,2,1
..........se siau cat mai multe tipuri de siruri....
Se sconstruiesc tabele in care pe coloana-1 se pune setul, pe coloana 2 se pune lungimea sirului, pe coloana 3 se pune numarul de interschimburi, pe coloana 4 se pune durata.
Se analizeaza dependentele, se fac grafice si chiar se construieste o ecuatie de regresie de forma:
durata = a * numar_elemente + b
sau
volum_interschimburi = a * numar_elemente + b
sau
durata = a * volum_interschimburi + b
Se face o analiza a acestor dependente rezultand diferentele dintre algoritmi.
4. Estimarea performantei procedurilor de sortare
Procedurile de sortare difera unele de altele prin:
- durate de sortare
- efort de pregatire siruri
- efort de realizare text sursa
- complexitate
- fiabilitate
- stabilitatea
- generalitate.
O procedura este mai performanta decat alta daca:
- durata de elaborare este mai redusa
- necesarul de resurse este rezonabil
- durata de sirtare este mai mica.
Se alege procedura cu durata cea mai mica.
Se face analiza stabilitatii duratei medii, adica daca aceasta durata medie nu variaza semnificativ de la un lot la altul de siruri avand proprietati similare.
daca asa stau lucrurile inseamna ca acea procedura este cea mai convenabila.
Toate caracteristicile sunt analizate si se fac masuratori pentru a vedea cat de bine sunt indeplinite cerintele de procedurile scrise.
5. Ierarhizarea algoritmilor de sortare
A ierarhiza elementele unei colectivitati inseamna:
- a lua in considerare o serie de criterii de diferentiere a elementelor colectivitatii
- a efectua masuratori pentru caracteristicile puse in corespondenta cu acele criterii
- a stabili importanta acelor criterii
- a calcula coeficienti de importanta pentru criterii.
In cazul algoritmilor de sortare:
- colectivitatea este formata din n proceduri care implementeaza n algoritmi
- criteriile vizeaza comportamentul procedurilor prin durata medie de sortare, complexitatea textelor sursa si volumul de interschimburi
- variabilele considerare sunt: durata medie de sortare DS, complexitatea Halstead CH, numarul de interschimburi VI
- coeficientii de importanta sunt p1 = 0.7, p2 = 0.2, p3 = 0.1
Indicatorul agregat IA este dat de relatia:
IA = p1 * DS + p2 * CH + p3 * VI
Se construieste tabelul avand col 1= nume procedura, col 2=DS col 3=CH col 4=VI col 5 = IA.
Se sorteaza procedurile descrescator dupa col 5 si rezulta ierarhizarea algoritmilor.
Se face o analiza a ceea ce a rezultat tinand seama ce s-a obtinut la performanta dar si la testare.
6. Concluzii
Se va scrie :
- la ce foloseste acest rezultat
- cum se extinde analiza de la siruri la sortarea fisierelor
- cum se lucreaza cu bazele de date
- o gestiune a starii fisierelor, pentru a nu sorta un fisier deja sortat.
- sortarea de n-tuple .
BIBLIOGRAFIE
30% carti
40% articole preponderente din reviste ISI
20% webgrafie
10% proceedings-uri de la conferinte
|
|
Studierea materialelor bibliografie
Se merge in biblioteca.
Se cauta pe Internet.
In toate cazurile se fac notite ce contin:
- problematica
- detalii
- sursa (autor, titlu, pagina) de unde este folosit un rezultat
- consideratii personale legate de modele, de algoritmi, de limitele solutiilor gasite.
Documentarea trebuie sa fie:
- la obiect
- completa
- cu lucrari fundamentale (pentru sortare tratatul lui KNUTH este esential caci volumul 3 se numeste chiar SORTARE).
|
Trecere la elaborare si testare proceduri
Se cauta pastrarea stilului de programare caci revenirea are rolul de a afecta intregul articol daca se produc schimbari fundamentale in proceduri.
Se culeg datele necesare si se va cauta ca datele sa fie complete si corecte pentru a avea tanelele cu care se va lucra.
O scapare va impune reluarea unor pasi lucru foarte dificil.
|
Construirea de modele si prelucrarea statistica a seriilro de date din tabele.
Se efectueaza prelucrari si se trag concluzii fara a aduce realitatea spre modele, ci a interpreta ceea ce s-a gasit pentru a analiza ceea ce este de fapt in realitate.
Se va vedea sa nu apara contradictii flagrante cu ceea ce este deja verificat in literatura.
|
Elaborarea propriu-zisa a articolului
respectand schita elaborata, folosind notitele de la studierea bibliografiei si tabelele obtinute de la realizarea si testarea procedurilor se elaboreaza articolul, pas de pas.
Se vor cita materialele pe masura ce sunt folosite notitele.
Se vor intercala tabele, diagrame si figuri.
Textul trebuie sa fie foarte clar si sa rezulte din el ca:
- autorul stie despre ce scrie
- autoryul are experienta
- ipotezele avansate de autor sunt verificate de acesta
- nu se plagiaza
- tot ceea ce este preluat este citat riguros
- sunt respectate cerintele din ghidul de elaborare impus de revista unde se trimite spre publicare articolul.
| | | | | | | | | |
