Grannröðun og Djúpleit
34 Questions
0 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to Lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

Hvað er meginmarkmið grannröðunar í stefndu, órásuðu neti?

  • Að finna stystu leið milli tveggja hnúta.
  • Að raða hnútum þannig að allir leggir vísi frá vinstri til hægri. (correct)
  • Að búa til hringrás í netinu.
  • Að flokka hnúta eftir tengslastyrk þeirra.

Hvernig er hægt að nota dýptarleit til að greina hvort stefnt net inniheldur rás?

  • Með því að fylgjast með hvort heimsóttur hnútur er heimsóttur aftur áður en hann er merktur sem FINISHED. (correct)
  • Með því að leita að hnútum með enga innleggi.
  • Með því að finna lengstu leið í netinu.
  • Með því að telja fjölda hnúta í netinu.

Hver er munurinn á uppsprettu (source) og svelg/ós (sink) í stefndu neti?

  • Uppspretta hefur enga útleggi en svelgur hefur enga innleggi.
  • Uppspretta hefur enga innleggi en svelgur hefur enga útleggi. (correct)
  • Uppspretta og svelgur eru sama hugtakið.
  • Uppspretta er alltaf fyrsti hnúturinn og svelgur er alltaf síðasti hnúturinn.

Hvert er hlutverk trjáleggja (tree edges) í djúpleit?

<p>Að mynda djúpleitartréð. (A)</p> Signup and view all the answers

Hvaða fullyrðing er rétt um snúið net (reversed graph) af órásuðu neti?

<p>Það er alltaf órásað. (B)</p> Signup and view all the answers

Í hvaða samhengi er grannröðun sérstaklega mikilvæg?

<p>Í verkefnastjórnun, skipulagningu verkefna og háðum verkþáttum. (C)</p> Signup and view all the answers

Hvað gerist við uppsprettur og svelgi þegar stefnt net er snúið (reversað)?

<p>Uppsprettur verða svelgir og svelgir verða uppsprettur. (C)</p> Signup and view all the answers

Hver er tímaflækjan við að reikna snúið net (reversed graph) með grenndarlista?

<p>$O(V + E)$ (C)</p> Signup and view all the answers

Í samhengi við kvika bestun, hvað táknar hæðisnet (dependency graph)?

<p>Myndræna framsetningu á undirverkefnum og háðingu þeirra. (D)</p> Signup and view all the answers

Hvaða fullyrðing er rétt um útreikning endurkvæmra undirverkefna með minnistöflunálgun?

<p>Hann samsvarar djúpleit á hæðisnetinu. (B)</p> Signup and view all the answers

Hvernig tryggir minnistöflunálgun (memoization) skilvirka útreikninga?

<p>Hún forðast endurtekin útreikning á undirverkefnum. (A)</p> Signup and view all the answers

Hvað felur í sér að vinna með stefnt órásað net í öfugri grannröðun?

<p>Að vinna með hvern hnút í lok ítrunar hans í dýptarleit. (B)</p> Signup and view all the answers

Ef kvikt bestunarreiknirrit er sagt vera jafngild eftirröðunaryfirferð á hæðisneti, hvað þýðir það?

<p>Að reikniritið endurspeglar uppbyggingu endurkvæmninnar í gegnum röð útreikninga. (A)</p> Signup and view all the answers

Hvernig er regluleg uppbygging hæðisneta nýtt í kvikri bestun?

<p>Til að forrita röðunina beint inn í reikniritið, oft með hreiðruðum lykkjum. (B)</p> Signup and view all the answers

Í hvaða tilvikum er djúpleit sérstaklega gagnleg við lausn á kvikbestunarvandamálum?

<p>Þegar hæðisnetið er óreglulegt. (D)</p> Signup and view all the answers

Hvernig má nota grannröðun til að finna lengsta veg í stefndu órásuðu neti?

<p>Með því að upphafsstilla lengdir allra vega sem óendanlega og fara í gegnum hnúta í grannraðaðri röð. (C)</p> Signup and view all the answers

