Merken

# Traversing Mazes the pythonic way and other Algorithmic Adventures

#### Automatisierte Medienanalyse

## Diese automatischen Videoanalysen setzt das TIB|AV-Portal ein:

**Szenenerkennung**—

**Shot Boundary Detection**segmentiert das Video anhand von Bildmerkmalen. Ein daraus erzeugtes visuelles Inhaltsverzeichnis gibt einen schnellen Überblick über den Inhalt des Videos und bietet einen zielgenauen Zugriff.

**Texterkennung**–

**Intelligent Character Recognition**erfasst, indexiert und macht geschriebene Sprache (zum Beispiel Text auf Folien) durchsuchbar.

**Spracherkennung**–

**Speech to Text**notiert die gesprochene Sprache im Video in Form eines Transkripts, das durchsuchbar ist.

**Bilderkennung**–

**Visual Concept Detection**indexiert das Bewegtbild mit fachspezifischen und fächerübergreifenden visuellen Konzepten (zum Beispiel Landschaft, Fassadendetail, technische Zeichnung, Computeranimation oder Vorlesung).

**Verschlagwortung**–

**Named Entity Recognition**beschreibt die einzelnen Videosegmente mit semantisch verknüpften Sachbegriffen. Synonyme oder Unterbegriffe von eingegebenen Suchbegriffen können dadurch automatisch mitgesucht werden, was die Treffermenge erweitert.

Erkannte Entitäten

Sprachtranskript

00:00

the

00:16

the guy thanks a lot for coming and very excited to be here today In this talk I would like to talk about something I like it a lot in computer science which is algorithms and in particular graph algorithms that are graphs are great data structures and almost useful for every problem you solve every in your everyday code OK so the

00:52

title says Thomas amazes amazes me in the graph so and the stuff we're going to talk about Trabelsi souls related problems and of course May society every data structure for the role playing game here today I'm quite sure and many of your heart have played dungeons and dragons and stuff like that so the stock seems to be a and we want to be an is each occurs guide for getting off from the engines again the 2nd part of the title is algorithmic adventures of rhythms are the most important endurable part of computer science and so they may be studied and analyzed in way which is language independent question independent but in this talk we're going to talk about Python right so we're trying to analyze the algorithms the algorithms and the algorithmic part in slices from a very very funny standpoint this is my my goal for this talk and by the way this is not supposed to be an algorithmic class right so this is what I will provide some very introductory staff I'll try to briefly something that on what should that you are already aware of no guidance I'm sorry in this yeah actually you're right or is it the case that the have that this is the 1st time I used the IPython offered to make presentations of quite a bit of maths again so the let me briefly recap some best export algorithm analysis we need a technique to compare the efficiency of them without worrying about the implementation of the machines and the the language so we have 2 different techniques we have the rumble computation we have the asymptotic analysis the worst-case complexity of those in other words than no Winston ever so weird I we're interested in the worst case here this is even in worst case and we have the wrong mobile computation from a little computation simply tells us that uh each simple operations such as Blast and minus if calls takes exactly 1 time step a loop some functions are not considered simple operations and each memory access takes exactly 1 time step that we have we may have as many memory as we want and the rumble of takes no notice on whether an item catch or in this so always on this so this in all the details are right behind the of the all the stuff but we don't think about it OK of 1st we have different but annotations to country to analyze the complexity of algorithm we have the worst-case complexity so that the goal also known as the Big O notation that have annotations of the average case complexity and the best case complexity of the legal notation originally was the big Omicron actually and tells us that the upper bound of the asymptotic upper bound for a function and the complexity of the of of an algorithm for instance we say that the time of our algorithm belongs to the old to the n squared this means that the come from for for a for a large enough value to and which is the size of the input of our algorithm the the time complexity asymptotic time complexity we will be bounded by the and square function again this is just a very brief recap for all this stuff just to introduce the as 2nd topic so what I will talk about later and just for information the infinite its dominance relations this table chose you in the different that relations among the different some of the well-known different asymptotic amputation from the constant time with to the the factorial which is the behavior heaviest yeah this 1 look at so all talk about the graphs graphs the 1 of the unifying themes in computer science very digressive rate data structure powerful mental model and graph can represents all parameters and almost all kinds of structuring systems you might think about transportation networks social networks to nowadays social network analysis is of great research field and very active research field uh dependency networks for since you might think to be it profits and think the dependencies of a piece of code or the the the the depends solve a the package that should be installed on your machine breast cancer comes in different flavors with different expressivity of course and in that natural the graph terminologies we have it we that rotorcraft G as a couple of the the the is the set of vertices he is the set of edges versus with the match uh um within a match between 2 of them are at a distance to the edge is there an incident in this and this purposes we may have a subgraphs so g prime which is the prime p p prime is there is a graph where the prime is a subset of the prime is all that the edges incident in notes of the prime we have the notion of task so we have a path is a sub graph where edges that connect the nodes in sequence and finally we have a cycle which is like a path that with the difference that less century links the 1st node in the path due to defer to the last node to the first one graph sources

