Karteikarten
Decision key points
Karten in diesem Stapel (51)
- 1DecisionAlgorithms
- 2Algorithms can be given in words or flowchartsUnordered list can be sorted using a bubble sort or a quick sort
- 3In a bubble sort, you compared adjacent items in a list - If they are in order, leave them - If they are not in order, swap them - The list is in order when a pass is completed without any swapsIn a quick sort, you select a pivot and then split the items into sub-lists: those less than the pivot and those greater than the pivot. Do this for every sub-list.
- 4In a quick sort, the item at the mid-point of the list is chosen as the pivot - Items less than the pivot are written down, keeping there order - The pivot is written next - Items greater than the pivot are written down, keeping their orderA binary search will search an ordered list to find out whether an item is on the list. If it is on the list, it will locate its position in the list.
- 5In a binary search, the pivot is the middle item on the list. If the target item is not the pivot, the pivot and half the list are discarded. The list splits in half with each pass.The middle of n items is found by [{1 + n}/2], rounding up if necessary.
- 6The three bin packing algorithms are first-fit, first-fit decreasing and full binFirst fit algorithm takes items in the order given
Advantage - Quick to do
Disadvantage - Not likely to lead to a good solution - 7First-fit decreasing algorithm requires the items to be in descending order before applying the algorithm Advantage - Usually a good solution - Easy to do Disadvantage - May not get an optimal solutionFull bin packing uses inspection to select items that will combine to full bins. Remaining items packed using the first-fit algorithm
Advantage - Usually a good solution
Disadvantage - Difficult to do, especially when lots of numbers or awkward numbers - 8Graphs and networksIf the graph has a number associated with each edge (its weight) then the graph is a weighted graph (network)
- 9A graph consists of ...A graph consists of vertices (nodes) which are connected by edges (arcs)
- 10A sub-graph is ...A sub-graph is part of a graph
- 11The degree or valency (or order) of a vertex is ...The degree or valency (or order) of a vertex is the number of edges incident to it
- 12A path is ...A path is a finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more than once
- 13A cycle (circuit) is ...A cycle (circuit) is a closed path, i.e. the end vertex of the last edge is the start vertex of the first edge
- 14Two vertices are connected if ...Two vertices are connected if there is a path between them.
- 15A graph is connected if ...A graph is connected if all the vertices are connected
- 16A loop is ...A loop is an edge that starts and finishes at the same vertex
- 17A simple graph is ...A simple graph is one in which there are no loops and not more than one edge connecting any pair of vertices
- 18If the edges of a graph have a direction associated with them they are known as a directed edges and the graph is known a digraph*blank*
- 19A tree is ...A tree is a connected graph with no cycle
- 20A spanning tree is ...A spanning tree of a graph, G, is a subgraph which includes all the vertices of G and is also a tree
- 21A bipartite graph consists of ...A bipartite graph consists of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set
- 22A complete graph is ...A complete graph is a graph in which every vertex is directly connected by an edge to each of the other vertices. If the graph has n vertices the connected graph is denoted Kn.
- 23A complete bipartite graph (denoted Kr,s) is ...A complete bipartite graph (denoted Kr,s) is a graph in which there are r vertices in set X and s vertices in set Y
- 24Isomorphic graphs show ...Isomorphic graphs show the same information but are drawn differently
- 25An adjacency matrix records ...An adjacency matrix records the number of direct links between vertices
- 26A distance matrix records ...A distance matrix records the weight on the weights on the edges. Where there is no weight , this is indicted by '-'
- 27Algorithms on networksKrusal's algorithm and Prim's algorithm can be used to find a minimum spanning tree, but they take different approachs
- 28To use Krusal's algorithm, you sort the arcs into ascending order of weight and use the arc of least weight to start the tree. You then add arcs in order of ascending weight, unless an arc would form a cycle, in which case it is rejectedTo use Prim's algorithm, you choose any vertex to start the tree. You then select an arc of least weight that joins a vertex that is already in the tree to a vertex that is not yet in the tree. You repeat this until all vertices are connected
- 29Prim's algorithm can be applied to a distance matrix. You choose any vertex to start the tree. You delete the row in the matrix for the chosen vertex. You ring the lowest undeleted entry in the labelled columns, which becomes the next vertex. You repeat this until all rows are deleted.You can use Dijkastra's algorithm to find the shortest path between two vertices in a network
- 30In Dijkstra's algorithm, the start vertex is given the final value 0. Every vertex that is directly connected to the start vertex is given a working value (final value + weight of the arc.) Select the smallest working value. This is the final value for that vertex. Repeat until the destination vertex receives its final label. Final the shortest path by tracing back from destination to start. Include an arc AB on the route if B is already on the route and final label B - final label A = weight of arc ABEach vertex is replaced by a box
(Look in textbook for diagram) - 31Route inspection (Chinese postman problem)A graph will be traversable if all the vertices are even
- 32A graph is traversable if ...A graph is traversable if it is possible to traverse (travel along) every arc just once without taking your pen from the paper
- 33A graph will be traversable if all the vertices are evenA graph is
- 34A graph is semi-traversable if ...A graph is semi-traversable if it has precisely two odd valencies. In this case, the start and finish will be with the odd valencies.
- 35A graph is not traversable if ...A graph is not traversable if it has more than two odd valencies
- 36The route inspection algorithm can be used to find the shortest route that traverses every arc at least once and returns to the starting pointIf there are only two odd vertices, repeat the shortest path between them and add it to the network
- 37If there are more than odd valencies, consider all possible complete pairings, select the one that gives the smallest total, then add this pairing to the network*blank*
- 38Critical path analysisA complex project may be broken down into a number of separate activities. The completion of an activity is described as an event
- 39Some activities may only be started once other activities are completed. This information is shown in a precedence table, sometimes called a dependence tableAn activity network provides a visual representation of the information given in a precedence table which makes it easier to work with. The type of activity network used on this course is called an activity on arc network. In this type of network, the activities are represented by arcs and events are represented as nodes
- 40Each event has an early event time and a late event time. The early event time is the earliest time at which all of the dependent events may be completed. The late event time is the latest time at which any of the dependent events may be completed without delaying the project. Early event timed are calculated using a forward scan and late event times are calculated using a backwards scanAt each vertex on a critical path the early event time is equal to the late event time
- 41An activity is described as a critical activity if any increase in its duration results in a corresponding increase in the duration of the whole projectA path from the source node to the sink node which entirely follows critical activities is called a critical path. A critical pathAt each vertex on a critical path the early event time is equal to the late event time is longest path containing in the network. It is possible for a possible to have more than one critical path, in which case the total project time is the same on each one
- 42The total float of an activity is ...The total float of an activity is the amount of time that its start may be delayed without affecting the duration of the project. Total float = latest finish time - duration - earliest start time
The total float of any critical activity is zero - 43A cascade (Gantt) chart provides a graphical way to represent the range of possible start and finish times for all activities on a single diagramA scheduling diagram is used to show how tasks are allocated to workers in order to complete a project subject to constraints on the time required or the number of workers available
- 44In general, a lower bound for the number of workers needed to complete a project within its critical time is given by the smallest integer greater than or equal to {sum of all of the activity times} / {critical time of the project}A dummy activity is shown by a dotted line. It has an arrow to indicate direction, but no weight
- 45What are the two reasons dummies are needed?Dummies are needed for two reasons:
- for example, if activity D depends only on activity B but activity E depends on activies B and C
- to enable the unique representation of activities in terms of their end eventd - 46Linear ProgrammingDoing after Christmas
- 47MatchingA bipartite graph has two sets of nodes
- 48Arcs may connect nodes from different sets but never connect nodes in the same setAn alternating path starts at an unmatched node on one side of a bipartite graph and finishes at an unmatched node on the other side. It uses arcs that are alternately 'not in' and 'in' the initial matching
- 49When you have drawn a bipartite graph, you can find an improved matching using the maximum matching algorithmThe maximum matching algorithm is as follows.
- Start with any initial matching
- Search for an alternating path
- If an alternating path can be found, use it to create an improved matching by changing the status of the arcs (in -> out, out -> in). If an alternative path cannot be found, stop.
(continues) - 50The maximum matching algorithm is as follows. (continued) - List the new matching, which consists of the results of applying the alternating path together with any unchanged elements of the previous matching - If the matching is now complete, stop. Otherwise look for another alternating pathIf there is more than one pair of unmatched nodes you will need to find more than one alternating path
- 51Each time you apply the maximum matching algorithm you increase the number of matched pairs by one*blank*
Informationen
- Beschreibung
- AS level Maths Karteikarten am Decision key points, erstellt von Benjamin Smith am 20/12/2017.
- Erstellt von
- Benjamin Smith
- Aufrufe
- 5
- Bewertung
Mehr zu Graph and Network Algorithms