Hvað gerir leit að besta vegi í stefndu órásuðu neti (DAG) að hentugri nálgun fyrir kvik bestunarverkefni?

<p>Hún gerir vandamálið auðveldara að skilja og leysa þar sem hægt er að endurskrifa mörg verkefni sem leit að besta vegi. (B)</p> Signup and view all the answers

Hvaða fullyrðing lýsir best hvernig finna má bestu lausn í trébyggðu kvik bestunarverkefni?

<p>Með því að leysa hvert undirtré óháð öðrum og sameina niðurstöðurnar. (C)</p> Signup and view all the answers

Hvað einkennir sterklega samhangandi net?

<p>Að hægt sé að komast á milli hvaða tveggja hnúta sem er í báðar áttir. (C)</p> Signup and view all the answers

Hvaða eiginleiki á við um sterklega samhangandi þáttagraf (strongly connected component graph)?

<p>Það er alltaf stefnt órásað net (DAG). (C)</p> Signup and view all the answers

Hvert er markmið Kosaraju-Sharir reikniritsins?

<p>Að finna sterklega samhangandi þætti í stefndu neti. (B)</p> Signup and view all the answers

Hvaða skref eru tekin í Kosaraju-Sharir reikniritinu?

<p>Keyra dýptarleit á snúna netinu og síðan dýptarleit á upprunalega netinu í öfugri röð við fullklárun. (B)</p> Signup and view all the answers

Hvers vegna er Kosaraju-Sharir reikniritið talið skilvirkt?

<p>Vegna þess að það keyrir á línulegum tíma, O(V + E). (A)</p> Signup and view all the answers

Hver er helsta ástæðan fyrir því að trébyggð verkefni henta illa fyrir lausnir sem byggjast á DAG (stefnt acyclískt net) nálgun?

<p>Trébyggð verkefni fela í sér samhliða ákvarðanir sem DAG getur illa höndlað. (D)</p> Signup and view all the answers

Hvaða fullyrðing lýsir best muninum á því hvernig línuleg og trébyggð kvik bestunarverkefni eru leyst?

<p>Línuleg verkefni eru leyst með leit að besta vegi í DAG, en trébyggð verkefni með samsetningu lausna úr undirtrjám. (D)</p> Signup and view all the answers

Í Kosaraju-Sharir reikniritinu, hvaða eiginleika nýtum við okkur þegar við keyrum dýptarleit í annað sinn á upprunalega netinu (G)?

<p>Sú staðreynd að hvert kall á DFS heimsækir nákvæmlega einn sterklega samhangandi þátt. (A)</p> Signup and view all the answers

Hvað þýðir það að sterklega samhangandi þáttur C sé svelgsþáttur (sink component) í neti?

<p>Að allir hnútar í C geti náð til allra annarra hnúta í C. (A)</p> Signup and view all the answers

Ef gefið er stefnt net, hvaða fullyrðing er alltaf sönn varðandi sterklega samhangandi þætti þess?

<p>Hver hnútur tilheyrir nákvæmlega einum sterklega samhangandi þætti. (D)</p> Signup and view all the answers

Hvert er hlutverk bakleggja (back edges) í djúpleit?

<p>Að vísa upp tréð og gefa til kynna mögulega hringrás. (A)</p> Signup and view all the answers

Hvaða fullyrðing er rétt um samband grannröðunar og öfugrar eftirröðunar í dýptarleit í stefndu órásuðu neti?

<p>Grannröðun er sú sama og öfug eftirröðun. (D)</p> Signup and view all the answers

Hver er munurinn á sterklega tengdum og venjulega tengdum netum?

<p>Sterklega tengd net leyfa ferð á milli allra hnúta í báðar áttir, en venjulega tengd tryggja aðeins tengingu í einhverja átt. (A)</p> Signup and view all the answers

Hvað er átt við þegar sagt er að lausn á kviku bestunarvandamáli sé „samfelld undirtré í djúpleitarskóginum“?

