Project Report

Get Started. It's Free
or sign up with your email address
Rocket clouds
Project Report by Mind Map: Project Report

1. knot theory

1.1. definitions

1.1.1. knot

1.1.2. knot projection

1.1.3. link

1.1.4. strands & under-/overcrossing

1.1.5. composite / prime

1.1.6. alternating

1.2. knot representations

1.2.1. planar

1.2.1.1. planar diagrams

1.2.1.2. Dowker codes / Gauss codes

1.2.1.3. planar graphs

1.2.2. 3-D

1.2.2.1. knot complement

1.2.2.2. polygonal

1.2.3. closed braids

1.2.4. Conway

1.2.4.1. def: tangle

1.3. history & application

1.3.1. Gauss: initial

1.3.2. Kelvin: knotted vortices

1.3.3. tabulation

1.3.3.1. Tait

1.3.3.2. Hoste

1.3.3.3. Rankin

1.3.4. applications

1.3.4.1. biology: knotted DNA

1.3.4.2. chemistry: knotted molecules

1.3.4.3. physics

1.4. knot equivalence

1.4.1. diagrammatic moves

1.4.1.1. Reidemeister

1.4.1.2. Flype

1.4.1.3. Markov moves on braids

1.4.2. invariants

1.4.2.1. tricolourability

1.4.2.2. polynomials

1.4.2.3. others

1.4.2.3.1. vassiliev

1.4.2.3.2. (?) minimum braid

1.4.3. special case: unknotting

1.4.3.1. Haken

1.4.3.2. NP bound

1.4.3.3. (?) Birman

1.4.3.4. Test cases

1.4.3.4.1. Monster

1.4.3.4.2. Freedman

1.4.3.4.3. Ochiai

1.4.4. types of knots

1.4.4.1. torus

1.4.4.2. satellite

1.4.4.3. hyperbolic

2. heuristic search

2.1. introduction

2.1.1. origin

2.1.2. definitions

2.1.2.1. optimisation problem

2.1.2.2. neighbourhood

2.1.2.3. cost/fitness function

2.1.3. types

2.1.3.1. local search

2.1.3.1.1. idea

2.1.3.1.2. examples

2.1.3.2. genetic algorithms

2.1.3.2.1. idea

2.2. simulated annealing

2.2.1. idea: metallurgy

2.2.2. pseudocode

2.2.3. parameters

2.2.3.1. cooling schedule

2.2.3.2. acceptance test

2.2.4. properties

2.2.4.1. theoretical convergence

2.3. tabu search

2.3.1. idea

2.3.2. pseudocode

2.3.3. parameters

2.3.3.1. adaptive memory

2.3.3.2. aspiration criteria

2.3.3.3. replacement criteria

2.3.4. properties

2.3.4.1. customisability

2.4. genetic algorithms

2.4.1. pseudocode

2.4.2. parameters

2.4.2.1. fitness function

2.4.2.2. reproduction

2.4.2.2.1. cross-over

2.4.2.2.2. mutation

2.4.2.3. selection

2.4.3. properties

2.4.3.1. non-local

2.4.3.2. parallel

2.5. applications to knot theory

2.5.1. unknotting

2.5.1.1. 3-D

2.5.1.1.1. energy functions

2.5.1.1.2. heuristic / gradient descent

2.5.1.2. planar

2.5.1.2.1. comparison to 3-D

2.5.1.3. examples

2.5.1.3.1. MING: Energy minimisation by gradient descent

2.5.1.3.2. Huang: Unknotting by annealing

2.5.1.3.3. Sharein: gradient descent

2.5.1.3.4. Ladd/Kavraki: Motion planning

2.5.1.3.5. Weaver: Planar annealing

2.5.2. other

2.5.2.1. Johnson: disproving conjectures

3. Plug & Play Tool

3.1. requirements

3.1.1. functional

3.1.1.1. flexible

3.1.1.2. extensible

3.1.1.3. efficient

3.1.1.4. manual / automated

3.1.2. process

3.1.2.1. timely / plannable

3.1.2.2. scalable

3.1.2.3. incremental

3.1.3. key functionalities

3.1.3.1. knot representation & manipulation

3.1.3.2. search

3.1.3.3. statistics & visualisation

3.2. architecture

3.2.1. process

3.2.1.1. comparison

3.2.1.1.1. waterfall

3.2.1.1.2. v-model

