diff options
author | Gregor Kleen <gkleen@yggdrasil.li> | 2017-05-31 11:40:49 +0200 |
---|---|---|
committer | Gregor Kleen <gkleen@yggdrasil.li> | 2017-05-31 11:40:49 +0200 |
commit | ca4d88e67d39d3071304508017e6543ab19d160d (patch) | |
tree | 7493f12c58c6e32fd518f24e007da1b24aa4d3ff /ss2017/stable_marriage_problem/structure.md | |
parent | 334ea750eb86da45764fd22d25524a80a5531597 (diff) | |
download | uni-ca4d88e67d39d3071304508017e6543ab19d160d.tar uni-ca4d88e67d39d3071304508017e6543ab19d160d.tar.gz uni-ca4d88e67d39d3071304508017e6543ab19d160d.tar.bz2 uni-ca4d88e67d39d3071304508017e6543ab19d160d.tar.xz uni-ca4d88e67d39d3071304508017e6543ab19d160d.zip |
Move stable-marriage-problem to submodule
Diffstat (limited to 'ss2017/stable_marriage_problem/structure.md')
-rw-r--r-- | ss2017/stable_marriage_problem/structure.md | 35 |
1 files changed, 0 insertions, 35 deletions
diff --git a/ss2017/stable_marriage_problem/structure.md b/ss2017/stable_marriage_problem/structure.md deleted file mode 100644 index fa9ac96..0000000 --- a/ss2017/stable_marriage_problem/structure.md +++ /dev/null | |||
@@ -1,35 +0,0 @@ | |||
1 | - Implement algorithm in haskell, split over single steps | ||
2 | - During presentation show steps working on examples of the problem (one solves during step 1, one fails during step 1, one that requires multiple rotations to be eliminated), within `ghci` | ||
3 | - For most important proofs (tbd) show applicable step in haskell code with sketch of proof | ||
4 | |||
5 | |||
6 | # Tables | ||
7 | - Definition: Tables, embedded tables, embedded pairs, embedded matchings | ||
8 | - Definition: stable tables | ||
9 | - Matchings embedded in stable tables are stable (4.2.4 ii) | ||
10 | - Stable tables are determined by all first OR all last entries (4.2.4 iii) | ||
11 | - No pair absent from a stable table can block any of it's embedded matchings (4.2.4 i) | ||
12 | |||
13 | # Phase 1 | ||
14 | - Removal of pairs from tables | ||
15 | - Engagement | ||
16 | - Present algorithm and demonstrate | ||
17 | - Phase 1 has no effect on the embeddedness of stable pairs (4.2.3 i) | ||
18 | - Phase 1 stabilizes a table, when it doesn't fail (4.2.2 + 4.2.3 ii) | ||
19 | - Phase 1 results in the largest stable table (4.2.4 iv) | ||
20 | |||
21 | # Rotations | ||
22 | - Definition: rotation, exposure of rotations in stable tables | ||
23 | - Directed graphs & tails | ||
24 | - (Rotations exposed in a stable T are either identical or disjunct (4.2.5)) | ||
25 | |||
26 | # Phase 2 | ||
27 | - Stable tables that are not already matchings expose at least one rotation and how to find it (4.2.6) | ||
28 | - Elimination of rotations from stable tables | ||
29 | - ignores non-elements of rotation (4.2.7 iii) | ||
30 | - results in table consistent with rotation (4.2.7 i, ii) | ||
31 | - Thus: produce stable subtables (4.2.8) | ||
32 | - Subtables that don't agree with an exposed rotation have at least that rotation removed entirely (4.2.9) | ||
33 | - Any subtable can be created by removing a series of exposed rotations (Cor 4.2.2) | ||
34 | - Removal of rotations preserve matchings (Thm 4.2.1) | ||
35 | - Present derived algorithm and demonstrate | ||