07:16

said comes in different flavors we may have directed or undirected graphs in the the figure you may see that the edges house and and and the notion of directions is the are unweighted or weighted graphs work sorry were the there is not a weights on the on the edges that there may be simple or non simple graphs the non-simple right here means that there's some edges make that may require some special handling in your in our algorithm for instance and this case self loops or groups in general uh we'll see another example of this in a few minutes and are sometimes thermal will be group ages that may be it may be incident multiple times in the signal in that case there will be a that will be graph not graph action OK so we may have cycling versus psychic graphs and understands for and cited references a tree uh trees are connected STT and undirected graphs we may have sold the well known in the so called Don which stands for directed acyclic graphs and we'd actually be made the applied topological sorting and stuff like that this is that these are called concepts for it a from very basic in introductory algorithmic blasts can and finally we may have a label advertis labeled graphs where there is a label on nodes so versus on the graph a graphs may be its forests or maybe bands in which refers to the number of edges in the graph uh and last but not least on graphs may be explicit or implicit this is what I was referring before when I told you that graphs are a great big structure and a powerful man mental model because sometimes when you have to deal with with the problem you have to solve such kind of problem you may think to the prom being uh as a graph problem so you may represent your data your problem as a graph and you may apply graph algorithms to your to problem so here we can here we go to the graph representation so finally we we start to see some code and actions of 1 of the most common way to represent

09:56

graphs use the education Salazar and something like that that what is additionally so 1 of the most intuitive ways to implement graphs and for each node we can access a list what as we will see in few minutes all its neighbors so this is the idea and this is the graph we're going to have to use the right sample in the next slides again so we have nodes labeled from 8 to age and for simplicity we assume that we number all the notes from a to age assigning a number that goes from 0 to 7 so and minus 1 in Python we want to implement

10:41

objections set which shows up In this case we is the shape of the notes from a to and H and then we use create the structure and which is an a list of additionally the uh over all sets are kind of come before just just the mention before Python 274 or Python 3 of you would use the set constructed here but and now we Europe you may

11:14

