Ayúdanos a dar forma a GoConqr. ¿Qué deberíamos añadir?

Mapa mental

D1 Maths

Grace Morris Maths A2 Inglés

Mind map about D1 maths: minimum connectors, travelling salesperson, flow charts and simplex algorithm

Mind map: D1 maths

Contenido del mapa

D1 Maths

  1. Minimum Connectors

    • Kruskal
      • Pick shortest edge
        • Pick next shortest edge (no cycle)
          • Repeat until all vertices = chosen
    • Prim
      • Select vertex
        • Select shortest edge connected to that vertex
          • Select shortest edge connected to any vertex already connected
            • Repeat until all vertices = connected
      • Matrix
        • Choose column, label it 1, and cross out its row
          • Choose smallest entry in that column and circle it
            • Cross out this row and label it 2
              • Continue until all vertices = selected
  2. Travelling Salesperson Problem

    • Lower bound algorithm
      • Total of 2 smallest weights of arcs to first node
        • Ignore first node and all arcs joined to it
          • Find the minimum connector
            • Sum of minimum connector and 2 smallest weights = lower bound
              • Repeat for all vertices and choose the highest
    • n nodes = (n-1)!/2 cycles
    • Optimum solution = in between lower and upper bound algorithms
    • Upper bound algorithm
      • Pick arc with the minimum weight joined to starting node
        • Repeat until all nodes are chosen
          • Add arc that joins last to first node
            • Repeat for all vertices and choose the lowest
  3. Packing Algorithm

    • First Fit
      • Place each object in turn in available space in which it will fit
    • First Fit Decreasing
      • Arrange in decreasing order then first fit
  4. Flow Charts

    • Oval = start/stop
    • Rectangle = instruction
    • Diamond = question
  5. Linear Programming

    • If vertices of feasible region = integers the use to solve problem
      • If not, then look at integer points closest to vertex
        • Take 2 values of x either side and find max value of y in feasible region
          • Sub in x and y values into constraints
            • Choose the smallest values
    • Shade unwanted region
    • State x=?, y=?, x≥0, y≥0, max/min function, constraints, draw graphs
    • Vertex method
      • Draw function as line graph and move parallel towards lines and first vertex = answer
    • Objective line method
      • Swap coefficients of x and y
        • Draw line then move parallel until it reaches feasible region
  6. Route Inspection/Chinese Postman problem

    • Only possible with Eulerian/semi
      • If semi, must repeat some edges
        • Locate all odd vertices
          • Find pairings for which total = smallest
            • Add up lengths of edges and pairing distances
              • Find route
  7. Order of an algorithm

    • Efficiency = run-time
    • Order = efficiency depending on size
    • Size = complexity
    • Efficiency α order
    • Bubble/shuttle sort = quadratic order 1/2(n(n-1))
    • Exponential order = very low efficiency
  8. Simplex Algorithm

    • Table with one row per equation and one column per variable
    • Top row = objective function equation
    • In each basis column, find 1 and read to final entry = value
    • Choose most negative entry in objective row = pivot element in pivot column
      • Do ratio test and choose minimum
        • Add/subtract multiples of pivot row to/from other rows
          • You are aiming to get the pivot column to 0s and get rid of negative numbers in objective row
  9. Sorting Algorithms

    • Bubble
      • Work left to right along list comparing 1st and 2nd then 2nd and 3rd (swapping if necessary)
        • 2nd pass with n-1 numbers etc
          • Keep going for n-1 passes until complete pass with no swaps
    • Shuttle
      • Compare 1st and 2nd item and swap if necessary
        • Compare 2nd and 3rd item and swap if necessary
          • If a swap is made go back to 1st and 2nd items
            • Repeat until n-1 passes
    • Total passes/swaps = 1/2(n(n-1))

Información

Descripción
A2 Maths Mapa Mental sobre D1 Maths, creado por Grace Morris el 10/05/2017.
Creado por
Grace Morris
Visitas
0
Valoración

Más sobre Graph and Network Algorithms

Escríbenos

¿Sobre qué es tu mensaje?

¿Qué deberíamos añadir?