Limbajul de programare C++ - Marius ??2. Descrierea generală ... • elaborarea algoritmilor de...

download Limbajul de programare C++ - Marius ??2. Descrierea generală ... • elaborarea algoritmilor de rezolvare a problemelor ... rezolvarea şicombinarea soluţiilorau un grad de complexitate

of 16

  • date post

    15-Feb-2018
  • Category

    Documents

  • view

    223
  • download

    1

Embed Size (px)

Transcript of Limbajul de programare C++ - Marius ??2. Descrierea generală ... • elaborarea algoritmilor de...

  • Sumar

    1. Competene . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

    2. Descrierea general a metodei . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

    3. Studii de caz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

    4. Aplicaii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

    5. Bibliografie i webografie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

    2

  • 1. CompeteneCompetene generale

    elaborarea algoritmilor de rezolvare a problemelor

    aplicarea algoritmilor fundamentali n prelucrarea datelor

    identificarea conexiunilor dintre informatic i societate

    Competene specifice

    prelucrarea datelor structurate

    recunoaterea situaiilor n care este necesar utilizarea unor

    subprograme

    analiza problemei n scopul identificrii subproblemelor acesteia

    elaborarea unui algoritm de rezolvare a unei probleme din aria

    curricular a specialitii

    alegerea unui algoritm eficient de rezolvare a unei probleme

    elaborarea i implementarea unor algoritmi de rezolvare a unor

    probleme cotidiene

    scrierea metodei de rezolvare a unei probleme n termeni recursivi

    3

  • 4

    Expresia divide et impera provine din limba latin i a constituit unul dintre

    principiile de guvernare ale mpratului roman Iulius Cezar.

    n traducere nseamn dezbin i stpnete, adic principiul conform

    cruia o mas de oameni poate fi mai uor stpnit atunci cnd este

    dezbinat.

    2. Descrierea general a metodei

  • 5

    Utilitatea metodei

    Metoda se folosete n problemele care pot fi descompuse n subprobleme

    similare cu problema iniial (care se rezolv prin aceeai metod) i care

    prelucreaz mulimi de date de dimensiuni mai mici, independente unele

    de altele (care folosesc mulimi de intrare disjuncte).

    Descrierea general a metodei

  • 6

    Principiul metodei

    Metoda const n descompunerea problemei de rezolvat n subprobleme.

    Rezultatul se obine rezolvnd subproblemele i combinnd soluiile

    acestora. Se presupune c fiecare din problemele n care a fost

    descompus problema iniial, se poate descompune n alte subprobleme,

    la fel cum a fost descompus problema iniial. Procedeul se reia pn

    cnd (n urma descopunerilor repetate) se ajunge la probleme care admit

    rezolvare imediat.

    Descrierea general a metodei

  • 7

    Etapele metodei

    Divide mprirea problemei n dou sau mai multe subprobleme.

    Rezolvarea subproblemelor se rezolv fiecare dintre subprobleme,

    direct (dac acestea sunt simple) sau prin reducearea acestora la alte

    subprobleme (adic recursiv).

    Impera combinarea soluiilor subproblemelor pentru obinerea soluiei

    problemei iniiale.

    Descrierea general a metodei

  • 8

    Impelmentarea metodei

    Descrierea general a metodei

    Divide_et_impera (p,q,s)

    dac dimensiunea p corespunde unui caz de baz atunci

    se determin soluia s a problemei

    altfel

    Divide_et_impera(p1,q1,s1)

    Divide_et_impera(p2,q2,s2)

    ...

    Divide_et_impera(pk,qk,sk)

    Combin soluiile s1, s2,...,sk pentru a

    obine soluia s

  • 9

    Concluzii

    Algoritmii divide et impera sunt n general rapizi, deoarece prin

    descompunere, de cele mai multe ori, se obin problem pentru care

    rezolvarea i combinarea soluiilor au un grad de complexitate mai mic

    dect problema iniial.

    Algoritmii divide et impera se implementeaz, de obicei, ntr-un

    subprogram recursiv.

    Nu toate problemele pot fi rezolvate prin utilizarea acestei tehnici.

    Numrul problemelor rezolvabile prin divide et impera este relativ mic,

    tocmai datorit cerinei ca problema s admit o descompunere repetat.

    Descrierea general a metodei

  • 10

    Studii de caz

    cutare binar

    turnurile din Hanoi

    merge sort

    quick sort

    Descrierea general a metodei

  • 11

    Studii de caz

    cutare binar

    Descrierea general a metodei

    https://www.youtube.com/watch?v=kazvOikPQrk

    https://www.youtube.com/watch?v=kazvOikPQrk

  • 12

    Studii de caz

    turnurile din Hanoi

    Descrierea general a metodei

    https://www.youtube.com/watch?v=5_6nsViVM00

    https://www.youtube.com/watch?v=5_6nsViVM00

  • 13

    Studii de caz

    merge sort

    Descrierea general a metodei

    https://www.youtube.com/watch?v=XaqR3G_NVoo

    https://www.youtube.com/watch?v=XaqR3G_NVoo

  • 14

    Studii de caz

    quick sort

    Descrierea general a metodei

    https://www.youtube.com/watch?v=ywWBy6J5gz8

    https://www.youtube.com/watch?v=ywWBy6J5gz8https://www.youtube.com/watch?v=ywWBy6J5gz8

  • 15

    Fi de lucru

    Aplicaii metoda de programare Divide et impera

    3. Aplicaii

  • 16

    1. Miloescu M., Informatic. Manual pentru clasa a XI, Editura Didactic

    i Pedagogic, Bucureti, 2006

    2. oca L., Inormatic. Manual pentru clasa a X, Editura Niculescu,

    Bucureti, 2001

    3. Popescu C., Culegere de probleme de informatic, Editura Donaris-

    Info, Sibiu, 2002

    4. Ministerul Educaiei, Cercetrii i Tineretului, Centrul Naional pentru

    Curriculum i Evaluare n nvmntul Preuniversitar, Proba scris la

    informatic. Examenul de bacalaureat Variante (1-100) , Bucureti

    2008

    5. http://ro.wikipedia.org/wiki/Iulius_Cezar

    6. http://ro.wikipedia.org/wiki/Divide_et_impera

    7. http://ro.wikipedia.org/wiki/Divide_et_impera_(informatic%C4%83)

    4. Bibliografie

    http://ro.wikipedia.org/wiki/Iulius_Cezarhttp://ro.wikipedia.org/wiki/Divide_et_imperahttp://ro.wikipedia.org/wiki/Divide_et_impera_(informatic%C4%83)