use the the this expression moon to to to create sets of literals right so in the in the brackets you may uh associate on set of literals OK the name and it has been used in graph theory and all of the which where B is a vertex stands for the the neighborhood of node be on that be right so in this case we might have the right blend of end of which is 3 in this case f is the node OK which is the degree of the node and then we may also test for the neighborhood membership of B the end the with this simple instructions and it returns to can so this is for neighborhood membership and we would like to discuss on the different complexity depending on the different implementation of the structure we going to use a cat so in the 1st example we use a set and this other example we try to modified a little bit and we use that as an additional so this so we replace the sets of OK so actually the code doesn't reflect this source for that I did didn't realize it before I'm sorry for baby In braces should be substituted of course with square brackets that for that In this case again we have the same expressivity OK so we may apply again land of an event which has 3 again so the degree of denote the number of nodes incident in the graph that we may test for membership for neighborhood membership so be in and the i returns a true but this time neighborhood memberships takes 10 . and all of uh these which is the vertex in case of set in the average case the neighborhood membership is constant and time OK so this is just the 1st difference of the the 2 of these 2 very simple implementation this can be problematic in case of dense graphs or be graphs OK we can leverage point for instance we could use these implementations all sort of uh additions lists we may sort of the the additions lists and we may rely on the sorting um and normal data of all sort and of the sort of data to you but applied binary search in order to tests for the membership of character in that case we may reduce the the the complexity to blogs of the the size of the neighborhood but In the general case if if the graph is speak maybe I'm an implementation based on sets on the average case with the vector the guy is just the 1st I think this is just an means for a more complex problems yet another tray we can substitute the lists or the sets with a dictionary of Kassel this time we implement the additional with dictionaries in this is a sort of sparse weighted graph representation in this in this example we also and that's in the graph representation the weight OK so we increase the expressivity of our graph week uh and also are taken with this kind of representation we are also able to represent the weights of of the of the edges ok so in case of our time case of weighted graphs this over Urry intuitive as a way to represent graph again we are able to test for membership to calculate the degree of the node in with exactly the same syntax as before but now we are also able to get the weight for a particular hedge for instance if we're interested in getting the weight forward that the the edges connecting nodes a to the weight is to get and this is this is that how we handle OK for a more flexible approach actually Python in this and documentation suggests this I did way to implement it up and implementation pattern for graphs differ in some please take a look at the end of the and at the the length of on the slide but basically the idea is to represent a graph in a very dynamic and flexible way by means of Python dictionary again so we you and that the nodes I mean of course considering the ideation sees uh structure can so did you embed the nodes as keys of a dictionary and every L every value as a in the dictionary is a list of all the keys in order to get the the the corresponding edge in the in the structure of text and this implementation is quite similar to what happens to the well known network x a library again at text is the reference python library for graph algorithms everything I'm going to do talk to 2 to talk about here today is already implemented in protects effect so my my goal here is not to to show how all this stuff is the made in natural text must just to and the reason for it just you know get more and more details on how you could handle all this stuff and Python and what are the difference of every possible decisions you make uh made on Grant OK so again the following the implementation Potter we made implemented and the jury of additions to sect character this is a very simple implementation we drop the weights information and we rely on the fact that we're dealing with a node's label it with a single letters so we create a set from from the strain so and very simple again so this implementation is very very similar to the former as to the first one but drops the the weights information and again it relies on a

18:24

dictionary where that's for and efficiencies X and uh with the structure we are allowed to just 4 membership for neighborhood membership which is still a constant time and we may calculate the degree of a new the other well known structure to represent graphs use the adhesion to metrics and so on In addition Semantics will list all the neighbors for each node of character so uh we want to store of value indicating the presence or the absence of the edge in the graph connecting 2 nodes which is true or false instance 0 1 1 atmosphere respectively OK and we may try to implement in addition metrics with nested lists the we may argue that this is not a and actually matrix this is a list of lists of guide this just implementation details of Python this just to adjust just to do that sort of proof of concept of and so a with this

19:35

structure we are able to implement we're able to test for membership as usual were able to to to calculate the degree of the nodes and of course you may substitute this homemade implementation of the metrics using for instance new pi race cancer which is of course even more efficient and if we will have time I will uh I would like to to talk about the the sci-fi graph implementation and already in the library of uh all sci-fi token of the

20:16

