Namų darbas

Ką pateikti

algo su net ir dense, praeinantis go test ./..., plius ataskaita.

1. Tavo tinklo forma

Pateik prie n = 1 000 / 10 000 / 100 000: viršūnės, briaunos, vidutinis ir medianinis laipsnis, komponenčių skaičius, didžiausios komponentės dydis ir jos skersmuo.

Tada keisk -trails ir -length ir rask tašką, kuriame didžiausia komponentė apima 90 % bibliotekos. Ką reikia keisti — pėdsakų skaičių ar jų ilgį? Paaiškink per tai, ką kiekviena vėliavėlė daro grafui.

2. Kuri paieška kuriam klausimui

Šeši klausimai. Kiekvienam: BFS, DFS ar bet kuri — ir vienas sakinys kodėl.

• ar knyga B apskritai pasiekiama iš knygos A?
• per kiek skolinimų atsiskyrusios A ir B?
• duok visas knygas, pasiekiamas iš A
• kiek atskirų salų turi biblioteka?
• rask bet kurią knygą, nutolusią nuo A per 10 ar daugiau perėjimų
• ar tinklas yra vientisas?

Bent vienas atsakymas turi būti „bet kuri", ir tam pasakyk, kurią rašytum iš tikrųjų ir kodėl.

3. Reprezentacija, nuspręsta skaičiais

Septintas žingsnis palygino sąrašą ir matricą tavo tinkle. Dabar rask persivertimą.

Laikyk V = 1 000 ir didink briaunų skaičių, kol matrica laimės atmintimi. Koks tai vidutinis laipsnis? Išreikšk jį V dalimi.

Tada pasakyk, kuris iš dviejų transit grafų būtų arti tos ribos, o kuris — nė iš tolo.

4. Modelis seka klausimą

Aštunto žingsnio mintis buvo, kad transit sąmoningai palieka laiką už stotelių grafo ribų.

Suprojektuok grafą kiekvienam iš šių trijų klausimų apie tavo biblioteką. Viršūnės, briaunos ir ką briauna reiškia — be kodo.

• kurios knygos dažniausiai skolinamos kartu?
• kurią knygą rekomenduoti po šitos?
• kurių dviejų knygų nė vienas skaitytojas negalėjo pasiimti per tą patį apsilankymą?

Bent vienas iš jų negali būti nesvorinis grafas. Pasakyk, kuris ir kodėl — tai visa penkioliktos pamokos prielaida.

5. Vienintelis dalykas, kurio BFS negali

BFS atsako „per kiek mažiausiai perėjimų", nes kiekvienas perėjimas kainuoja tiek pat.

Užrašyk savais žodžiais, kas tiksliai lūžta, jei tavo tinklo briaunos turėtų skirtingas kainas — tarkim, dienas tarp skolinimų. Ne „būtų lėčiau": pasakyk, kuo remiasi BFS sluoksnių argumentas ir kuri jo dalis nustoja galioti.

Tada nuspėk, kas turėtų pakeisti eilę. Ją pastatei tryliktoje pamokoje.