Teoria numerelor *

1. Algoritmul lui Euclid

Alegeți varianta/variantele corectă/corecte de calcul al celui mai mare divizor comun:

a. gcd x, y = x, y = 0

gcd y, x − y x

y , y > 0

b. gcd x, y = x, y = 0

gcd y, x mod y , y > 0

2. Ciurul lui Eratostene

Scrieți numerele de la 1 la 50. Exemplificați apoi algoritmul de identificare a numerelor

compuse, subliniind diferit fiecare număr neprim identificat cu ajutorul unui număr

prim, în funcție de acesta din urmă.

3. Suma și numărul divizorilor

Se consideră numărul n reprezentat ca în formula de mai jos:

n = p1d1 + ⋯ + pk

dk

Demonstrați că numărul de divizori ai acestui număr este:

σn = (1 + di)

k

i=1

4. Elementul majoritar

Problema a fost evaluată la temă. Se va considera media primelor trei întrebări.

i. Vlad Apetroaei, Andrei Burlică, Dan Cuciureanu

ii. Călin Buzilă, Claudiu Chiuaru, Vlad Pătrașcu

iii. Bogdan Ailincăi, Valentin Pașcău

iv. Bogdan Dutcă

v. Valentin Popa

vi. Daniel Burghelea

vii. Victor Filimon

Grafuri ***

1. Parcurgerea în lățime a unui graf

Să presupunem că vrem să afișăm toate vârfurile dintr-un graf care se află la distanța

minimă k de un vârf fixat. În acest sens, parcurgem în lățime graful. Propuneți un model

de a reține datele, astfel încât spațiul suplimentar să fie O(1). Spre exemplu, reținerea

distanței k pentru fiecare vârf adaugă un spațiu suplimentar O(n).

2. Parcurgerea în adâncime a unui graf

Să presupunem că avem un arbore cu număr infinit de noduri și o rădăcină cunoscută.

Să se decidă care din următoarele parcurgeri garantează vizitarea unui nod oarecare,

dar fixat, în timp finit. Argumentați alegerea/alegerile.

a. parcurgerea în adâncime

b. parcurgerea în lățime

3. Sortarea topologică a unui graf

Grafurile asupra cărora se poate realiza sortarea topologică au o proprietate aparte.

a) definiți această proprietate,

b) construiți un exemplu și un contraexemplu,

c) pe contraexemplu, motivați alegerea proprietății.

4. Componentele tare conexe ale unui graf

Descrieți un algoritm pentru un graf cu minim 7 noduri și 15 muchii.

i. Florentina Barcan, Andreea Mazilu, Gabriela Neagu

ii. Nicolaie Airini

iii. Bety Hapău, Magdalena Roca

iv. Iulian Gherasim

v. Lavinia Gherasim, Lidia Lupașcu, Veronica Miron

vi. Alexandra Andrei, Alina Cocalia, Veronica Rotar

vii. Ciprian Boiciuc, Claudiu Darie

viii. Dorin Petroiu, Ramona Zaharia

ix. Vlad Băeșu, Ștefan Dospinescu, Daniel Stoian

Programare dinamică *****

1. Subsecvența de sumă maximă

Secvența dată la intrare este reținută într-un tablou S de n numere întregi. Definim prin

C[i] costul subsecvenței de sumă maximă care începe pe poziția i a tabloului. Descrieți

relația de recurență.

2. Parantezare optimă de matrici

Considerăm n matrice notate M1, ..., Mn de dimensiuni (Li, Ci). Se dorește aflarea

numărului minim de înmulțiri scalare ale produsului matriceal Mi,j = Mi × …× Mj , unde

i și j sunt date de intrare. Descrieți relația de recurență pentru calculul acestui număr,

verificând și proprietățile necesare înmulțirii matricelor. Verificarea se va face a priori,

în complexitate timp O(j-i). Dacă Mi, j nu se poate calcula, se va considera ∞.

3. Ciclu hamiltonian de cost minim

Recurenţa descrisă în explicația soluției este dată de formula

Mi,j = min Mi⊗2j ,v + Cv,j v ∈ i}

Explicați această formulă, folosind reprezentarea unui lanț într-un graf la alegere.

4. Interogări de minim pe intervale

Descrieți pe un exemplu netrivial legătura dintre minimul pe un interval și cel mai

apropiat strămoș comun. Aveți în vedere etapa de preprocesare prin parcurgerea Euler

și etapa de întrebare, cu minim 2 înterogări.

i. Bogdan Cernat, Andreea Hurjui, Adrian Schipor

ii. Cristian Gafița, Emil Grigore, Cosmin Tarsichi

iii. Radu Cârjan

iv. Raluca Chiroșcă, Daniel Irimia

v. Irinel Bogdan, Mihai Pricop

vi. Ciprian Roșculescu