From df6269ce248021e9705c716346751e3afa924ba0 Mon Sep 17 00:00:00 2001 From: Gregor Kleen Date: Wed, 3 May 2017 13:45:13 +0200 Subject: Some work on structure --- ss2017/stable_marriage_problem/structure.md | 29 +++++++++++++++++++++++++++++ 1 file changed, 29 insertions(+) create mode 100644 ss2017/stable_marriage_problem/structure.md (limited to 'ss2017/stable_marriage_problem') diff --git a/ss2017/stable_marriage_problem/structure.md b/ss2017/stable_marriage_problem/structure.md new file mode 100644 index 0000000..89f467c --- /dev/null +++ b/ss2017/stable_marriage_problem/structure.md @@ -0,0 +1,29 @@ + - Implement algorithm in haskell, split over single steps + - 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` + - For most important proofs (tbd) show applicable step in haskell code with sketch of proof + + +# Tables + - Definition: Tables, embedded tables, embedded pairs, embedded matchings + - Definition: stable tables + - Matchings embedded in stable tables are stable (4.2.4 ii) + - (Stable tables are determined by all first OR all last entries (4.2.4 iii)) + - No pair absent from a stable table can block any of it's embedded matchings (4.2.4 i) + +# Phase 1 + - Present algorithm and demonstrate + - Phase 1 has no effect on the embeddedness of stable pairs (4.2.3 i) + - Phase 1 stabilizes a table, when it doesn't fail (4.2.2 + 4.2.3 ii) + - Phase 1 results in the largest stable table (4.2.4 iv) + +# Rotations + - Definition: rotation, exposure of rotations in stable tables + - Rotations exposed in a stable T are either identical or disjunct (4.2.5) + +# Phase 2 + - Stable tables that are not already matchings expose at least one rotation and how to find it (4.2.6) + - Elimination of rotations from stable tables + - ignores non-elements of rotation (4.2.7 iii) + - results in table consistent with rotation (4.2.7 i, ii) + - Thus: produce stable subtables (4.2.8) + - Present derived algorithm and demonstrate -- cgit v1.2.3