<p>Lausnin byggist á undirverkefnum sem tengjast í röð, líkt og trjágrein. (C)</p> Signup and view all the answers

Kosaraju-Sharir reikniritið byggir á eftirfarandi:

<p>Að nýta eiginleika svelga í snúnu neti. (B)</p> Signup and view all the answers

Hvað er átt við með því að nota „grenndarlista“ til að reikna snúið net (reversed graph)?

<p>Að reikna snúið net með því að nota tengda lista til að tákna tengingar milli hnúta. (B)</p> Signup and view all the answers

Flashcards

Djúpleit (Depth-First Search)

Records start and stop times for each node, providing info about the graph's structure.

Edge classification in DFS

Tree edges form the DFS tree, back edges point up, forward edges point down, and cross edges point between trees.

Grannröðun (Topological Sorting)

Arranges nodes in a directed acyclic graph so that edges point from left to right.

Uppspretta (Source)

A node with no incoming edges in a directed graph.

Signup and view all the flashcards

Svelgur/ós (Sink)

A node with no outgoing edges in a directed graph.

Signup and view all the flashcards

Topological Sorting via Postorder

Sorts nodes by descending order of finish time in DFS.

Signup and view all the flashcards

Node Marking in DFS

Mark nodes as ACTIVE when visited and FINISHED after neighbors are processed.

Signup and view all the flashcards

Simplified Post-processing for DAGs

Mark nodes as visited or unvisited to determine graph structure.

Signup and view all the flashcards

Preprocessing in Acyclic Graphs

Create the reversed net, where sources become sinks and vice versa.

Signup and view all the flashcards

Memoization and Depth-First Search

Use DFS on the dependency graph to calculate values.

Signup and view all the flashcards

Dynamic Programming and Postordering

Each subproblem is calculated after all subproblems it depends on.

Signup and view all the flashcards

Dynamic Programming with Depth-First Search

Build dynamic programming algorithms for problems with irregular height.

Signup and view all the flashcards

Strongly Connected Nodes

If u can reach v, and v can reach u.

Signup and view all the flashcards

Kosaraju-Sharir Algorithm

Find a node in source components with DFS.

Signup and view all the flashcards

Krossleggur

Leggur í djúpleit sem vísar á milli tveggja leitartrjáa.

Signup and view all the flashcards

Bakleggur

Leggur í djúpleit sem vísar upp tréð.

Signup and view all the flashcards

Framleggur

Leggur í djúpleit sem vísar niður tréð.

Signup and view all the flashcards

Notkun grannröðunar

Raðar verkefnum í röð þannig að hægt sé að ljúka stærra verki.

Signup and view all the flashcards

Rásargreining með dýptarleit

Aðferð til að finna hvort stefnt net inniheldur rás.

Signup and view all the flashcards

Snúið net

Snúa við öllum leggjum í neti.

Signup and view all the flashcards

Besti vegur í DAG

Þegar leit að besta vegi í DAG er endurskrifað sem kvik bestunarverkefni

Signup and view all the flashcards

Setning um samhangandi þætti

Fyrir sérvert djúpleit á stefndu neti, inniheldur hver samhangandi þáttur nákvæmlega einn hnút sem hefur ekki foreldri.

Signup and view all the flashcards

Skilgreining á sterklega samahangandi neti

Sterk samhengi jafngildisvensla á hnútum stefnds nets þar sem öll hnútapör eru sterklega tengd.

Signup and view all the flashcards

Snúa við sterklega samahangandi þáttagraf

Snúa við sterklega samahangandi þáttagraf er það sama og taka sterklega samahangandi þáttagraf af snúið graf.

Signup and view all the flashcards

Study Notes

Djúpleit og Tímasetningar

  • Djúpleit includes recording start and stop times for each node
  • These times provide information about the structure of the graph