properties of the mediation semantics of semantics is a great structure of character and and haven't I thought to to to talk about the the differences of additional synsets additions to lists in general and issues Mavericks because in of algorithmic class algorithm class in the university uh and sometimes there should be some misconceptions on the use of the 2 different structure that so on the 1 hand we have the additions lists where we are interested in storing the only the information related to the existing uh edges between the vertices in addition semantics represents all the information carried so sometimes there should be a misconception that you want to use 1 structure uh when you have very small graph for the other 1 1 year of uh the big with a bigger or graphic but we were talking about this in a few slides uh additions metrics have uh the has great as some of the very interesting properties of the day the diagonal matrix the idea of the metrics is the cost you a binary of 0 character so as long as we don't allow self loops so we're dealing with pseudo graphs the dead diagonal you In case of undirected graphs there must exist a method of so if we're and we're dealing with undirected graphs we may leverage the sun and very efficient method of presentation for triangular matrix extending the additional semanticists allow for edge weights is very trivial instead of storing truth values 0 1 we may story that the values of the weights let's make an example but in this case we're going to represent that the the weighted In addition semantics and we store we use this syntax in the 1st line to to sort the infinite white OK so in this case if you want to test for the membership during the week we should check if the the values corresponding to a and B is less than infinity which is in this case history uh but it is not true in case of C eat so there's no there's no edge connecting c and b or know worse than did that the way the world and the weights of the edges in uh is infinite can and finally we made calculate the degree by summing on the role of the metrics in this case we really we apply minus 1 at the end because we want to remove the diagonal elements can so in case of a node the degrees which is the number of the uh the number of elements in row except for the diagonal can and finally some some consideration about the efficient representation this is a great book can was there from Germany is in red it's Goldfield efficient representation and she says in his book that means there is a classical misconceptions in general after taking an algorithm class we may end up considering that there are 2 methods representing graph in the computer science additions mattresses conditions lists it is faster to work with addition semanticist but there'd there they use more spaces on the other hand you may choose additions to list in case of the other resources In this case resources is the most important thing is to you there many interesting way to represent the graph actually In addition to mattresses and this lists are just too of the ways to represent graphs not the only 2 ways to account for instance you might say have additional ages that edge with or instance metrics OK which is something a bit different from the additions to the but there are some people socialize representation for different graph types persons trees are specialized versions of graphs and there are represented in a very different way for from general-purpose graph interval graphs another very interesting example the rule of thumb that uh he suggests this decide on the asymptotic overall complexity and decide which is the structure that best uh works for your particular problem for your particular data OK so this is just a variant of saying a consideration of those OK so here we hard to the traversal of mazes again so we have a nice this kind of a partial reversal of the typical role playing Dungeons can you may think to the rooms the the edge of graph and you may think that sought to as and the nodes of graph you may think to the doors connecting the different rooms as the edges the graph can the traversal tree is the finest is defined by you track so you by the the try q applied while you're traversing the makes the french or the frontier ordered to wrestle Q consists 2 the neighbor heating rate problems can the remaining documents rooms here in the in the maze all the notes that have no is that not been discovered yet OK so this is not a very simple and a trivial example of at the classical problem represented by means of a graph structure OK in this case the graph is implicit we have no explicit graph this representation of all Forms lights all the using the dictionary with additions to sets for reference and OK 1 of the most famous for but also algorithm for amazes is the 1 by treating and ends Lucas in 1891 misery crystal Mathématique broke explains this argument in this way of on trying to to to pull this 1 completely from vessel the passages of a library and twice from any initial point simply follow the rules posted by criminal making H entry to or exit from an intersection these rules may be summarized as follows when possible passing intersection you have read the visitors or avoid taking passages have already travesti uh is this not approve approach which also applies in everyday life OK so the basic idea here is to you a to get the information and every time we we Trabelsi and edge so connection between 2 nodes we we store entry or exit information in this in this case we would like to find not go over the same steps and

28:10

the same ways of more than once a cat cover the basic idea is backtracking so the idea is some looking in any direction once and then backtracked whenever you came to dead end or an intersection that you are ready to walk through to avoid cycles this is the basic idea and we will see and details of this 1 OK so I'm sorry for the the formatting this this may be due to the the font size the

28:46

server that we may have this kind of functions in Python which is the arbitrary walk can we assume as said before we assume our graph represented as a dictionary agency set and we have an input and an S node which is the starting point OK so we select a random starting point or the point the point where we are and how we have to structures that P and acute uh structures these the predecessors to use the set of the nodes to

29:17

be we selected randomly uh we simply we add to the to the to the set to the starting point and we traits while Q while the the the the set Q has elements inside we pick 1 element in the queue completely arbitrary OK I by using that you don't popped method and for every node switches in the which is incident to the you know to what has not been visited yet we and there's no to the you and then we sort the predecessor so in this case we walked through the to do graph 1 step the step by step I actually this algorithm will travesti a single connected component OK so we'll try we will weird you we will find the connected components of a graph starting from the uh from at a given node p is that processes 3 if

30:25

you would like to be uh if you would like to get all the connected components in graph we might I rate only ever every node in the graph and we call the walk functions and we use this is simply um updates the structure of a scene which is a set of this is nodes again OK well thank you could have the time complexity of this algorithm is status of the plus of these so this the which is the complexity of almost every traversal of a but just a little another detail about this is the important point here is that when we select the notes we want to do this if we use real on

31:21

the the the pop method here on the set which takes randomly an element in the sector of character so this is why this is called an arbitrary uh and that's if

31:37

