Merken

Traversing Mazes the pythonic way and other Algorithmic Adventures

Zitierlink des Filmsegments
Embed Code

Automatisierte Medienanalyse

Beta
Erkannte Entitäten
Sprachtranskript
the
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
only any questions there
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
Algorithmus
Graph
Code
Ungerichteter Graph
Datenstruktur
Informatik
Code
Computeranimation
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
Shape <Informatik>
Graph
Zahlenbereich
Mailing-Liste
Ungerichteter Graph
Menge
Computeranimation
Rechenschieber
Objekt <Kategorie>
Graph
Metropolitan area network
Knotenmenge
Menge
Stichprobenumfang
Datenstruktur
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
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
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
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
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
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
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>
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
Metropolitan area network
Lineares Funktional
Knotenmenge
Logarithmus
Algorithmus
Güte der Anpassung
Routing
Abstand
Computeranimation
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

Ähnliche Filme

Loading...