Mercurial > hg > Papers > 2016 > atton-ipsjpro
changeset 53:fa1d602b1676
Add rbtree image
| author | Yasutaka Higa <e115763@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Thu, 04 Aug 2016 18:11:02 +0900 |
| parents | 02e5ae71c319 |
| children | a0bffeced069 |
| files | presentation/images/code_segments.graffle presentation/images/code_segments.pdf presentation/images/code_segments.svg presentation/images/rbtree.graffle presentation/images/rbtree.pdf presentation/images/rbtree.svg presentation/slide.md |
| diffstat | 7 files changed, 145 insertions(+), 857 deletions(-) [+] |
line wrap: on
line diff
--- a/presentation/images/code_segments.graffle Wed Aug 03 17:53:25 2016 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,601 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd"> -<plist version="1.0"> -<dict> - <key>ActiveLayerIndex</key> - <integer>0</integer> - <key>ApplicationVersion</key> - <array> - <string>com.omnigroup.OmniGraffle6</string> - <string>169.17.0.263360</string> - </array> - <key>AutoAdjust</key> - <true/> - <key>BackgroundGraphic</key> - <dict> - <key>Bounds</key> - <string>{{0, 0}, {559, 783}}</string> - <key>Class</key> - <string>SolidGraphic</string> - <key>ID</key> - <integer>2</integer> - <key>Style</key> - <dict> - <key>stroke</key> - <dict> - <key>Draws</key> - <string>NO</string> - </dict> - </dict> - </dict> - <key>BaseZoom</key> - <integer>0</integer> - <key>CanvasOrigin</key> - <string>{0, 0}</string> - <key>ColumnAlign</key> - <integer>1</integer> - <key>ColumnSpacing</key> - <real>36</real> - <key>CreationDate</key> - <string>2012-02-05 20:00:27 +0000</string> - <key>Creator</key> - <string>Kazuki AKAMINE</string> - <key>DisplayScale</key> - <string>1 in = 1 in</string> - <key>GraphDocumentVersion</key> - <integer>12</integer> - <key>GraphicsList</key> - <array> - <dict> - <key>AllowLabelDrop</key> - <false/> - <key>Class</key> - <string>LineGraphic</string> - <key>Head</key> - <dict> - <key>ID</key> - <integer>44</integer> - </dict> - <key>ID</key> - <integer>45</integer> - <key>Points</key> - <array> - <string>{227.05808893202135, 162.32628729047525}</string> - <string>{274.00441106797865, 156.04871270952472}</string> - </array> - <key>Style</key> - <dict> - <key>shadow</key> - <dict> - <key>Draws</key> - <string>NO</string> - </dict> - <key>stroke</key> - <dict> - <key>HeadArrow</key> - <string>FilledArrow</string> - <key>HeadScale</key> - <real>1.4285709857940674</real> - <key>Legacy</key> - <true/> - <key>TailArrow</key> - <string>0</string> - <key>TailScale</key> - <real>0.5</real> - </dict> - </dict> - <key>Tail</key> - <dict> - <key>ID</key> - <integer>33</integer> - </dict> - </dict> - <dict> - <key>Bounds</key> - <string>{{274.5, 125.5}, {82, 50}}</string> - <key>Class</key> - <string>ShapedGraphic</string> - <key>ID</key> - <integer>44</integer> - <key>Style</key> - <dict> - <key>shadow</key> - <dict> - <key>Draws</key> - <string>NO</string> - </dict> - </dict> - <key>Text</key> - <dict> - <key>Text</key> - <string>{\rtf1\ansi\ansicpg1252\cocoartf1348\cocoasubrtf170 -{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc - -\f0\fs24 \cf0 Code\ -Segment}</string> - </dict> - </dict> - <dict> - <key>AllowLabelDrop</key> - <false/> - <key>Class</key> - <string>LineGraphic</string> - <key>ID</key> - <integer>42</integer> - <key>Points</key> - <array> - <string>{227.04657487753181, 43.603137424407386}</string> - <string>{274.5, 55.875}</string> - </array> - <key>Style</key> - <dict> - <key>shadow</key> - <dict> - <key>Draws</key> - <string>NO</string> - </dict> - <key>stroke</key> - <dict> - <key>HeadArrow</key> - <string>FilledArrow</string> - <key>HeadScale</key> - <real>1.4285709857940674</real> - <key>Legacy</key> - <true/> - <key>TailArrow</key> - <string>0</string> - <key>TailScale</key> - <real>0.5</real> - </dict> - </dict> - <key>Tail</key> - <dict> - <key>ID</key> - <integer>30</integer> - </dict> - </dict> - <dict> - <key>Bounds</key> - <string>{{274.5, 31.5}, {82, 50}}</string> - <key>Class</key> - <string>ShapedGraphic</string> - <key>ID</key> - <integer>41</integer> - <key>Style</key> - <dict> - <key>shadow</key> - <dict> - <key>Draws</key> - <string>NO</string> - </dict> - </dict> - <key>Text</key> - <dict> - <key>Text</key> - <string>{\rtf1\ansi\ansicpg1252\cocoartf1348\cocoasubrtf170 -{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc - -\f0\fs24 \cf0 Code\ -Segment}</string> - </dict> - </dict> - <dict> - <key>AllowLabelDrop</key> - <false/> - <key>Class</key> - <string>LineGraphic</string> - <key>Head</key> - <dict> - <key>ID</key> - <integer>38</integer> - </dict> - <key>ID</key> - <integer>40</integer> - <key>Points</key> - <array> - <string>{97.098722833775156, 70.504114203612403}</string> - <string>{144.08877716622484, 86.370885796387611}</string> - </array> - <key>Style</key> - <dict> - <key>shadow</key> - <dict> - <key>Draws</key> - <string>NO</string> - </dict> - <key>stroke</key> - <dict> - <key>HeadArrow</key> - <string>FilledArrow</string> - <key>HeadScale</key> - <real>1.4285709857940674</real> - <key>Legacy</key> - <true/> - <key>TailArrow</key> - <string>0</string> - <key>TailScale</key> - <real>0.5</real> - </dict> - </dict> - <key>Tail</key> - <dict> - <key>ID</key> - <integer>15</integer> - </dict> - </dict> - <dict> - <key>AllowLabelDrop</key> - <false/> - <key>Class</key> - <string>LineGraphic</string> - <key>Head</key> - <dict> - <key>ID</key> - <integer>33</integer> - </dict> - <key>ID</key> - <integer>39</integer> - <key>Points</key> - <array> - <string>{97.120588932021334, 156.04871270952475}</string> - <string>{144.06691106797865, 162.32628729047528}</string> - </array> - <key>Style</key> - <dict> - <key>shadow</key> - <dict> - <key>Draws</key> - <string>NO</string> - </dict> - <key>stroke</key> - <dict> - <key>HeadArrow</key> - <string>FilledArrow</string> - <key>HeadScale</key> - <real>1.4285709857940674</real> - <key>Legacy</key> - <true/> - <key>TailArrow</key> - <string>0</string> - <key>TailScale</key> - <real>0.5</real> - </dict> - </dict> - <key>Tail</key> - <dict> - <key>ID</key> - <integer>17</integer> - </dict> - </dict> - <dict> - <key>Bounds</key> - <string>{{144.5625, 75.375}, {82, 50}}</string> - <key>Class</key> - <string>ShapedGraphic</string> - <key>ID</key> - <integer>38</integer> - <key>Style</key> - <dict> - <key>shadow</key> - <dict> - <key>Draws</key> - <string>NO</string> - </dict> - </dict> - <key>Text</key> - <dict> - <key>Text</key> - <string>{\rtf1\ansi\ansicpg1252\cocoartf1348\cocoasubrtf170 -{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc - -\f0\fs24 \cf0 Code\ -Segment}</string> - </dict> - </dict> - <dict> - <key>AllowLabelDrop</key> - <false/> - <key>Class</key> - <string>LineGraphic</string> - <key>Head</key> - <dict> - <key>ID</key> - <integer>30</integer> - </dict> - <key>ID</key> - <integer>37</integer> - <key>Points</key> - <array> - <string>{96.625, 58.5}</string> - <string>{144.08204500032224, 44.826501440525568}</string> - </array> - <key>Style</key> - <dict> - <key>shadow</key> - <dict> - <key>Draws</key> - <string>NO</string> - </dict> - <key>stroke</key> - <dict> - <key>HeadArrow</key> - <string>FilledArrow</string> - <key>HeadScale</key> - <real>1.4285709857940674</real> - <key>Legacy</key> - <true/> - <key>TailArrow</key> - <string>0</string> - <key>TailScale</key> - <real>0.5</real> - </dict> - </dict> - </dict> - <dict> - <key>Bounds</key> - <string>{{144.5625, 142.875}, {82, 50}}</string> - <key>Class</key> - <string>ShapedGraphic</string> - <key>ID</key> - <integer>33</integer> - <key>Style</key> - <dict> - <key>shadow</key> - <dict> - <key>Draws</key> - <string>NO</string> - </dict> - </dict> - <key>Text</key> - <dict> - <key>Text</key> - <string>{\rtf1\ansi\ansicpg1252\cocoartf1348\cocoasubrtf170 -{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc - -\f0\fs24 \cf0 Code\ -Segment}</string> - </dict> - </dict> - <dict> - <key>Bounds</key> - <string>{{144.5625, 7.875}, {82, 50}}</string> - <key>Class</key> - <string>ShapedGraphic</string> - <key>ID</key> - <integer>30</integer> - <key>Style</key> - <dict> - <key>shadow</key> - <dict> - <key>Draws</key> - <string>NO</string> - </dict> - </dict> - <key>Text</key> - <dict> - <key>Text</key> - <string>{\rtf1\ansi\ansicpg1252\cocoartf1348\cocoasubrtf170 -{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc - -\f0\fs24 \cf0 Code\ -Segment}</string> - </dict> - </dict> - <dict> - <key>Bounds</key> - <string>{{14.625, 125.5}, {82, 50}}</string> - <key>Class</key> - <string>ShapedGraphic</string> - <key>ID</key> - <integer>17</integer> - <key>Style</key> - <dict> - <key>shadow</key> - <dict> - <key>Draws</key> - <string>NO</string> - </dict> - </dict> - <key>Text</key> - <dict> - <key>Text</key> - <string>{\rtf1\ansi\ansicpg1252\cocoartf1348\cocoasubrtf170 -{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc - -\f0\fs24 \cf0 Code\ -Segment}</string> - </dict> - </dict> - <dict> - <key>Bounds</key> - <string>{{14.625, 31.5}, {82, 50}}</string> - <key>Class</key> - <string>ShapedGraphic</string> - <key>ID</key> - <integer>15</integer> - <key>Style</key> - <dict> - <key>shadow</key> - <dict> - <key>Draws</key> - <string>NO</string> - </dict> - </dict> - <key>Text</key> - <dict> - <key>Text</key> - <string>{\rtf1\ansi\ansicpg1252\cocoartf1348\cocoasubrtf170 -{\fonttbl\f0\fswiss\fcharset0 Helvetica;} -{\colortbl;\red255\green255\blue255;} -\pard\tx560\tx1120\tx1680\tx2240\tx2800\tx3360\tx3920\tx4480\tx5040\tx5600\tx6160\tx6720\pardirnatural\qc - -\f0\fs24 \cf0 Code\ -Segment}</string> - </dict> - </dict> - </array> - <key>GridInfo</key> - <dict/> - <key>GuidesLocked</key> - <string>NO</string> - <key>GuidesVisible</key> - <string>YES</string> - <key>HPages</key> - <integer>1</integer> - <key>ImageCounter</key> - <integer>1</integer> - <key>KeepToScale</key> - <false/> - <key>Layers</key> - <array> - <dict> - <key>Lock</key> - <string>NO</string> - <key>Name</key> - <string>レイヤー 1</string> - <key>Print</key> - <string>YES</string> - <key>Slices</key> - <string>NO</string> - <key>View</key> - <string>YES</string> - </dict> - </array> - <key>LayoutInfo</key> - <dict> - <key>Animate</key> - <string>NO</string> - <key>circoMinDist</key> - <real>18</real> - <key>circoSeparation</key> - <real>0.0</real> - <key>layoutEngine</key> - <string>dot</string> - <key>neatoLineLength</key> - <real>0.20000000298023224</real> - <key>neatoSeparation</key> - <real>0.0</real> - <key>twopiSeparation</key> - <real>0.0</real> - </dict> - <key>LinksVisible</key> - <string>NO</string> - <key>MagnetsVisible</key> - <string>NO</string> - <key>MasterSheets</key> - <array/> - <key>ModificationDate</key> - <string>2016-08-02 07:48:28 +0000</string> - <key>Modifier</key> - <string>atton</string> - <key>NotesVisible</key> - <string>NO</string> - <key>Orientation</key> - <integer>2</integer> - <key>OriginVisible</key> - <string>NO</string> - <key>PageBreaks</key> - <string>YES</string> - <key>PrintInfo</key> - <dict> - <key>NSBottomMargin</key> - <array> - <string>float</string> - <string>41</string> - </array> - <key>NSHorizonalPagination</key> - <array> - <string>coded</string> - <string>BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG</string> - </array> - <key>NSLeftMargin</key> - <array> - <string>float</string> - <string>18</string> - </array> - <key>NSPaperSize</key> - <array> - <string>size</string> - <string>{595, 842}</string> - </array> - <key>NSPrintReverseOrientation</key> - <array> - <string>coded</string> - <string>BAtzdHJlYW10eXBlZIHoA4QBQISEhAhOU051bWJlcgCEhAdOU1ZhbHVlAISECE5TT2JqZWN0AIWEASqEhAFxlwCG</string> - </array> - <key>NSRightMargin</key> - <array> - <string>float</string> - <string>18</string> - </array> - <key>NSTopMargin</key> - <array> - <string>float</string> - <string>18</string> - </array> - </dict> - <key>PrintOnePage</key> - <false/> - <key>ReadOnly</key> - <string>NO</string> - <key>RowAlign</key> - <integer>1</integer> - <key>RowSpacing</key> - <real>36</real> - <key>SheetTitle</key> - <string>キャンバス 1</string> - <key>SmartAlignmentGuidesActive</key> - <string>YES</string> - <key>SmartDistanceGuidesActive</key> - <string>YES</string> - <key>UniqueID</key> - <integer>1</integer> - <key>UseEntirePage</key> - <false/> - <key>VPages</key> - <integer>1</integer> - <key>WindowInfo</key> - <dict> - <key>CurrentSheet</key> - <integer>0</integer> - <key>Expanded_Canvases</key> - <array/> - <key>Frame</key> - <string>{{110, 115}, {1449, 937}}</string> - <key>ShowInfo</key> - <true/> - <key>ShowRuler</key> - <true/> - <key>Sidebar</key> - <true/> - <key>SidebarWidth</key> - <integer>200</integer> - <key>TopSlabHeight</key> - <real>250</real> - <key>VisibleRegion</key> - <string>{{-64, 0}, {687.50000000000011, 573.52941176470597}}</string> - <key>Zoom</key> - <real>1.3599999999999999</real> - <key>ZoomValues</key> - <array> - <array> - <string>キャンバス 1</string> - <real>1.3599999999999999</real> - <real>1.3500000000000001</real> - </array> - </array> - </dict> -</dict> -</plist>
--- a/presentation/images/code_segments.svg Wed Aug 03 17:53:25 2016 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,217 +0,0 @@ -<?xml version="1.0" encoding="UTF-8"?> -<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" width="365pt" height="208pt" viewBox="0 0 365 208" version="1.1"> -<defs> -<g> -<symbol overflow="visible" id="glyph0-0"> -<path style="stroke:none;" d="M 0.390625 0 L 0.390625 -8.609375 L 7.21875 -8.609375 L 7.21875 0 Z M 6.140625 -1.078125 L 6.140625 -7.53125 L 1.46875 -7.53125 L 1.46875 -1.078125 Z M 6.140625 -1.078125 "/> -</symbol> -<symbol overflow="visible" id="glyph0-1"> -<path style="stroke:none;" d="M 4.546875 -8.84375 C 5.628906 -8.84375 6.472656 -8.554688 7.078125 -7.984375 C 7.679688 -7.410156 8.015625 -6.757812 8.078125 -6.03125 L 6.9375 -6.03125 C 6.8125 -6.582031 6.554688 -7.019531 6.171875 -7.34375 C 5.785156 -7.664062 5.242188 -7.828125 4.546875 -7.828125 C 3.703125 -7.828125 3.019531 -7.53125 2.5 -6.9375 C 1.976562 -6.34375 1.71875 -5.429688 1.71875 -4.203125 C 1.71875 -3.191406 1.953125 -2.367188 2.421875 -1.734375 C 2.890625 -1.109375 3.59375 -0.796875 4.53125 -0.796875 C 5.382812 -0.796875 6.039062 -1.128906 6.5 -1.796875 C 6.726562 -2.140625 6.90625 -2.597656 7.03125 -3.171875 L 8.15625 -3.171875 C 8.0625 -2.265625 7.726562 -1.503906 7.15625 -0.890625 C 6.46875 -0.148438 5.546875 0.21875 4.390625 0.21875 C 3.390625 0.21875 2.550781 -0.0820312 1.875 -0.6875 C 0.976562 -1.488281 0.53125 -2.722656 0.53125 -4.390625 C 0.53125 -5.660156 0.863281 -6.703125 1.53125 -7.515625 C 2.257812 -8.398438 3.265625 -8.84375 4.546875 -8.84375 Z M 4.3125 -8.84375 Z M 4.3125 -8.84375 "/> -</symbol> -<symbol overflow="visible" id="glyph0-2"> -<path style="stroke:none;" d="M 3.265625 -0.6875 C 3.960938 -0.6875 4.441406 -0.945312 4.703125 -1.46875 C 4.960938 -2 5.09375 -2.585938 5.09375 -3.234375 C 5.09375 -3.828125 5 -4.304688 4.8125 -4.671875 C 4.507812 -5.242188 4 -5.53125 3.28125 -5.53125 C 2.632812 -5.53125 2.164062 -5.285156 1.875 -4.796875 C 1.582031 -4.304688 1.4375 -3.710938 1.4375 -3.015625 C 1.4375 -2.347656 1.582031 -1.789062 1.875 -1.34375 C 2.164062 -0.90625 2.628906 -0.6875 3.265625 -0.6875 Z M 3.3125 -6.453125 C 4.113281 -6.453125 4.789062 -6.179688 5.34375 -5.640625 C 5.90625 -5.109375 6.1875 -4.316406 6.1875 -3.265625 C 6.1875 -2.253906 5.941406 -1.414062 5.453125 -0.75 C 4.960938 -0.09375 4.203125 0.234375 3.171875 0.234375 C 2.304688 0.234375 1.617188 -0.0546875 1.109375 -0.640625 C 0.597656 -1.234375 0.34375 -2.019531 0.34375 -3 C 0.34375 -4.050781 0.609375 -4.890625 1.140625 -5.515625 C 1.679688 -6.140625 2.40625 -6.453125 3.3125 -6.453125 Z M 3.265625 -6.421875 Z M 3.265625 -6.421875 "/> -</symbol> -<symbol overflow="visible" id="glyph0-3"> -<path style="stroke:none;" d="M 1.4375 -3.0625 C 1.4375 -2.394531 1.578125 -1.832031 1.859375 -1.375 C 2.148438 -0.925781 2.609375 -0.703125 3.234375 -0.703125 C 3.722656 -0.703125 4.125 -0.910156 4.4375 -1.328125 C 4.757812 -1.742188 4.921875 -2.347656 4.921875 -3.140625 C 4.921875 -3.929688 4.753906 -4.515625 4.421875 -4.890625 C 4.097656 -5.273438 3.703125 -5.46875 3.234375 -5.46875 C 2.703125 -5.46875 2.269531 -5.265625 1.9375 -4.859375 C 1.601562 -4.453125 1.4375 -3.851562 1.4375 -3.0625 Z M 3.03125 -6.390625 C 3.507812 -6.390625 3.910156 -6.285156 4.234375 -6.078125 C 4.421875 -5.960938 4.632812 -5.757812 4.875 -5.46875 L 4.875 -8.640625 L 5.890625 -8.640625 L 5.890625 0 L 4.9375 0 L 4.9375 -0.875 C 4.695312 -0.488281 4.40625 -0.207031 4.0625 -0.03125 C 3.726562 0.132812 3.34375 0.21875 2.90625 0.21875 C 2.207031 0.21875 1.601562 -0.0703125 1.09375 -0.65625 C 0.582031 -1.25 0.328125 -2.03125 0.328125 -3 C 0.328125 -3.914062 0.5625 -4.707031 1.03125 -5.375 C 1.5 -6.050781 2.164062 -6.390625 3.03125 -6.390625 Z M 3.03125 -6.390625 "/> -</symbol> -<symbol overflow="visible" id="glyph0-4"> -<path style="stroke:none;" d="M 3.390625 -6.421875 C 3.835938 -6.421875 4.269531 -6.316406 4.6875 -6.109375 C 5.101562 -5.898438 5.421875 -5.628906 5.640625 -5.296875 C 5.847656 -4.972656 5.988281 -4.601562 6.0625 -4.1875 C 6.125 -3.894531 6.15625 -3.429688 6.15625 -2.796875 L 1.546875 -2.796875 C 1.566406 -2.160156 1.71875 -1.648438 2 -1.265625 C 2.28125 -0.878906 2.71875 -0.6875 3.3125 -0.6875 C 3.863281 -0.6875 4.300781 -0.867188 4.625 -1.234375 C 4.8125 -1.441406 4.945312 -1.6875 5.03125 -1.96875 L 6.0625 -1.96875 C 6.039062 -1.738281 5.953125 -1.484375 5.796875 -1.203125 C 5.640625 -0.921875 5.46875 -0.6875 5.28125 -0.5 C 4.957031 -0.1875 4.554688 0.0195312 4.078125 0.125 C 3.828125 0.1875 3.539062 0.21875 3.21875 0.21875 C 2.4375 0.21875 1.773438 -0.0625 1.234375 -0.625 C 0.691406 -1.195312 0.421875 -1.992188 0.421875 -3.015625 C 0.421875 -4.023438 0.691406 -4.84375 1.234375 -5.46875 C 1.785156 -6.101562 2.503906 -6.421875 3.390625 -6.421875 Z M 5.0625 -3.640625 C 5.019531 -4.097656 4.921875 -4.460938 4.765625 -4.734375 C 4.484375 -5.242188 4.003906 -5.5 3.328125 -5.5 C 2.835938 -5.5 2.425781 -5.320312 2.09375 -4.96875 C 1.769531 -4.625 1.597656 -4.179688 1.578125 -3.640625 Z M 3.28125 -6.421875 Z M 3.28125 -6.421875 "/> -</symbol> -<symbol overflow="visible" id="glyph0-5"> -<path style="stroke:none;" d="M 1.671875 -2.78125 C 1.703125 -2.289062 1.816406 -1.894531 2.015625 -1.59375 C 2.410156 -1.019531 3.09375 -0.734375 4.0625 -0.734375 C 4.5 -0.734375 4.898438 -0.796875 5.265625 -0.921875 C 5.960938 -1.160156 6.3125 -1.59375 6.3125 -2.21875 C 6.3125 -2.6875 6.160156 -3.019531 5.859375 -3.21875 C 5.566406 -3.414062 5.101562 -3.585938 4.46875 -3.734375 L 3.3125 -4 C 2.539062 -4.164062 2 -4.351562 1.6875 -4.5625 C 1.144531 -4.925781 0.875 -5.460938 0.875 -6.171875 C 0.875 -6.953125 1.140625 -7.585938 1.671875 -8.078125 C 2.203125 -8.578125 2.957031 -8.828125 3.9375 -8.828125 C 4.84375 -8.828125 5.609375 -8.609375 6.234375 -8.171875 C 6.867188 -7.734375 7.1875 -7.035156 7.1875 -6.078125 L 6.09375 -6.078125 C 6.03125 -6.546875 5.90625 -6.898438 5.71875 -7.140625 C 5.363281 -7.585938 4.757812 -7.8125 3.90625 -7.8125 C 3.21875 -7.8125 2.722656 -7.664062 2.421875 -7.375 C 2.117188 -7.09375 1.96875 -6.757812 1.96875 -6.375 C 1.96875 -5.957031 2.144531 -5.648438 2.5 -5.453125 C 2.726562 -5.328125 3.25 -5.171875 4.0625 -4.984375 L 5.28125 -4.703125 C 5.851562 -4.566406 6.300781 -4.382812 6.625 -4.15625 C 7.164062 -3.757812 7.4375 -3.175781 7.4375 -2.40625 C 7.4375 -1.457031 7.085938 -0.773438 6.390625 -0.359375 C 5.703125 0.046875 4.898438 0.25 3.984375 0.25 C 2.910156 0.25 2.070312 -0.0195312 1.46875 -0.5625 C 0.863281 -1.113281 0.566406 -1.851562 0.578125 -2.78125 Z M 4.03125 -8.84375 Z M 4.03125 -8.84375 "/> -</symbol> -<symbol overflow="visible" id="glyph0-6"> -<path style="stroke:none;" d="M 2.984375 -6.390625 C 3.484375 -6.390625 3.914062 -6.269531 4.28125 -6.03125 C 4.476562 -5.882812 4.679688 -5.679688 4.890625 -5.421875 L 4.890625 -6.21875 L 5.859375 -6.21875 L 5.859375 -0.515625 C 5.859375 0.285156 5.742188 0.914062 5.515625 1.375 C 5.078125 2.226562 4.25 2.65625 3.03125 2.65625 C 2.351562 2.65625 1.785156 2.503906 1.328125 2.203125 C 0.867188 1.898438 0.609375 1.425781 0.546875 0.78125 L 1.625 0.78125 C 1.675781 1.0625 1.773438 1.28125 1.921875 1.4375 C 2.160156 1.664062 2.535156 1.78125 3.046875 1.78125 C 3.859375 1.78125 4.390625 1.492188 4.640625 0.921875 C 4.785156 0.585938 4.851562 -0.0078125 4.84375 -0.875 C 4.632812 -0.550781 4.378906 -0.3125 4.078125 -0.15625 C 3.785156 0 3.394531 0.078125 2.90625 0.078125 C 2.226562 0.078125 1.632812 -0.160156 1.125 -0.640625 C 0.613281 -1.128906 0.359375 -1.929688 0.359375 -3.046875 C 0.359375 -4.097656 0.613281 -4.914062 1.125 -5.5 C 1.644531 -6.09375 2.265625 -6.390625 2.984375 -6.390625 Z M 4.890625 -3.171875 C 4.890625 -3.941406 4.726562 -4.515625 4.40625 -4.890625 C 4.082031 -5.265625 3.675781 -5.453125 3.1875 -5.453125 C 2.4375 -5.453125 1.925781 -5.101562 1.65625 -4.40625 C 1.507812 -4.039062 1.4375 -3.554688 1.4375 -2.953125 C 1.4375 -2.242188 1.578125 -1.703125 1.859375 -1.328125 C 2.148438 -0.960938 2.539062 -0.78125 3.03125 -0.78125 C 3.789062 -0.78125 4.320312 -1.125 4.625 -1.8125 C 4.800781 -2.195312 4.890625 -2.648438 4.890625 -3.171875 Z M 3.109375 -6.421875 Z M 3.109375 -6.421875 "/> -</symbol> -<symbol overflow="visible" id="glyph0-7"> -<path style="stroke:none;" d="M 0.78125 -6.28125 L 1.8125 -6.28125 L 1.8125 -5.390625 C 2.0625 -5.691406 2.289062 -5.914062 2.5 -6.0625 C 2.84375 -6.300781 3.238281 -6.421875 3.6875 -6.421875 C 4.1875 -6.421875 4.585938 -6.296875 4.890625 -6.046875 C 5.054688 -5.910156 5.210938 -5.703125 5.359375 -5.421875 C 5.585938 -5.765625 5.859375 -6.015625 6.171875 -6.171875 C 6.492188 -6.335938 6.851562 -6.421875 7.25 -6.421875 C 8.09375 -6.421875 8.664062 -6.113281 8.96875 -5.5 C 9.132812 -5.175781 9.21875 -4.734375 9.21875 -4.171875 L 9.21875 0 L 8.125 0 L 8.125 -4.359375 C 8.125 -4.773438 8.019531 -5.0625 7.8125 -5.21875 C 7.601562 -5.375 7.347656 -5.453125 7.046875 -5.453125 C 6.628906 -5.453125 6.269531 -5.3125 5.96875 -5.03125 C 5.675781 -4.757812 5.53125 -4.300781 5.53125 -3.65625 L 5.53125 0 L 4.453125 0 L 4.453125 -4.09375 C 4.453125 -4.519531 4.398438 -4.832031 4.296875 -5.03125 C 4.140625 -5.320312 3.84375 -5.46875 3.40625 -5.46875 C 3.007812 -5.46875 2.644531 -5.3125 2.3125 -5 C 1.988281 -4.695312 1.828125 -4.140625 1.828125 -3.328125 L 1.828125 0 L 0.78125 0 Z M 0.78125 -6.28125 "/> -</symbol> -<symbol overflow="visible" id="glyph0-8"> -<path style="stroke:none;" d="M 0.78125 -6.28125 L 1.78125 -6.28125 L 1.78125 -5.390625 C 2.070312 -5.753906 2.382812 -6.015625 2.71875 -6.171875 C 3.050781 -6.335938 3.421875 -6.421875 3.828125 -6.421875 C 4.710938 -6.421875 5.3125 -6.109375 5.625 -5.484375 C 5.800781 -5.140625 5.890625 -4.65625 5.890625 -4.03125 L 5.890625 0 L 4.8125 0 L 4.8125 -3.953125 C 4.8125 -4.335938 4.753906 -4.644531 4.640625 -4.875 C 4.453125 -5.269531 4.113281 -5.46875 3.625 -5.46875 C 3.375 -5.46875 3.171875 -5.441406 3.015625 -5.390625 C 2.722656 -5.304688 2.46875 -5.132812 2.25 -4.875 C 2.070312 -4.664062 1.957031 -4.453125 1.90625 -4.234375 C 1.851562 -4.015625 1.828125 -3.695312 1.828125 -3.28125 L 1.828125 0 L 0.78125 0 Z M 3.25 -6.421875 Z M 3.25 -6.421875 "/> -</symbol> -<symbol overflow="visible" id="glyph0-9"> -<path style="stroke:none;" d="M 0.984375 -8.03125 L 2.046875 -8.03125 L 2.046875 -6.28125 L 3.046875 -6.28125 L 3.046875 -5.421875 L 2.046875 -5.421875 L 2.046875 -1.3125 C 2.046875 -1.09375 2.125 -0.945312 2.28125 -0.875 C 2.351562 -0.832031 2.488281 -0.8125 2.6875 -0.8125 C 2.738281 -0.8125 2.789062 -0.8125 2.84375 -0.8125 C 2.90625 -0.820312 2.972656 -0.828125 3.046875 -0.828125 L 3.046875 0 C 2.929688 0.03125 2.804688 0.0507812 2.671875 0.0625 C 2.546875 0.0820312 2.40625 0.09375 2.25 0.09375 C 1.757812 0.09375 1.425781 -0.03125 1.25 -0.28125 C 1.070312 -0.53125 0.984375 -0.859375 0.984375 -1.265625 L 0.984375 -5.421875 L 0.140625 -5.421875 L 0.140625 -6.28125 L 0.984375 -6.28125 Z M 0.984375 -8.03125 "/> -</symbol> -</g> -</defs> -<g id="surface1"> -<path style="fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 14.625 31.5 L 96.625 31.5 L 96.625 81.5 L 14.625 81.5 Z M 14.625 31.5 " transform="matrix(1,0,0,1,-3,4)"/> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-1" x="38.28125" y="57.5"/> - <use xlink:href="#glyph0-2" x="46.94765" y="57.5"/> - <use xlink:href="#glyph0-3" x="53.62205" y="57.5"/> - <use xlink:href="#glyph0-4" x="60.29645" y="57.5"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-5" x="28.61035" y="71.5"/> - <use xlink:href="#glyph0-4" x="36.61435" y="71.5"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-6" x="43.28875" y="71.5"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-7" x="49.96315" y="71.5"/> - <use xlink:href="#glyph0-4" x="59.95915" y="71.5"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-8" x="66.63355" y="71.5"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-9" x="73.30795" y="71.5"/> -</g> -<path style="fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 14.625 125.5 L 96.625 125.5 L 96.625 175.5 L 14.625 175.5 Z M 14.625 125.5 " transform="matrix(1,0,0,1,-3,4)"/> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-1" x="38.28125" y="151.5"/> - <use xlink:href="#glyph0-2" x="46.94765" y="151.5"/> - <use xlink:href="#glyph0-3" x="53.62205" y="151.5"/> - <use xlink:href="#glyph0-4" x="60.29645" y="151.5"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-5" x="28.61035" y="165.5"/> - <use xlink:href="#glyph0-4" x="36.61435" y="165.5"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-6" x="43.28875" y="165.5"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-7" x="49.96315" y="165.5"/> - <use xlink:href="#glyph0-4" x="59.95915" y="165.5"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-8" x="66.63355" y="165.5"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-9" x="73.30795" y="165.5"/> -</g> -<path style="fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 144.5625 7.875 L 226.5625 7.875 L 226.5625 57.875 L 144.5625 57.875 Z M 144.5625 7.875 " transform="matrix(1,0,0,1,-3,4)"/> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-1" x="168.21875" y="33.875"/> - <use xlink:href="#glyph0-2" x="176.88515" y="33.875"/> - <use xlink:href="#glyph0-3" x="183.55955" y="33.875"/> - <use xlink:href="#glyph0-4" x="190.23395" y="33.875"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-5" x="158.54785" y="47.875"/> - <use xlink:href="#glyph0-4" x="166.55185" y="47.875"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-6" x="173.22625" y="47.875"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-7" x="179.90065" y="47.875"/> - <use xlink:href="#glyph0-4" x="189.89665" y="47.875"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-8" x="196.57105" y="47.875"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-9" x="203.24545" y="47.875"/> -</g> -<path style="fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 144.5625 142.875 L 226.5625 142.875 L 226.5625 192.875 L 144.5625 192.875 Z M 144.5625 142.875 " transform="matrix(1,0,0,1,-3,4)"/> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-1" x="168.21875" y="168.875"/> - <use xlink:href="#glyph0-2" x="176.88515" y="168.875"/> - <use xlink:href="#glyph0-3" x="183.55955" y="168.875"/> - <use xlink:href="#glyph0-4" x="190.23395" y="168.875"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-5" x="158.54785" y="182.875"/> - <use xlink:href="#glyph0-4" x="166.55185" y="182.875"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-6" x="173.22625" y="182.875"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-7" x="179.90065" y="182.875"/> - <use xlink:href="#glyph0-4" x="189.89665" y="182.875"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-8" x="196.57105" y="182.875"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-9" x="203.24545" y="182.875"/> -</g> -<path style="fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 96.625 58.5 L 131.273438 48.515625 " transform="matrix(1,0,0,1,-3,4)"/> -<path style="fill-rule:nonzero;fill:rgb(0%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 142.257812 45.351562 L 130.089844 44.398438 L 132.460938 52.636719 Z M 142.257812 45.351562 " transform="matrix(1,0,0,1,-3,4)"/> -<path style="fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 144.5625 75.375 L 226.5625 75.375 L 226.5625 125.375 L 144.5625 125.375 Z M 144.5625 75.375 " transform="matrix(1,0,0,1,-3,4)"/> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-1" x="168.21875" y="101.375"/> - <use xlink:href="#glyph0-2" x="176.88515" y="101.375"/> - <use xlink:href="#glyph0-3" x="183.55955" y="101.375"/> - <use xlink:href="#glyph0-4" x="190.23395" y="101.375"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-5" x="158.54785" y="115.375"/> - <use xlink:href="#glyph0-4" x="166.55185" y="115.375"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-6" x="173.22625" y="115.375"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-7" x="179.90065" y="115.375"/> - <use xlink:href="#glyph0-4" x="189.89665" y="115.375"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-8" x="196.57105" y="115.375"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-9" x="203.24545" y="115.375"/> -</g> -<path style="fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 97.121094 156.046875 L 130.855469 160.558594 " transform="matrix(1,0,0,1,-3,4)"/> -<path style="fill-rule:nonzero;fill:rgb(0%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 142.183594 162.074219 L 131.425781 156.3125 L 130.289062 164.808594 Z M 142.183594 162.074219 " transform="matrix(1,0,0,1,-3,4)"/> -<path style="fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 97.097656 70.503906 L 131.460938 82.105469 " transform="matrix(1,0,0,1,-3,4)"/> -<path style="fill-rule:nonzero;fill:rgb(0%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 142.289062 85.761719 L 132.832031 78.046875 L 130.089844 86.167969 Z M 142.289062 85.761719 " transform="matrix(1,0,0,1,-3,4)"/> -<path style="fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 274.5 31.5 L 356.5 31.5 L 356.5 81.5 L 274.5 81.5 Z M 274.5 31.5 " transform="matrix(1,0,0,1,-3,4)"/> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-1" x="298.15625" y="57.5"/> - <use xlink:href="#glyph0-2" x="306.82265" y="57.5"/> - <use xlink:href="#glyph0-3" x="313.49705" y="57.5"/> - <use xlink:href="#glyph0-4" x="320.17145" y="57.5"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-5" x="288.48535" y="71.5"/> - <use xlink:href="#glyph0-4" x="296.48935" y="71.5"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-6" x="303.16375" y="71.5"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-7" x="309.83815" y="71.5"/> - <use xlink:href="#glyph0-4" x="319.83415" y="71.5"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-8" x="326.50855" y="71.5"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-9" x="333.18295" y="71.5"/> -</g> -<path style="fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 227.046875 43.601562 L 261.597656 52.539062 " transform="matrix(1,0,0,1,-3,4)"/> -<path style="fill-rule:nonzero;fill:rgb(0%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 272.660156 55.398438 L 262.667969 48.390625 L 260.523438 56.6875 Z M 272.660156 55.398438 " transform="matrix(1,0,0,1,-3,4)"/> -<path style="fill-rule:nonzero;fill:rgb(100%,100%,100%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 274.5 125.5 L 356.5 125.5 L 356.5 175.5 L 274.5 175.5 Z M 274.5 125.5 " transform="matrix(1,0,0,1,-3,4)"/> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-1" x="298.15625" y="151.5"/> - <use xlink:href="#glyph0-2" x="306.82265" y="151.5"/> - <use xlink:href="#glyph0-3" x="313.49705" y="151.5"/> - <use xlink:href="#glyph0-4" x="320.17145" y="151.5"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-5" x="288.48535" y="165.5"/> - <use xlink:href="#glyph0-4" x="296.48935" y="165.5"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-6" x="303.16375" y="165.5"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-7" x="309.83815" y="165.5"/> - <use xlink:href="#glyph0-4" x="319.83415" y="165.5"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-8" x="326.50855" y="165.5"/> -</g> -<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> - <use xlink:href="#glyph0-9" x="333.18295" y="165.5"/> -</g> -<path style="fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 227.058594 162.328125 L 260.792969 157.816406 " transform="matrix(1,0,0,1,-3,4)"/> -<path style="fill-rule:nonzero;fill:rgb(0%,0%,0%);fill-opacity:1;stroke-width:1;stroke-linecap:butt;stroke-linejoin:miter;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 272.121094 156.300781 L 260.226562 153.566406 L 261.363281 162.0625 Z M 272.121094 156.300781 " transform="matrix(1,0,0,1,-3,4)"/> -</g> -</svg>
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/presentation/images/rbtree.svg Thu Aug 04 18:11:02 2016 +0900 @@ -0,0 +1,103 @@ +<?xml version="1.0" encoding="UTF-8"?> +<svg xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink" width="580pt" height="292pt" viewBox="0 0 580 292" version="1.1"> +<defs> +<g> +<symbol overflow="visible" id="glyph0-0"> +<path style="stroke:none;" d="M 6.546875 -10.65625 L 1.625 -10.65625 L 1.625 -0.75 L 6.546875 -0.75 Z M 7.359375 -11.390625 L 7.359375 -0.015625 L 0.8125 -0.015625 L 0.8125 -11.390625 Z M 7.359375 -11.390625 "/> +</symbol> +<symbol overflow="visible" id="glyph0-1"> +<path style="stroke:none;" d="M 8.140625 -9.984375 L 8.140625 -11.15625 L 0.796875 -11.15625 L 0.796875 -9.875 L 6.75 -9.875 C 6.15625 -9.238281 5.597656 -8.546875 5.078125 -7.796875 C 4.554688 -7.054688 4.097656 -6.265625 3.703125 -5.421875 C 3.316406 -4.585938 3 -3.710938 2.75 -2.796875 C 2.5 -1.890625 2.335938 -0.957031 2.265625 0 L 3.796875 0 C 3.847656 -0.882812 3.992188 -1.796875 4.234375 -2.734375 C 4.484375 -3.671875 4.800781 -4.582031 5.1875 -5.46875 C 5.582031 -6.351562 6.03125 -7.1875 6.53125 -7.96875 C 7.03125 -8.75 7.566406 -9.421875 8.140625 -9.984375 Z M 8.140625 -9.984375 "/> +</symbol> +<symbol overflow="visible" id="glyph0-2"> +<path style="stroke:none;" d="M 3.484375 -6.484375 L 3.484375 -5.328125 C 3.742188 -5.359375 4.015625 -5.375 4.296875 -5.375 C 4.640625 -5.375 4.957031 -5.328125 5.25 -5.234375 C 5.550781 -5.148438 5.804688 -5.015625 6.015625 -4.828125 C 6.234375 -4.640625 6.40625 -4.410156 6.53125 -4.140625 C 6.65625 -3.867188 6.71875 -3.554688 6.71875 -3.203125 C 6.71875 -2.859375 6.648438 -2.550781 6.515625 -2.28125 C 6.378906 -2.007812 6.195312 -1.78125 5.96875 -1.59375 C 5.75 -1.40625 5.488281 -1.257812 5.1875 -1.15625 C 4.894531 -1.0625 4.582031 -1.015625 4.25 -1.015625 C 3.476562 -1.015625 2.890625 -1.242188 2.484375 -1.703125 C 2.078125 -2.171875 1.863281 -2.769531 1.84375 -3.5 L 0.484375 -3.5 C 0.472656 -2.914062 0.550781 -2.394531 0.71875 -1.9375 C 0.894531 -1.476562 1.148438 -1.085938 1.484375 -0.765625 C 1.816406 -0.453125 2.21875 -0.21875 2.6875 -0.0625 C 3.15625 0.09375 3.675781 0.171875 4.25 0.171875 C 4.789062 0.171875 5.296875 0.101562 5.765625 -0.03125 C 6.242188 -0.175781 6.65625 -0.394531 7 -0.6875 C 7.351562 -0.976562 7.632812 -1.335938 7.84375 -1.765625 C 8.050781 -2.203125 8.15625 -2.703125 8.15625 -3.265625 C 8.15625 -3.941406 7.988281 -4.53125 7.65625 -5.03125 C 7.320312 -5.539062 6.804688 -5.867188 6.109375 -6.015625 L 6.109375 -6.046875 C 6.554688 -6.253906 6.929688 -6.550781 7.234375 -6.9375 C 7.535156 -7.332031 7.6875 -7.785156 7.6875 -8.296875 C 7.6875 -8.828125 7.597656 -9.28125 7.421875 -9.65625 C 7.242188 -10.039062 7 -10.351562 6.6875 -10.59375 C 6.375 -10.84375 6.003906 -11.03125 5.578125 -11.15625 C 5.160156 -11.28125 4.707031 -11.34375 4.21875 -11.34375 C 3.65625 -11.34375 3.15625 -11.25 2.71875 -11.0625 C 2.289062 -10.882812 1.929688 -10.632812 1.640625 -10.3125 C 1.359375 -10 1.140625 -9.617188 0.984375 -9.171875 C 0.828125 -8.722656 0.738281 -8.226562 0.71875 -7.6875 L 2.078125 -7.6875 C 2.078125 -8.007812 2.117188 -8.320312 2.203125 -8.625 C 2.296875 -8.925781 2.425781 -9.1875 2.59375 -9.40625 C 2.769531 -9.632812 2.992188 -9.8125 3.265625 -9.9375 C 3.546875 -10.070312 3.863281 -10.140625 4.21875 -10.140625 C 4.800781 -10.140625 5.28125 -9.988281 5.65625 -9.6875 C 6.039062 -9.382812 6.234375 -8.925781 6.234375 -8.3125 C 6.234375 -8.019531 6.175781 -7.753906 6.0625 -7.515625 C 5.945312 -7.285156 5.789062 -7.09375 5.59375 -6.9375 C 5.394531 -6.78125 5.164062 -6.660156 4.90625 -6.578125 C 4.644531 -6.503906 4.367188 -6.46875 4.078125 -6.46875 L 3.796875 -6.46875 C 3.742188 -6.46875 3.6875 -6.46875 3.625 -6.46875 C 3.582031 -6.46875 3.535156 -6.472656 3.484375 -6.484375 Z M 3.484375 -6.484375 "/> +</symbol> +<symbol overflow="visible" id="glyph0-3"> +<path style="stroke:none;" d="M 2.140625 -2.734375 L 0.78125 -2.734375 C 0.863281 -1.753906 1.21875 -1.023438 1.84375 -0.546875 C 2.476562 -0.0664062 3.269531 0.171875 4.21875 0.171875 C 5.59375 0.171875 6.59375 -0.347656 7.21875 -1.390625 C 7.84375 -2.441406 8.15625 -3.953125 8.15625 -5.921875 C 8.15625 -6.992188 8.050781 -7.878906 7.84375 -8.578125 C 7.632812 -9.273438 7.351562 -9.828125 7 -10.234375 C 6.65625 -10.640625 6.25 -10.925781 5.78125 -11.09375 C 5.3125 -11.257812 4.804688 -11.34375 4.265625 -11.34375 C 3.722656 -11.34375 3.222656 -11.25 2.765625 -11.0625 C 2.304688 -10.882812 1.910156 -10.632812 1.578125 -10.3125 C 1.253906 -9.988281 1 -9.597656 0.8125 -9.140625 C 0.632812 -8.691406 0.546875 -8.191406 0.546875 -7.640625 C 0.546875 -7.085938 0.625 -6.578125 0.78125 -6.109375 C 0.9375 -5.640625 1.164062 -5.238281 1.46875 -4.90625 C 1.769531 -4.582031 2.144531 -4.328125 2.59375 -4.140625 C 3.039062 -3.953125 3.550781 -3.859375 4.125 -3.859375 C 4.675781 -3.859375 5.1875 -4 5.65625 -4.28125 C 6.132812 -4.5625 6.5 -4.941406 6.75 -5.421875 L 6.78125 -5.390625 C 6.738281 -3.910156 6.507812 -2.8125 6.09375 -2.09375 C 5.675781 -1.375 5.050781 -1.015625 4.21875 -1.015625 C 3.675781 -1.015625 3.207031 -1.160156 2.8125 -1.453125 C 2.414062 -1.753906 2.191406 -2.179688 2.140625 -2.734375 Z M 6.546875 -7.546875 C 6.546875 -7.222656 6.488281 -6.90625 6.375 -6.59375 C 6.269531 -6.289062 6.113281 -6.023438 5.90625 -5.796875 C 5.707031 -5.566406 5.460938 -5.382812 5.171875 -5.25 C 4.890625 -5.125 4.570312 -5.0625 4.21875 -5.0625 C 3.894531 -5.0625 3.59375 -5.125 3.3125 -5.25 C 3.039062 -5.382812 2.804688 -5.5625 2.609375 -5.78125 C 2.410156 -6.007812 2.253906 -6.265625 2.140625 -6.546875 C 2.035156 -6.835938 1.984375 -7.140625 1.984375 -7.453125 C 1.984375 -7.804688 2.019531 -8.140625 2.09375 -8.453125 C 2.175781 -8.773438 2.304688 -9.0625 2.484375 -9.3125 C 2.660156 -9.570312 2.890625 -9.773438 3.171875 -9.921875 C 3.453125 -10.066406 3.796875 -10.140625 4.203125 -10.140625 C 4.585938 -10.140625 4.921875 -10.070312 5.203125 -9.9375 C 5.492188 -9.800781 5.738281 -9.613281 5.9375 -9.375 C 6.132812 -9.132812 6.285156 -8.859375 6.390625 -8.546875 C 6.492188 -8.234375 6.546875 -7.898438 6.546875 -7.546875 Z M 6.546875 -7.546875 "/> +</symbol> +<symbol overflow="visible" id="glyph0-4"> +<path style="stroke:none;" d="M 5.421875 -3.859375 L 1.609375 -3.859375 L 5.390625 -9.40625 L 5.421875 -9.40625 Z M 6.703125 -3.859375 L 6.703125 -11.34375 L 5.609375 -11.34375 L 0.453125 -3.96875 L 0.453125 -2.65625 L 5.421875 -2.65625 L 5.421875 0 L 6.703125 0 L 6.703125 -2.65625 L 8.234375 -2.65625 L 8.234375 -3.859375 Z M 6.703125 -3.859375 "/> +</symbol> +<symbol overflow="visible" id="glyph0-5"> +<path style="stroke:none;" d="M 5.703125 0 L 5.703125 -11.34375 L 4.65625 -11.34375 C 4.582031 -10.914062 4.441406 -10.5625 4.234375 -10.28125 C 4.035156 -10.007812 3.789062 -9.789062 3.5 -9.625 C 3.207031 -9.46875 2.878906 -9.359375 2.515625 -9.296875 C 2.148438 -9.242188 1.773438 -9.21875 1.390625 -9.21875 L 1.390625 -8.125 L 4.34375 -8.125 L 4.34375 0 Z M 5.703125 0 "/> +</symbol> +<symbol overflow="visible" id="glyph0-6"> +<path style="stroke:none;" d="M 0.703125 -7.328125 L 2.0625 -7.328125 C 2.050781 -7.671875 2.082031 -8.007812 2.15625 -8.34375 C 2.238281 -8.675781 2.367188 -8.972656 2.546875 -9.234375 C 2.734375 -9.503906 2.96875 -9.722656 3.25 -9.890625 C 3.539062 -10.054688 3.878906 -10.140625 4.265625 -10.140625 C 4.566406 -10.140625 4.847656 -10.09375 5.109375 -10 C 5.378906 -9.90625 5.613281 -9.765625 5.8125 -9.578125 C 6.007812 -9.398438 6.164062 -9.1875 6.28125 -8.9375 C 6.40625 -8.6875 6.46875 -8.40625 6.46875 -8.09375 C 6.46875 -7.695312 6.40625 -7.347656 6.28125 -7.046875 C 6.15625 -6.753906 5.972656 -6.476562 5.734375 -6.21875 C 5.492188 -5.96875 5.191406 -5.71875 4.828125 -5.46875 C 4.460938 -5.21875 4.039062 -4.941406 3.5625 -4.640625 C 3.164062 -4.398438 2.785156 -4.144531 2.421875 -3.875 C 2.066406 -3.613281 1.742188 -3.304688 1.453125 -2.953125 C 1.171875 -2.609375 0.9375 -2.195312 0.75 -1.71875 C 0.5625 -1.25 0.441406 -0.675781 0.390625 0 L 7.796875 0 L 7.796875 -1.203125 L 1.96875 -1.203125 C 2.03125 -1.554688 2.164062 -1.867188 2.375 -2.140625 C 2.582031 -2.410156 2.832031 -2.660156 3.125 -2.890625 C 3.414062 -3.128906 3.738281 -3.351562 4.09375 -3.5625 C 4.445312 -3.769531 4.800781 -3.976562 5.15625 -4.1875 C 5.507812 -4.414062 5.847656 -4.648438 6.171875 -4.890625 C 6.503906 -5.140625 6.796875 -5.414062 7.046875 -5.71875 C 7.304688 -6.019531 7.515625 -6.363281 7.671875 -6.75 C 7.828125 -7.132812 7.90625 -7.578125 7.90625 -8.078125 C 7.90625 -8.609375 7.8125 -9.078125 7.625 -9.484375 C 7.4375 -9.890625 7.179688 -10.226562 6.859375 -10.5 C 6.546875 -10.769531 6.171875 -10.976562 5.734375 -11.125 C 5.304688 -11.269531 4.847656 -11.34375 4.359375 -11.34375 C 3.753906 -11.34375 3.21875 -11.238281 2.75 -11.03125 C 2.28125 -10.832031 1.890625 -10.550781 1.578125 -10.1875 C 1.265625 -9.832031 1.03125 -9.410156 0.875 -8.921875 C 0.726562 -8.429688 0.671875 -7.898438 0.703125 -7.328125 Z M 0.703125 -7.328125 "/> +</symbol> +<symbol overflow="visible" id="glyph0-7"> +<path style="stroke:none;" d="M 2.484375 -8.40625 C 2.484375 -8.6875 2.535156 -8.929688 2.640625 -9.140625 C 2.742188 -9.359375 2.882812 -9.539062 3.0625 -9.6875 C 3.238281 -9.84375 3.445312 -9.957031 3.6875 -10.03125 C 3.9375 -10.101562 4.195312 -10.140625 4.46875 -10.140625 C 5.019531 -10.140625 5.472656 -9.992188 5.828125 -9.703125 C 6.191406 -9.410156 6.375 -8.976562 6.375 -8.40625 C 6.375 -7.820312 6.195312 -7.367188 5.84375 -7.046875 C 5.488281 -6.734375 5.039062 -6.578125 4.5 -6.578125 C 4.21875 -6.578125 3.953125 -6.613281 3.703125 -6.6875 C 3.460938 -6.757812 3.25 -6.867188 3.0625 -7.015625 C 2.882812 -7.171875 2.742188 -7.363281 2.640625 -7.59375 C 2.535156 -7.820312 2.484375 -8.09375 2.484375 -8.40625 Z M 1.046875 -8.453125 C 1.046875 -7.941406 1.1875 -7.46875 1.46875 -7.03125 C 1.757812 -6.601562 2.144531 -6.289062 2.625 -6.09375 C 1.976562 -5.875 1.484375 -5.515625 1.140625 -5.015625 C 0.804688 -4.515625 0.640625 -3.929688 0.640625 -3.265625 C 0.640625 -2.691406 0.738281 -2.1875 0.9375 -1.75 C 1.132812 -1.320312 1.40625 -0.960938 1.75 -0.671875 C 2.09375 -0.378906 2.5 -0.164062 2.96875 -0.03125 C 3.445312 0.101562 3.957031 0.171875 4.5 0.171875 C 5.019531 0.171875 5.507812 0.0976562 5.96875 -0.046875 C 6.425781 -0.191406 6.820312 -0.410156 7.15625 -0.703125 C 7.488281 -1.003906 7.753906 -1.367188 7.953125 -1.796875 C 8.148438 -2.222656 8.25 -2.710938 8.25 -3.265625 C 8.25 -3.960938 8.082031 -4.554688 7.75 -5.046875 C 7.425781 -5.535156 6.921875 -5.882812 6.234375 -6.09375 C 6.710938 -6.3125 7.09375 -6.628906 7.375 -7.046875 C 7.664062 -7.472656 7.8125 -7.941406 7.8125 -8.453125 C 7.8125 -8.804688 7.742188 -9.15625 7.609375 -9.5 C 7.484375 -9.851562 7.285156 -10.164062 7.015625 -10.4375 C 6.742188 -10.707031 6.390625 -10.925781 5.953125 -11.09375 C 5.515625 -11.257812 4.988281 -11.34375 4.375 -11.34375 C 3.9375 -11.34375 3.515625 -11.273438 3.109375 -11.140625 C 2.710938 -11.015625 2.359375 -10.828125 2.046875 -10.578125 C 1.734375 -10.335938 1.488281 -10.039062 1.3125 -9.6875 C 1.132812 -9.332031 1.046875 -8.921875 1.046875 -8.453125 Z M 2.078125 -3.203125 C 2.078125 -3.535156 2.140625 -3.832031 2.265625 -4.09375 C 2.390625 -4.363281 2.5625 -4.59375 2.78125 -4.78125 C 3 -4.976562 3.253906 -5.125 3.546875 -5.21875 C 3.835938 -5.320312 4.148438 -5.375 4.484375 -5.375 C 4.796875 -5.375 5.09375 -5.316406 5.375 -5.203125 C 5.664062 -5.097656 5.914062 -4.945312 6.125 -4.75 C 6.34375 -4.5625 6.507812 -4.335938 6.625 -4.078125 C 6.75 -3.816406 6.8125 -3.53125 6.8125 -3.21875 C 6.8125 -2.894531 6.753906 -2.597656 6.640625 -2.328125 C 6.535156 -2.066406 6.378906 -1.835938 6.171875 -1.640625 C 5.960938 -1.441406 5.71875 -1.285156 5.4375 -1.171875 C 5.15625 -1.066406 4.84375 -1.015625 4.5 -1.015625 C 3.789062 -1.015625 3.207031 -1.207031 2.75 -1.59375 C 2.300781 -1.976562 2.078125 -2.515625 2.078125 -3.203125 Z M 2.078125 -3.203125 "/> +</symbol> +<symbol overflow="visible" id="glyph0-8"> +<path style="stroke:none;" d="M 7.515625 -9.953125 L 7.515625 -11.15625 L 1.921875 -11.15625 L 0.859375 -5.265625 L 2.03125 -5.203125 C 2.300781 -5.523438 2.609375 -5.78125 2.953125 -5.96875 C 3.296875 -6.164062 3.691406 -6.265625 4.140625 -6.265625 C 4.523438 -6.265625 4.875 -6.203125 5.1875 -6.078125 C 5.5 -5.953125 5.769531 -5.773438 6 -5.546875 C 6.226562 -5.316406 6.398438 -5.039062 6.515625 -4.71875 C 6.640625 -4.40625 6.703125 -4.066406 6.703125 -3.703125 C 6.703125 -3.253906 6.632812 -2.859375 6.5 -2.515625 C 6.375 -2.179688 6.203125 -1.898438 5.984375 -1.671875 C 5.765625 -1.453125 5.507812 -1.285156 5.21875 -1.171875 C 4.925781 -1.066406 4.617188 -1.015625 4.296875 -1.015625 C 3.960938 -1.015625 3.648438 -1.0625 3.359375 -1.15625 C 3.078125 -1.257812 2.832031 -1.40625 2.625 -1.59375 C 2.414062 -1.78125 2.25 -2 2.125 -2.25 C 2.007812 -2.5 1.941406 -2.769531 1.921875 -3.0625 L 0.5625 -3.0625 C 0.570312 -2.539062 0.671875 -2.078125 0.859375 -1.671875 C 1.054688 -1.273438 1.316406 -0.9375 1.640625 -0.65625 C 1.972656 -0.382812 2.351562 -0.175781 2.78125 -0.03125 C 3.21875 0.101562 3.679688 0.171875 4.171875 0.171875 C 4.835938 0.171875 5.414062 0.0664062 5.90625 -0.140625 C 6.40625 -0.347656 6.816406 -0.625 7.140625 -0.96875 C 7.472656 -1.320312 7.722656 -1.722656 7.890625 -2.171875 C 8.054688 -2.628906 8.140625 -3.097656 8.140625 -3.578125 C 8.140625 -4.234375 8.039062 -4.800781 7.84375 -5.28125 C 7.65625 -5.769531 7.394531 -6.175781 7.0625 -6.5 C 6.738281 -6.820312 6.351562 -7.0625 5.90625 -7.21875 C 5.457031 -7.382812 4.984375 -7.46875 4.484375 -7.46875 C 4.097656 -7.46875 3.707031 -7.398438 3.3125 -7.265625 C 2.925781 -7.140625 2.613281 -6.9375 2.375 -6.65625 L 2.34375 -6.6875 L 2.9375 -9.953125 Z M 7.515625 -9.953125 "/> +</symbol> +<symbol overflow="visible" id="glyph0-9"> +<path style="stroke:none;" d="M 2.109375 -5.578125 C 2.109375 -5.859375 2.109375 -6.164062 2.109375 -6.5 C 2.117188 -6.84375 2.144531 -7.179688 2.1875 -7.515625 C 2.238281 -7.847656 2.3125 -8.171875 2.40625 -8.484375 C 2.5 -8.804688 2.632812 -9.085938 2.8125 -9.328125 C 2.988281 -9.578125 3.207031 -9.773438 3.46875 -9.921875 C 3.738281 -10.066406 4.066406 -10.140625 4.453125 -10.140625 C 4.835938 -10.140625 5.160156 -10.066406 5.421875 -9.921875 C 5.691406 -9.773438 5.914062 -9.578125 6.09375 -9.328125 C 6.269531 -9.085938 6.398438 -8.804688 6.484375 -8.484375 C 6.578125 -8.171875 6.644531 -7.847656 6.6875 -7.515625 C 6.738281 -7.179688 6.765625 -6.84375 6.765625 -6.5 C 6.773438 -6.164062 6.78125 -5.859375 6.78125 -5.578125 C 6.78125 -5.148438 6.765625 -4.671875 6.734375 -4.140625 C 6.710938 -3.617188 6.628906 -3.125 6.484375 -2.65625 C 6.335938 -2.195312 6.101562 -1.804688 5.78125 -1.484375 C 5.46875 -1.171875 5.023438 -1.015625 4.453125 -1.015625 C 3.867188 -1.015625 3.414062 -1.171875 3.09375 -1.484375 C 2.78125 -1.804688 2.550781 -2.195312 2.40625 -2.65625 C 2.257812 -3.125 2.171875 -3.617188 2.140625 -4.140625 C 2.117188 -4.671875 2.109375 -5.148438 2.109375 -5.578125 Z M 0.671875 -5.5625 C 0.671875 -5.144531 0.679688 -4.710938 0.703125 -4.265625 C 0.722656 -3.816406 0.773438 -3.378906 0.859375 -2.953125 C 0.941406 -2.523438 1.0625 -2.125 1.21875 -1.75 C 1.382812 -1.375 1.601562 -1.039062 1.875 -0.75 C 2.15625 -0.457031 2.503906 -0.226562 2.921875 -0.0625 C 3.347656 0.09375 3.859375 0.171875 4.453125 0.171875 C 5.046875 0.171875 5.550781 0.09375 5.96875 -0.0625 C 6.382812 -0.226562 6.726562 -0.457031 7 -0.75 C 7.28125 -1.039062 7.5 -1.375 7.65625 -1.75 C 7.820312 -2.125 7.945312 -2.523438 8.03125 -2.953125 C 8.113281 -3.378906 8.164062 -3.816406 8.1875 -4.265625 C 8.207031 -4.710938 8.21875 -5.144531 8.21875 -5.5625 C 8.21875 -5.976562 8.207031 -6.410156 8.1875 -6.859375 C 8.164062 -7.304688 8.113281 -7.742188 8.03125 -8.171875 C 7.945312 -8.597656 7.820312 -9.003906 7.65625 -9.390625 C 7.5 -9.773438 7.28125 -10.109375 7 -10.390625 C 6.726562 -10.679688 6.378906 -10.910156 5.953125 -11.078125 C 5.535156 -11.253906 5.035156 -11.34375 4.453125 -11.34375 C 3.859375 -11.34375 3.347656 -11.253906 2.921875 -11.078125 C 2.503906 -10.910156 2.15625 -10.679688 1.875 -10.390625 C 1.601562 -10.109375 1.382812 -9.773438 1.21875 -9.390625 C 1.0625 -9.003906 0.941406 -8.597656 0.859375 -8.171875 C 0.773438 -7.742188 0.722656 -7.304688 0.703125 -6.859375 C 0.679688 -6.410156 0.671875 -5.976562 0.671875 -5.5625 Z M 0.671875 -5.5625 "/> +</symbol> +</g> +</defs> +<g id="surface1"> +<path style="fill-rule:nonzero;fill:rgb(96.862793%,47.058105%,54.118347%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 199.09375 133.90625 C 209.636719 144.453125 209.636719 161.546875 199.09375 172.09375 C 188.546875 182.636719 171.453125 182.636719 160.90625 172.09375 C 150.363281 161.546875 150.363281 144.453125 160.90625 133.90625 C 171.453125 123.363281 188.546875 123.363281 199.09375 133.90625 " transform="matrix(1,0,0,1,-34,-34)"/> +<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> + <use xlink:href="#glyph0-1" x="137.104" y="125"/> + <use xlink:href="#glyph0-2" x="146" y="125"/> +</g> +<path style="fill-rule:nonzero;fill:rgb(96.862793%,47.058105%,54.118347%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 91.09375 268.90625 C 101.636719 279.453125 101.636719 296.546875 91.09375 307.09375 C 80.546875 317.636719 63.453125 317.636719 52.90625 307.09375 C 42.363281 296.546875 42.363281 279.453125 52.90625 268.90625 C 63.453125 258.363281 80.546875 258.363281 91.09375 268.90625 " transform="matrix(1,0,0,1,-34,-34)"/> +<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> + <use xlink:href="#glyph0-1" x="29.104" y="260"/> + <use xlink:href="#glyph0-3" x="38" y="260"/> +</g> +<path style="fill-rule:nonzero;fill:rgb(96.862793%,47.058105%,54.118347%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 451.09375 268.90625 C 461.636719 279.453125 461.636719 296.546875 451.09375 307.09375 C 440.546875 317.636719 423.453125 317.636719 412.90625 307.09375 C 402.363281 296.546875 402.363281 279.453125 412.90625 268.90625 C 423.453125 258.363281 440.546875 258.363281 451.09375 268.90625 " transform="matrix(1,0,0,1,-34,-34)"/> +<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> + <use xlink:href="#glyph0-4" x="389.104" y="260"/> + <use xlink:href="#glyph0-5" x="398" y="260"/> +</g> +<path style="fill-rule:nonzero;fill:rgb(96.862793%,47.058105%,54.118347%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 523.09375 268.90625 C 533.636719 279.453125 533.636719 296.546875 523.09375 307.09375 C 512.546875 317.636719 495.453125 317.636719 484.90625 307.09375 C 474.363281 296.546875 474.363281 279.453125 484.90625 268.90625 C 495.453125 258.363281 512.546875 258.363281 523.09375 268.90625 " transform="matrix(1,0,0,1,-34,-34)"/> +<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> + <use xlink:href="#glyph0-6" x="461.104" y="260"/> + <use xlink:href="#glyph0-4" x="470" y="260"/> +</g> +<path style="fill-rule:nonzero;fill:rgb(96.862793%,47.058105%,54.118347%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 595.09375 268.90625 C 605.636719 279.453125 605.636719 296.546875 595.09375 307.09375 C 584.546875 317.636719 567.453125 317.636719 556.90625 307.09375 C 546.363281 296.546875 546.363281 279.453125 556.90625 268.90625 C 567.453125 258.363281 584.546875 258.363281 595.09375 268.90625 " transform="matrix(1,0,0,1,-34,-34)"/> +<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> + <use xlink:href="#glyph0-7" x="537.552" y="260"/> +</g> +<path style="fill-rule:nonzero;fill:rgb(70.588684%,70.588684%,70.588684%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 127.09375 196.90625 C 137.636719 207.453125 137.636719 224.546875 127.09375 235.09375 C 116.546875 245.636719 99.453125 245.636719 88.90625 235.09375 C 78.363281 224.546875 78.363281 207.453125 88.90625 196.90625 C 99.453125 186.363281 116.546875 186.363281 127.09375 196.90625 " transform="matrix(1,0,0,1,-34,-34)"/> +<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> + <use xlink:href="#glyph0-1" x="65.104" y="188"/> + <use xlink:href="#glyph0-4" x="74" y="188"/> +</g> +<path style="fill-rule:nonzero;fill:rgb(70.588684%,70.588684%,70.588684%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 271.09375 196.90625 C 281.636719 207.453125 281.636719 224.546875 271.09375 235.09375 C 260.546875 245.636719 243.453125 245.636719 232.90625 235.09375 C 222.363281 224.546875 222.363281 207.453125 232.90625 196.90625 C 243.453125 186.363281 260.546875 186.363281 271.09375 196.90625 " transform="matrix(1,0,0,1,-34,-34)"/> +<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> + <use xlink:href="#glyph0-8" x="209.104" y="188"/> + <use xlink:href="#glyph0-3" x="218" y="188"/> +</g> +<path style="fill-rule:nonzero;fill:rgb(70.588684%,70.588684%,70.588684%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 415.09375 196.90625 C 425.636719 207.453125 425.636719 224.546875 415.09375 235.09375 C 404.546875 245.636719 387.453125 245.636719 376.90625 235.09375 C 366.363281 224.546875 366.363281 207.453125 376.90625 196.90625 C 387.453125 186.363281 404.546875 186.363281 415.09375 196.90625 " transform="matrix(1,0,0,1,-34,-34)"/> +<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> + <use xlink:href="#glyph0-4" x="353.104" y="188"/> + <use xlink:href="#glyph0-8" x="362" y="188"/> +</g> +<path style="fill-rule:nonzero;fill:rgb(70.588684%,70.588684%,70.588684%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 559.09375 196.90625 C 569.636719 207.453125 569.636719 224.546875 559.09375 235.09375 C 548.546875 245.636719 531.453125 245.636719 520.90625 235.09375 C 510.363281 224.546875 510.363281 207.453125 520.90625 196.90625 C 531.453125 186.363281 548.546875 186.363281 559.09375 196.90625 " transform="matrix(1,0,0,1,-34,-34)"/> +<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> + <use xlink:href="#glyph0-5" x="497.104" y="188"/> + <use xlink:href="#glyph0-9" x="506" y="188"/> +</g> +<path style="fill-rule:nonzero;fill:rgb(96.862793%,47.058105%,54.118347%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 487.09375 133.90625 C 497.636719 144.453125 497.636719 161.546875 487.09375 172.09375 C 476.546875 182.636719 459.453125 182.636719 448.90625 172.09375 C 438.363281 161.546875 438.363281 144.453125 448.90625 133.90625 C 459.453125 123.363281 476.546875 123.363281 487.09375 133.90625 " transform="matrix(1,0,0,1,-34,-34)"/> +<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> + <use xlink:href="#glyph0-2" x="425.104" y="125"/> + <use xlink:href="#glyph0-5" x="434" y="125"/> +</g> +<path style="fill-rule:nonzero;fill:rgb(70.588684%,70.588684%,70.588684%);fill-opacity:1;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 334.09375 52.90625 C 344.636719 63.453125 344.636719 80.546875 334.09375 91.09375 C 323.546875 101.636719 306.453125 101.636719 295.90625 91.09375 C 285.363281 80.546875 285.363281 63.453125 295.90625 52.90625 C 306.453125 42.363281 323.546875 42.363281 334.09375 52.90625 " transform="matrix(1,0,0,1,-34,-34)"/> +<g style="fill:rgb(0%,0%,0%);fill-opacity:1;"> + <use xlink:href="#glyph0-8" x="272.104" y="44"/> + <use xlink:href="#glyph0-9" x="281" y="44"/> +</g> +<path style="fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 291.84375 85.894531 L 203.15625 139.105469 " transform="matrix(1,0,0,1,-34,-34)"/> +<path style="fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 338.867188 84.636719 L 444.132812 140.363281 " transform="matrix(1,0,0,1,-34,-34)"/> +<path style="fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 159.679688 170.78125 L 128.320312 198.21875 " transform="matrix(1,0,0,1,-34,-34)"/> +<path style="fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 200.320312 170.78125 L 231.679688 198.21875 " transform="matrix(1,0,0,1,-34,-34)"/> +<path style="fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 95.921875 240.15625 L 84.078125 263.84375 " transform="matrix(1,0,0,1,-34,-34)"/> +<path style="fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 447.679688 170.78125 L 416.320312 198.21875 " transform="matrix(1,0,0,1,-34,-34)"/> +<path style="fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 488.320312 170.78125 L 519.679688 198.21875 " transform="matrix(1,0,0,1,-34,-34)"/> +<path style="fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 408.078125 240.15625 L 419.921875 263.84375 " transform="matrix(1,0,0,1,-34,-34)"/> +<path style="fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 527.921875 240.15625 L 516.078125 263.84375 " transform="matrix(1,0,0,1,-34,-34)"/> +<path style="fill:none;stroke-width:1;stroke-linecap:round;stroke-linejoin:round;stroke:rgb(0%,0%,0%);stroke-opacity:1;stroke-miterlimit:10;" d="M 552.078125 240.15625 L 563.921875 263.84375 " transform="matrix(1,0,0,1,-34,-34)"/> +</g> +</svg>
--- a/presentation/slide.md Wed Aug 03 17:53:25 2016 +0900 +++ b/presentation/slide.md Thu Aug 04 18:11:02 2016 +0900 @@ -17,6 +17,8 @@ * 検証の計算システムで実行する(メタ計算) * Java Path Finder, Valgrind * 大規模システムは実行できない + +# ソフトウェアの信頼性向上手法 * アルゴリズムの正しさを証明する * Agda, Coq, Idris といった証明支援系でプログラムを記述する * 極めて難しい @@ -77,6 +79,7 @@ # CbC のメタ計算の実際 * プログラムで使用する Data Segment は Meta Data Segment で全て定義されている + ``` union Data { struct Count { @@ -94,8 +97,10 @@ }; ``` +# CbC のメタ計算の実際 * Meta Code Segment では Data Segment は struct Data という形で一様に処理される * メタ計算と通常の計算は stub と meta によって接続される + ``` __code addTen_stub(struct Context* context) { goto addTen(context, context->data[Count]); @@ -117,6 +122,7 @@ } ``` +# CbC のメタ計算の実際 * デフォルトの meta * meta を変更することで平行計算や例外処理やソフトウェア検証を行なう @@ -185,63 +191,60 @@ * 赤ノードは2つの黒ノードを子として持つ(よって赤ノードが続くことはない) * ルートから最下位ノードへの経路に含まれる黒ノードの数はどの最下位ノードでも一定である * 仕様: 最も長い経路は最も短い経路の高々2倍に収まる -* todo 図を入れておこう -# Verification of Red-Black Tree -* どのような順番で要素が挿入されても常に仕様が満たされることを確認する -* 仕様を満たさないような挿入順番があればそれを表示する -* 木への挿入は有限の個数だけ行なわれる +{:width="35%"} # Verification Library Akasha * 本研究で作成した検証用メタ計算ライブラリ -* 実装コードの ``meta`` を上書きするだけで検証を行なうことができる -* 深さ優先探索で有限個の要素の挿入順番を総当たりで列挙 -* 挿入後の木はきちんとバランスしているかチェックする -* Meta Data Segment に挿入順番や実行履歴を記憶させる +* 実装コードの `meta` を上書きするだけで検証を行なうことができる +* どのような順番で要素が挿入されても常に仕様が満たされることを確認する +* 仕様を満たさない挿入順番があればそれを表示 + * 深さ優先探索で有限個の要素の挿入順番を総当たりで列挙 + * 挿入後の木はきちんとバランスしているかチェックする +* CbC のメタ計算 Akasha では要素数13個までチェックできた +* 実装にわざとバグを入れた場合にはバランスしていない入力例を返した # C Bounded Model Checker -* Carnegie Mellon University で開発されている ANSI-C の記号実行モデルチェッカ +* Carnegie Mellon University で開発されている記号実行モデルチェッカ + * C, C++, Java に対応 * CbC は `__code` を `void` に、`goto` を `return` に変えると C Syntaxになる -* Red-Black Tree を C に変換して検証 + * コードを C に変換して検証 * 挿入順番は非決定的な入力 `nondet_int` を使う +* 関数呼び出しやループは展開される + * 展開可能な最大数まで展開しても赤黒木の仕様を検証できず -# Result of Verification -* CbC のメタ計算 Akasha では要素数13個までチェックできた -* CBMC ではチェックできなかった - -| | akasha | CBMC | -|----------------------------------|:------:|:----:| -| 要素数1個までは仕様を保証 | 可 | 不可 | -| 要素数13個までは仕様を保証 | 可 | 不可 | -| 実装にバグを入れた際に反例を表示 | 可 | 不可 | - +# Conclusion +* 動作するプログラムの記述を変更せず検証を行なえた + * テストケースの自動生成+仕様の反例表示ができた +* CBMC では検証できない範囲の検証を行なうことができた + * 総当たりでチェックしているため # Comparison of tools -| | akasha | cbmc | unit test | Spin | 証明 | JavaPathFinder | valgrind | +| | akasha | cbmc | unit test | Spin | 証明 | JavaPathFinder | valgrind | |------------------------|:----------:|:--------------:|:----------:|:------------:|:------------:|:---------------:|:--------:| -| 検証用に実装の変更 | 必要なし | 必要なし | 必要なし | 必要 | 必要なし | 必要なし | 必要なし | +| 検証用に実装の変更 | 必要なし | 必要なし | 必要なし | 別に記述 | 別に記述 | 必要なし | 必要なし | | 検証用に記述する言語 | 実装と同じ | 実装とほぼ同じ | 実装と同じ | 実装と異なる | 実装と異なる | 必要なし | 必要なし | | 仕様の検証 | 可能 | 可能 | 不可能 | 可能 | 可能 | 不可能 | 不可能 | -| メモリリークなどの検出 | 今は不可能 | 不可能? | 不可能 | | | | 可能 | -| 状態の数え上げ | 可能 | 可能 | 不可能 | 可能 | ものによる | 可能 | | -| 反例の表示 | 可能 | 可能 | 不可能 | | | 不可能 | | +| メモリリークなどの検出 | 不可能 | 可能 | 不可能 | 不可能 | 不可能 | 不可能 | 可能 | +| 状態の数え上げ | 可能 | 可能 | 不可能 | 可能 | 不可能 | 可能 | 不可能 | +| 反例の表示 | 可能 | 可能 | 不可能 | 可能 | 不可能 | 不可能 | 不可能 | -# Conclusion and Future Works -* CBMC では検証できない範囲の検証を行なうことができた -* 動作するプログラムの記述を変更することなく検証を行なえた - * テストケースの自動生成+仕様の反例表示ができた -* 今後の課題 - * 挿入だけでなく削除を含む赤黒木の仕様検証 - * 状態の抽象化による探索の効率化 - * ポインタへの不正アクセス検出などの機能 - * 言語処理系に検証を行ないやすくする機構の導入 +# Future Works +* 挿入だけでなく削除を含む赤黒木の仕様検証 +* 状態の抽象化による探索の効率化 +* ポインタへの不正アクセス検出などの機能 +* 言語処理系に検証を行ないやすくする機構の導入 -# TODO: おまけ -* cbmc のバージョン、オプション -* rbtree の行数 -* 実行時間 +# CBMC Informations +* CBMC 5.4 +* 実行オプション + * cbmc --unwind 1 + * cbmc --depth 400 --property verifySpecification.assertion.1 +* 赤黒木のCbC実装 + * 赤黒木部分のみ: 330行 + * スタックやメモリのアロケータなどを含める: 640行