we want to go deep so we want to apply the on the so called adapt 1st trouble so we might use another trick so instead of picking randomly the the the elements in the In this structure we might use a structure that task of the size of a predefined particle to get the elements in this case in the case of the death 1st proposal is the last in 1st out particles cat but this is a recursive implementation but in Python where we may we generally we made every always translated custom implementation to a unintelligible 1 In this case we rely on the list structure mechanics so every time we at the end up to a node which is which is new a week extend the the the frames to the the set of incidence nodes to do today to be you want of God and you know a mock implementation we use a set of characters so we would risk having the same nodes scheduled from more than 1 this OK so this is why the depth-first traversal yes more efficient in general case in the DFS we use the Allies uh therefore use so every node is scheduled for only once if you want to generalize this role so we might write this function which is the progress and um did the did the type of turbo so we're going to my depends on the

33:21

structure we're going to use for the french OK in general this is a set which is very similar to the arbitrary walk already showed a few slides go if we use the the list of so the Python lists these will end up to be depth-first 1st reversal and using the yield that allows for it lazy iterations so on uh it will may create an generated Python which is very very useful and this is more efficient for dance and the graphs can and that's it for yes thank you and that's it for it and the mazes OK but what about the infinite mazes and unweighted shortest path a so far the over EGA behaviors 4th deft 1st for fossils have hasn't the a problem actually the problem of the dead dead 1st reversal of the 1st search is that you may run for ages and never get back a character so in case of very very deep graph the graph the depth 1st reversal is not a good is not a good choice that in fact in case of visiting of trolling the graph of the web the adapt 1st proposal is not that the solution can in general the debris uh the the distillate Bayesian here's another kind of 2 rules so which is the breadth 1st search at that I'm going to talk about now and what if we would like to follow the shortest path from s and amazing so in this case the shoppers sparse means the minimum number of the intersection of time the 1st attempt is the iterative deepening their 1st search and I'm not going into the details of this ordering the basic idea is that this algorithm applies a depth-first search for causal many times with different our death limits OK kind but this algorithm led to another well known algorithm which is the breath 1st search breath 1st search is versatility the ITER DFS so the idea of a version of the depth-first-search but if it uses a different our structure OK in disguise the daft breath 1st search for users are um a structure which is a Q and follow that follows the FIFO set first-come-first-served uh which is the 1st the 1st of words and then we may be implemented in Python using the DTD structure which is in the standard library in this for a very simple and very retrieval to to implement the did you actually corresponds to a double links to in Python as you may know that ends up in this case we rely on the top-left function to be get the element we want to start visiting start traversing and the proper leftists constant time because of the implementation of the uh the you structure the complexity of overall breath 1st search is always again that's out of the each of the dimension of edges plus the dimension of purchases and it can be demonstrated that the birth the BFS calculus always apparent

37:00

and in case of weighted graphs and other well known problem in computer science and and algorithms in general is the shortest path but this time the short to spot means the path with the minimum within the minimum cost start as these comics as I would like to have a pillow talk sort uh we will talk about the dice for algorithm not the moment for as in this it's a comic OK they and the dice threshold back on directed acyclic graphs relies on the relaxed function which the basic idea of the relaxed function is to propagate the knowledge about the shortest path 1 uh step at a time we looked for an improvement to the publicly known distance to be by trying to take a shortcut through are you which is the they vertex we want to test OK if the structure if the it is a short so if we pass through the you know to cost less than the already computed shortest path we will follow that direction and we tested this 1 step at a time a kind of OK and so on yep did I saw

38:20

algorithm applied and exploits the EQ structure which is a priority queue that allows us to get the notes every time we add a note to this structure we Our guaranteed to respect the EP fight uh relations so that and we add the a the notes you in order this is a priority queue so this is a Q order to and we get the elements a with the pop which which returns the the element with the least priority OK of the difference in the relationship between the dice frog remember breath 1st search algorithm is that by allows assigning distances of the then 1 for each step meanwhile the breadth-first-search search basically just expands the search by 1 step of that which happens to have the effect of finding the moles the number of steps it takes to get to and even a to any given node from any source

39:30