Flokkar Leggja í Djúpleit

  • Djúpleit classifies edges into four categories
  • Trjáleggir (Tree edges) are in green and form the depth-first search tree
  • Bakleggir (Back edges) in red point up the tree
  • Framleggir (Forward edges) in blue point down the tree
  • Krossleggir (Cross edges) in gray point between two search trees

Yfirlit

  • Grannröðun(Topological Sorting)
  • Minnistöflunálgun og Kvik Bestun (Memoization and Dynamic Programming)
  • Sterkt Samhengi í Netum (Strong Connectivity in Graphs)
  • Kosaraju-Sharir Reikniritið (The Kosaraju-Sharir Algorithm)
  • Niðurstöður Miðmisseriskönnunar(Midterm Survey Results)

Grannröðun(Topological Sorting)

  • Arranges nodes in a directed acyclic graph
  • All edges point from left to right
  • It is important in Verkefnastjórnun (Project management), Skipulagningu Verkefna (Planning Projects) and Háðum Verkþáttum (Dependent tasks)

Sérstakir Hnútar í Stefndum Netum(Special Nodes in Directed Graphs)

  • Uppspretta (Source) is a node with no incoming edges
  • Svelgur/ós (Sink)is a node with no outgoing edges

Grannröðun Með Eftirröðun (Topological Sorting with Postorder Traversal)

  • Grannröðun can be based on depth-first search postorder traversal
  • Nodes are sorted in descending order of finish time

Reiknirit Fyrir Grannröðun (Algorithm for Topological Sorting)

  • Implementation includes a function called topological_sort(G)
  • The function takes a graph G as input and returns a topologically sorted list of vertices
  • It performs a depth-first search on the graph.
  • Nodes are sorted by finish time in descending order.

Athugum Verk Sem

Ef ljúka þarf verkþætti i áður en verkþáttur j getur hafist þá ritum við v₁→vⱼ

  • Grannröðun gives which order to do work items in

