Introducere în algoritmică și Java

în algoritmică și în Java Licență 1 Curs MASS, SEMS și ESD în Java și în algoritmică [email protected] www.i3s.unice.fr/ verel Echipa ScoBi - Université Nice Sophia Antipolis 1 februarie 2013

Buna! Lector din septembrie 2006. Cercetare: Proiectarea și studiul algoritmilor de optimizare inspirate din biologie. algoritmi: a se vedea optimizarea suplimentară: găsiți cele mai bune soluții posibile la o problemă (transport, orar, proiectare, ajustarea protezei, proiectarea teoriei cognitive.) bio-inspirat: extrageți principiile active dintr-o teorie a evoluției sistemului biologic, furajând furnici, păsări în mișcare . proiectare: creați și testați algoritmi noi studiați: înțelegeți și preziceți de ce funcționează sau, mai bine, de ce eșuează! La laboratorul I3S (universitate/cnrs) din Sophia-Antipolis, echipa DOLPHIN, INRIA Lille Nord Europe.

Buna! Predare: tu, prj. scient. info, L2; intro Syst. complexe, info L3; rețele, L3; sist. artă. complexe, informații M1; modelare, M2 psy. Contact: pentru toate problemele legate de predare (corecții, absențe, cerere de explicații, informații suplimentare, îndrumare.) [email protected] www.i3s.unice.fr/ verel bureau 426, Petit Valrose tel. 04.94.92.07.69.83

Buna! Motivația pentru această predare: pentru a preda elementele de bază ale rezolvării anumitor probleme prin metoda algoritmică pentru a preda informatica ca limbaj capabil să exprime prelucrarea informațiilor pentru a preda elevilor a căror predare de bază nu este doar informatică

Informații despre scopul, obiectivele de predare etc. cf: www.i3s.unice.fr/ verel

Cursul unui curs 1 Prezentarea unei realizări în procesare: După trimiterea uneia dintre realizările dvs. prin e-mail (publicare pe pagina web) Prezentare orală scurtă în CM (1 diapozitiv) x elevi 2 Inima cursului 3 Sinteza orală și scrisă: La sfârșitul cursului sinteza orală a punctelor importante Redactarea acestei sinteze în forumul didactic de referință 3 studenți

Obiectivele sesiunii 1 1 Cunoașterea algoritmilor istorici 2 Cunoașterea unei definiții a algoritmului 3 Cunoașterea mediului de procesare 4 Editarea și comentarea codului java cu procesarea 5 Știința afișării unui text 6 Știerea afișării formelor grafice simple Întrebarea principală a zilei: Ce este- ce algoritm?

Planul 1 Exemple de algoritmi din istorie și viața de zi cu zi 2 3 4 5

Algoritmul lui Euclid (elemente, VII, -325/-265 î.Hr.) Problemă Găsiți o unitate comună de măsură pentru două lungimi de segmente, adică găsiți gcd doi numere întregi. Algoritm GCD (a, b: întreg): început întreg dacă b = 0 atunci GCD = a altfel c restul diviziunii lui a cu b GCD = GCD (b, c) sfârșit dacă sfârșit

Executarea algoritmului GCD (72, 34) Pentru a = 72 și b = 34 1. GCD (72, 34) 4. b 0 7. c = 4 8. GCD (34, 4) 4. b 0 7. c = 2 8. GCD (4, 2) 4. b 0 7. c = 0 8. GCD (2, 0) 4. b = 0 5. GCD = 2

Seta Erastotenului (3 î.Hr.) Problemă Determinați toate numerele prime mai mici decât un număr dat. Algoritmul Erastothene (N: întreg): începe tabelul de numere întregi Scrieți în tabel întregii între 2 și N. atâta timp cât pătratul celui mai mic număr nelimitat și nemarcat este mai mic decât N marca cel mai mic număr din matricea necrucisată și nemarcată din matrice, toți multiplii acestui număr se termină ca numere prime mai mici decât N: numere marcate sau nu sunt tăiate

Sita Erastotenului (III e î.Hr.) Observații Posibilitatea de a îmbunătăți algoritmul: nu scrieți multipli de 2 și multipli de 5. Avantaj: scrieți mai repede la început, deoarece mai puțin spațiu folosit pe o foaie Dezavantaj: mai lung pentru a tăia: aveți să gândești mai mult pentru a tăia numerele potrivite! Versiune modernă a algoritmului: Sieve d Atkin (1999) Referință: A.O.L. Atkin, D.J. Bernstein, sitele Prime folosind forme pătratice binare, Math. Comp. 73 (1999), 1023-1030.

Multiplicarea egipteană Problema Calculați produsul a 2 numere întregi Algoritm Multiplicarea egipteană (a, b: număr întreg): începe întreg Scrieți tabelul puterilor de 2 mai mic sau egal cu numărul a Scrieți tabelul dublurilor numărului b atâta timp cât numărul a nu este zero nu Verificați cea mai mare putere de 2 a Scădeți această putere de 2 din numărul a sfârșit atâta timp cât adăugarea dublurilor numărului b corespunde puterilor lui 2 verificate anterior produse de a de b: suma calculată mai sus Sfârșit

Truc magic! Alegeți un număr între 1 și 15.

Truc magic! 9 14 10 15 8 13 12 11

Truc magic! 15 3 11 13 9 5 7 1

Truc magic! 6 14 13 12 4 5 15 7

Truc magic! 2 3 6 7 10 11 14 15

Truc magic! Care este culoarea numărului dvs.

Căutați un cuvânt într-un dicționar Algoritm de căutare în mod iterativ (țintă: cuvânt): lista de cuvinte începe Citiți primul cuvânt din dicționar atâta timp cât cuvântul citit nu este cuvântul țintă faceți Citiți sfârșitul cuvântului următor ca listă de cuvinte: definiție a cuvântul lu sfârșit Găsim cuvântul corect, dar algoritmul nu este foarte eficient. în medie, N/2 cuvinte citite cu N dimensiunea dicționarului Este necesar să se utilizeze ordinea lexicografică a dicționarului și metoda dihotomică (împarte și cucerește)

Căutați un cuvânt într-un dicționar prin dihotomie Algoritm de căutare (țintă: cuvânt): lista de cuvinte începe primul primul cuvânt al dicționarului ultimul cuvânt al dicționarului Citiți cuvântul median între primul și ultimul, atâta timp cât cuvântul citit nu este cuvântul țintă faceți dacă cuvântul țintă este înainte de cuvântul citit apoi ultimul cuvânt citit altfel primul cuvânt citit sfârșit dacă Citiți cuvântul median între primul și ultimul sfârșit ca o listă de cuvinte: definiția cuvântului citit sfârșit în medie, jurnal 2 (N) cuvinte citite cu N de mărimea dicționarului

Indicele masei corporale Problemă Dați un grad de corpulență bazat pe indicele masei corporale Algoritmul masei corporale (t: număr real, M: număr real): începe i M/T 2 dacă i