3.2.1.1.3. agile / xp

3.2.1.2. test-driven

3.2.1.3. incremental

3.2.1.4. (?) refactoring

3.2.2. technology

3.2.2.1. language

3.2.2.1.1. ruby + C

3.2.2.1.2. flexible

3.2.2.1.3. fast

3.2.2.2. shell interfacing + GUI

3.2.2.3. external tools

3.2.2.3.1. gnuplot

3.3. design

3.3.1. high-level structure

3.3.1.1. gui

3.3.1.2. experiment

3.3.1.2.1. load & save

3.3.1.3. heuristic search

3.3.1.4. problem

3.3.1.4.1. neighbourhood

3.3.1.4.2. cost

3.3.1.4.3. solution

3.3.1.5. knot manipulation

3.3.2. heuristic search

3.3.2.1. interface

3.3.2.2. criteria

3.3.2.3. simulated annealing

3.3.2.3.1. cooling schedule

3.3.3. knot manipulation

3.3.3.1. criteria

3.3.3.1.1. complete

3.3.3.1.2. unambiguous

3.3.3.1.3. manipulable

3.3.3.1.4. efficient

3.3.3.1.5. (?) scalable

3.3.3.1.6. (?) evaluable

3.3.3.1.7. availability of data

3.3.3.2. planar

3.3.3.2.1. data structures

3.3.3.2.2. interface

3.3.3.3. 3-D

3.3.3.3.1. data structures

3.3.3.3.2. interface

3.4. V & V

3.4.1. unit testing

3.4.2. integration testing

3.4.3. sanity checks

4. Experimentation

4.1. test cases

4.1.1. categories

4.1.1.1. torus/satellite/hyperbolic

4.1.1.2. prime / composite

4.1.1.3. reduced / non-reduced

4.1.1.4. mutant: KT

4.1.1.5. chiral

4.1.1.6. unknots: Monster, Freedman, Ochiai

4.1.1.7. knots: Perko

4.1.2. list of projections

4.1.2.1. caveats

4.1.2.2. generation

4.1.2.2.1. dowker codes

4.1.2.2.2. culling

4.1.2.2.3. pipeline

4.1.2.2.4. efficiency concerns

4.2. preliminary experiments

4.2.1. redo weaver

4.2.2. add ochiai

4.2.3. random perturbation very weak

4.2.4. different weights for Reid moves

4.3. planar direct search

4.3.1. testing for identical projections

4.3.1.1. graph isomorphism

4.3.1.2. cost functions

4.3.1.2.1. criteria

4.3.1.2.2. degree of isomorphism

4.3.1.2.3. sum of characteristics

4.3.1.2.4. sum + grounding term

4.3.1.2.5. Weisfeiler Lehman cost

4.3.2. one sided / two sided

4.3.3. bounds

4.3.3.1. classifying projections

4.3.3.2. finding bounds

4.3.3.3. results

4.3.3.4. other moves: flypes

4.3.3.5. other identity test: only WL cost

4.4. planar statistical

4.4.1. initial: search results

4.4.2. search process statistics

4.4.2.1. sources

4.4.2.1.1. accept streak

4.4.2.1.2. cost function

4.4.2.2. problems

4.4.2.2.1. higher crossing numbers

4.4.2.2.2. requires bounds

4.4.2.2.3. cannot manage chirality

4.4.2.3. other areas

4.4.2.3.1. word problem: braids

4.4.2.3.2. graph isomorphism

4.5. 3-D

4.5.1. experimentation

4.5.1.1. same as for statistical

4.5.2. results

4.5.2.1. harder to find global optima

4.5.2.2. weird: deeper search -> worse results

5. Evaluation

5.1. planar direct search

5.1.1. proof of concept

5.1.2. bounds

5.2. statistical

5.2.1. automatic "invariants"

5.2.2. transferable

5.3. software engineering

6. Objectives

6.1. insufficiencies

6.1.1. only unknotting

6.1.1.1. uniqueness below threshold

6.1.1.2. unique global minima

6.1.2. local minima (?)

6.1.3. negative results

6.2. knot equivalence

6.2.1. bounds

6.2.2. statistical methods

6.3. tool

6.3.1. efficient exploration

6.3.1.1. multiple knot representations

6.3.1.2. multiple heuristic searches

6.3.1.3. multiple cost functions

7. Conclusion