Óbein Grannröðun (Implicit Topological Sorting

  • It is usually unnessecary to keep/store the topological sort
  • Implementation involves performing operations during search
  • This saves memory and simplifies the program
  • To work in reverse topological order, perform operations at the end of the depth-first search iteration
  • Grannröðun is the same as reverse post order

Eftirvinnsla Dýptarleitar (Post-processing a Depth-First Search)

  • Depth-first search can determine whether a graph contains a cycle
  • When a node is visited in depth-first search, it is marked as ACTIVE
  • After all of node's neighbors are looked after, it is marked as FINISHED
  • A cycle has been found if an edge points to an ACTIVE note

Einfölduð Eftirvinnsla Fyrir Órásað Net (Simplified post processing for acyclic DAGs)

  • Algorithm can be simplified if it is known that the graph is free of cycles.
  • It suffices just to mark nodes visited or unvisited
  • You do not need to keep track of the ACITVE/FINISHED node

Framvinnsla á Órásuðu Neti (Preprocessing in Acyclic Graphs)

  • There are two ways to process nodes in forward order
  • Store a topological ordering of nodes in an to an array, loop through this array
  • To implement depth-first search on the reversed net, you have to create the reversed net first rev(G)
  • The revered net of an acyclic net is also acyclic
  • Sources become sinks and vice versa
  • Topological sorting on rev(G) is the reverse topological sorting on G
  • Compute reversed nets using the adjacency list in O(V+E) time

Minnistöflunálgun og Kvik Bestun (Top Down Dynamic Programming and Bottom Up Dynamic Programming)

  • Grannröðunorreiknir is a the model for a lot of kvikrar bestunar
  • Hæðisnet Endurkvæmra Undirverkefna means
    • Hnútur is for hvert Endurkvæmt Undirverkefni
    • Leggur fr´a einu undirverefni and annars ef útreikningur fyrra krefst útrekninga á ´þv´i seinna
  • Hæðisnetið verður a´ð vera órásað stefnt net
    • Annars myndi endurvæma reikniritið aldrei stöðvast
  • Útreignigur Endurkvæmra means use Djúpleit on Hæðisnetinu
  • Hnútur er merktur þegar búið er að reikna gildi undirverkefnisins
  • Previsit and Postvisit eru staðgenglar fyrir útreikning gildanna
  • Minnistöflunálgun Tryggir A´ð Hvert Undirverkefni er Aðeins Reiknað einu sinni

Kvik Bestun og Eftirröðun (Dynamic Programming and Postordering)

  • Útreikningur endurkvæmni corresponds to reikna öll for the Hæðisnetinu á öfugrigrannröð
  • Hvert undirverkefni is reiknað after búið er að reikna öll undirverkefni se það er háð
  • Sérhvert a kvik beustnerreiknir is after að reikna hæðisnet á endurspeglar

Regluleg Uppbygging Hæðisneta

  • Flest Hæðisnet i Kvikri Bestun hafa reglulega Uppbyggingu
  • Dæmi: breitingafjarlægð Reglulegt net with skálínum
  • Djúpleit (Depth-first search) is used byggja (to build) Kvik BestunarReiknirit, for vandamál með óreglulegri hæðisnet(irregular height)

Samanburður á Aðferðum (Comparison of Techniques)

  • There are two different type of aðferðir - Endirvæmni - For - Lykkja (loop)
  • Báðar frakvæma sömu djúpleit (both run the same Depth First Search Algorithm )
  • Best aðferðir is eimungis to choose á þæginda
  • Báðar skila sömu Niðurstöðu

Flókin Hæðisvensl (Complex Height Relations)

  • Hæðisvenslin relate to multi öðrum verkefni sem hafa sem áhrif hvað a annað
  • Besta lausn krefst þess að meta og sameina niðurstöður ur sjálfstæðum
  • Lausn doesn't have to eins og BESTAvEGI dagur og dagur

Sterkt Samhengi(Strong Connection)

  • Hnútur u getur náð til hnútar v í stefndu neti G if it can from between a vegur fra u til v
  • Mengið reach(u) táknar alla hnúta sem u getur náð til
  • Hnútar U and V are sterklega tengdir if u getur náð til v og v getur náð til u
  • Stefnt net(directed) er sterklega samanhangandi and því aðeins að öll séu sterklega tengd

Samhengi

Setning fyrir sérhverja djúpleit a stefndu neti G inniheldur hver sterklega samhangandi áttur C nákvæmlega einn hnút sem hefur foreldri í C.

Kosaraju-Sharir reiknirit

  • Finda hnút í svelgsþætti is erfitt
  • Hins vegrar is auðvolt að finda hnút i is uppsprettuþættum með djúpleti

Algengustu Ábendingar (Common Suggestions)

  • The most common issues are related to, lausnir á prófum og heimadæmum (solutions to exams and homework), dæmatímar og nýting þeirra (exercise time and their utilization) and Tímalengd og tímasetning prófa (length and timing of exams)

Studying That Suits You

Use AI to generate personalized quizzes and flashcards to suit your learning preferences.

Quiz Team

Related Documents

Description

Djúpleit flokkar brúnir í fjóra flokka og skráir upphafs- og endatíma fyrir hvern hnút. Grannröðun raðar hnútum í beina línurit þannig að allar brúnir vísi frá vinstri til hægri. Þetta er mikilvægt í verkefnastjórnun og skipulagningu verkefna.

More Like This

Mastering Topological Sort
10 questions

Mastering Topological Sort

ChivalrousSmokyQuartz avatar
ChivalrousSmokyQuartz
Mastering Topological Ordering
6 questions

Mastering Topological Ordering

ChivalrousSmokyQuartz avatar
ChivalrousSmokyQuartz
Topological Sorting Quiz
5 questions

Topological Sorting Quiz

KeenSnail avatar
KeenSnail
Grafi: Visite e Ordinamento Topologico
45 questions

Grafi: Visite e Ordinamento Topologico

SteadyBoltzmann avatar
SteadyBoltzmann
Use Quizgecko on...
Browser
Open
Browser
Browser