it can the last example here is the shortest path from all of for all pairs because I story is the sure this past also known as shortest paths Single source so you have and nodes a target that you want to optimized and you start looking for the shortest paths considering that single node the another very interesting problem is the shortest path for all pairs OK so we're interested in getting the shot response for every possible proposal on our graph this is usually solved by a well known algorithm which is the Floyd-Warshall algorithm that relies on a technique an optimization technique which is called dynamic programming also known as don't repeat yourself In mathematics Adamic programming is a method for solving complex problems by breaking them down into simpler subproblems it is applicable to problems 6 beating the properties of overlapping subproblems and optimal substructure so the basic idea is memoization memoization means cash value already solved problems is so instead of recomputing every time the same subproblems we might create

40:47

function for memorization implies that in a very elegant way I like this a lot we may create a mammal decorated which relies on which exploits the prox function from fund tools which it wraps is a sort of show that for a partial and another function is a function of Fund tools to sort function which is partial and in this case we create

41:13

them this decorator to uh in this broker recreated cash which is the dictionary that stores the values of all the problems OK this is it in action the Floyd-Warshall algorithm is a problem that may relying on the dynamic programming technique because the the basic idea is that uh let us consider the DUP k be the length of the shortest path that exists from node u to node b a if you're only allowed to use that you're only allowed to use the 1st k nodes in your graph right you can decompose the problem as it follows that the distance from node u to node v using the k a notice in your path corresponds to the minimum to the distance from you to the without taking that node or the cost uh from that good of the path that goes from a you to can and k to the maybe this is uh this is uh more clear in this in this slide we might considering whether or not to include not k in the in the the shortest path of character so we calculate the cost of the paths that pass through the k nodes that starting from you and ending to to be if this as I'm not a convenient costs so so if the cost of not taking that node is less than taking that node we simply consider we simply disregarded node but otherwise we include that node the node k initial paths we may I create the so we may implement the Floyd-Warshall algorithm in Python considering 1st since the additional semantics and the distance all the solution in this case we a deep copy the graphs and updates that implies that the the the weights of the of the distances but we may also exploit the memoization a wraps for afford formatting is very often awful

43:24

and we made a recursively apply the but this the D function which is the function that calculates the distance from notes using the memorization so if we end up to our distance from a node u v and K already calculated the memorization functions of Y to calculated again and

43:47

returns the value thanks to the decorator presented before so that sets some references to buy the logarithms this a very introductory route for this kind of stuff uh of the algorithm this manually as not actually related to fight and but it's very a good reference manual and that's it thank you very much for a definitive thank you very much for their

44:22

only any questions there

44:26

is the lifetimes lunch break Saul please feel free to ask questions OK so I think it was a very compact introduction thank you very much like what the

00:00

Algorithmus

Graph

Code

Ungerichteter Graph

Datenstruktur

Informatik

Code

Computeranimation

00:49

Program Slicing

Ungerichteter Graph

Computeranimation

Richtung

Netzwerktopologie

Zahlensystem

Algorithmus

Gruppe <Mathematik>

Elektronischer Programmführer

Metropolitan area network

Kartesische Koordinaten

Datennetz

Bitrate

Menge

Rechter Winkel

Festspeicher

Ext-Funktor

Tabelle <Informatik>

Instantiierung

Subtraktion

Folge <Mathematik>

Mathematisierung

Klasse <Mathematik>

Green-Funktion

Asymptote

Virtuelle Maschine

Loop

Informationsmodellierung

Knotenmenge

Spieltheorie

Abstand

Datenstruktur

Informatik

Analysis

Gerichtete Menge

Transinformation

Stochastische Abhängigkeit

Datenmodell

Binder <Informatik>

Teilgraph

Unendlichkeit

Wort <Informatik>

Personal Area Network

PROM

Bit

Formale Sprache

Selbstrepräsentation

Gruppenkeim

Computerunterstütztes Verfahren

Inzidenzalgebra

Komplex <Algebra>

Zahlensystem

Analysis

Metropolitan area network

Arithmetischer Ausdruck

Figurierte Zahl

Bildauflösung

Nichtlinearer Operator

Lineares Funktional

Parametersystem

Asymptotik

Systemaufruf

Quellcode

Ein-Ausgabe

Endlicher Graph

Teilmenge

Datenfeld

Information

Gewicht <Mathematik>

Stab

Gruppenoperation

Implementierung

Zahlenbereich

Kombinatorische Gruppentheorie

Transportproblem

ROM <Informatik>

Code

Abenteuerspiel

Komplexitätstheorie

Task

Graph

Systemprogrammierung

Multiplikation

Zeitkomplexität

Booten

Leistung <Physik>

Wald <Graphentheorie>

Matching <Graphentheorie>

Graph

Relativitätstheorie

Einfach zusammenhängender Raum

Physikalisches System

Quadratzahl

Dreiecksfreier Graph

Mereologie

Binäre Relation

Einfügungsdämpfung

09:56

Shape <Informatik>

Graph

Zahlenbereich

Mailing-Liste

Ungerichteter Graph

Menge

Computeranimation

Rechenschieber

Objekt <Kategorie>

Graph

Metropolitan area network

Knotenmenge

Menge

Stichprobenumfang

Datenstruktur

11:14

Nachbarschaft <Mathematik>

Matrizenrechnung

Adhäsion

Bit

Punkt

Web log

Selbstrepräsentation

Element <Mathematik>

Ungerichteter Graph

Binärcode

Komplex <Algebra>

Inzidenzalgebra

Computeranimation

Formale Semantik

Metropolitan area network

Arithmetischer Ausdruck

Poisson-Klammer

Algorithmus

Momentenproblem

Mustersprache

Elektronischer Programmführer

Softwaretest

Addition

Datennetz

Schwach besetzte Matrix

Ereignishorizont

Entscheidungstheorie

Dichte <Physik>

Arithmetisches Mittel

Rechenschieber

Menge

Beweistheorie

Information

Ordnung <Mathematik>

Graphentheorie

Computerunterstützte Übersetzung

Schlüsselverwaltung

Instantiierung

Subtraktion

Gewicht <Mathematik>

Matrizenrechnung

Implementierung

Zahlenbereich

Code

Graph

Knotenmenge

Programmbibliothek

Zeitkomplexität

Speicher <Informatik>

Datenstruktur

Soundverarbeitung

Assoziativgesetz

Linienelement

Graph

Zwei

Mailing-Liste

Vektorraum

Menge

Quick-Sort

Data Dictionary

Linienmethode

Minimalgrad

Quadratzahl

Normalvektor

19:35

Punkt

Selbstrepräsentation

Versionsverwaltung

Oval

Element <Mathematik>

Ungerichteter Graph

Extrempunkt

Binärcode

Raum-Zeit

Marketinginformationssystem

Computeranimation

Formale Semantik

Netzwerktopologie

Metropolitan area network

Algorithmus

Polygonzug

Reverse Engineering

Typentheorie

Gerade

Softwaretest

Tabusuche

Addition

Parametersystem

Kategorie <Mathematik>

Ausnahmebehandlung

Bitrate

Dreiecksmatrix

Endlicher Graph

Arithmetisches Mittel

Rechenschieber

Menge

Konditionszahl

Information

Diagonale <Geometrie>

Instantiierung

Subtraktion

Gewicht <Mathematik>

Thumbnail

Klasse <Mathematik>

Matrizenrechnung

Zahlenbereich

Implementierung

Kombinatorische Gruppentheorie

Graph

Loop

Bildschirmmaske

Knotenmenge

Datensatz

Netzbetriebssystem

Datentyp

Programmbibliothek

Datenstruktur

Grundraum

Informatik

Gammafunktion

Einfach zusammenhängender Raum

Videospiel

Graph

Linienelement

Schlussregel

Mailing-Liste

Unendlichkeit

Diagonalform

System F

Minimalgrad

Betafunktion

28:09

Lineares Funktional

Punkt

Graph

Oval

Ein-Ausgabe

Computeranimation

Richtung

Metropolitan area network

Knotenmenge

Font

Menge

Dreiecksfreier Graph

Server

Dateiformat

Persönliche Identifikationsnummer

Datenstruktur

Computerunterstützte Übersetzung

29:17

Einfach zusammenhängender Raum

Pell-Gleichung

Lineares Funktional

Punkt

Graph

Einfach zusammenhängender Raum

Element <Mathematik>

Extrempunkt

Inzidenzalgebra

Komplex <Algebra>

Computeranimation

Demoszene <Programmierung>

Metropolitan area network

Knotenmenge

Algorithmus

Menge

Polygonzug

Warteschlange

Datenstruktur

31:20

Lineares Funktional

Strukturmechanik

Rahmenproblem

Landau-Theorie

Einfach zusammenhängender Raum

Tiefensuche

Implementierung

Mailing-Liste

Turbo-Code

Element <Mathematik>

Inzidenzalgebra

Computeranimation

Task

Metropolitan area network

Knotenmenge

Diskrete-Elemente-Methode

Menge

Arithmetische Folge

Grundsätze ordnungsmäßiger Datenverarbeitung

Datentyp

Datenerfassung

Rekursive Funktion

Partikelsystem

Datenstruktur

Computerunterstützte Übersetzung

33:19

Information Retrieval

Kalkül

Momentenproblem

Extrempunkt

Versionsverwaltung

Iteration

Ungerichteter Graph

Element <Mathematik>

Extrempunkt

Komplex <Algebra>

Marketinginformationssystem

Computeranimation

Richtung

Metropolitan area network

Algorithmus

Vier

Reverse Engineering

Auswahlaxiom

Bayes-Netz

Lineares Funktional

Schnelltaste

Dicke

Schwellwertverfahren

Physikalischer Effekt

Güte der Anpassung

Rechenschieber

Konstante

Diskrete-Elemente-Methode

Menge

Gewicht <Mathematik>

Hausdorff-Dimension

DTD

Tiefensuche

Implementierung

Zahlenbereich

Unendlichkeit

Graph

Benutzerbeteiligung

Programmbibliothek

Inverser Limes

Abstand

Datenstruktur

Informatik

Graph

Division

Schlussregel

Binder <Informatik>

EINKAUF <Programm>

Quick-Sort

Unendlichkeit

Wort <Informatik>

Eigentliche Abbildung

Personal Area Network

38:16

Soundverarbeitung

Subtraktion

Graph

Mathematik

Kategorie <Mathematik>

Minimierung

Landau-Theorie

Relativitätstheorie

Einfache Genauigkeit

Zahlenbereich

Element <Mathematik>

Quellcode

Computeranimation

Warteschlange

Suchverfahren

Metropolitan area network

Knotenmenge

Algorithmus

Prioritätswarteschlange

Endogene Variable

Abstand

Optimierung

Datenstruktur

Ordnung <Mathematik>

40:46

Gewicht <Mathematik>

Extrempunkt

Gruppenoperation

Matrizenrechnung

Ungerichteter Graph

Extrempunkt

Computeranimation

Formale Semantik

Metropolitan area network

Knotenmenge

Algorithmus

Abstand

Speicher <Informatik>

Optimierung

Serviceorientierte Architektur

Lineares Funktional

Multifunktion

Dicke

Graph

Diskretes System

Quick-Sort

Rechenschieber

Arithmetisch-logische Einheit

Rechter Winkel

Dateiformat

Personal Area Network

43:23

Metropolitan area network

Lineares Funktional

Knotenmenge

Logarithmus

Algorithmus

Güte der Anpassung

Routing

Abstand

Computeranimation

44:15

Kontrollstruktur

Reelle Zahl

Computeranimation

### Metadaten

#### Formale Metadaten

Titel | Traversing Mazes the pythonic way and other Algorithmic Adventures |

Serientitel | EuroPython 2014 |

Teil | 67 |

Anzahl der Teile | 120 |

Autor | Maggio, Valerio |

Lizenz |
CC-Namensnennung 3.0 Unported: Sie dürfen das Werk bzw. den Inhalt zu jedem legalen Zweck nutzen, verändern und in unveränderter oder veränderter Form vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen. |

DOI | 10.5446/20047 |

Herausgeber | EuroPython |

Erscheinungsjahr | 2014 |

Sprache | Englisch |

Produktionsort | Berlin |

#### Inhaltliche Metadaten

Fachgebiet | Informatik |

Abstract | Valerio Maggio - Traversing Mazes the pythonic way and other Algorithmic Adventures Graphs define a powerful mental (and mathematical) model of structure, representing the building blocks of formulations and/or solutions for many hard problems. In this talk, graphs and (some of the) main graph-related algorithms will be analysed from a very pythonic angle: the Zen of Python (e.g., beautiful is better than ugly, simple is better than complex, readability counts). |

Schlagwörter |
EuroPython Conference EP 2014 EuroPython 2014 |