From 397cefef7929e6cd49959db1d891f5b0654ebd05 Mon Sep 17 00:00:00 2001 From: bryan newbold Date: Tue, 10 Jun 2008 10:48:24 -0400 Subject: added a bunch of math content based on alaska notes. added more ethernet content --- Ethernet | 107 ++++++++++++++++++++++++++++++++++-- math/algebra | 71 ++++++++++++++++++++++++ math/books to read | 33 +++++++++++ math/good books | 5 ++ math/integers | 5 ++ math/logic | 18 ++++++ math/numbers | 54 ++++++++++++++++++ math/sets | 45 +++++++++++++-- restructured text cheatsheet | 127 ------------------------------------------- sheets/rst | 127 +++++++++++++++++++++++++++++++++++++++++++ 10 files changed, 456 insertions(+), 136 deletions(-) create mode 100644 math/algebra create mode 100644 math/books to read create mode 100644 math/good books create mode 100644 math/integers create mode 100644 math/logic create mode 100644 math/numbers delete mode 100644 restructured text cheatsheet create mode 100644 sheets/rst diff --git a/Ethernet b/Ethernet index 6b4be44..6240871 100644 --- a/Ethernet +++ b/Ethernet @@ -1,14 +1,15 @@ ======== Ethernet ======== +:Author: Bryan Newbold -.. warning:: Under progress! +.. contents:: History ======= -Bob Metcalfe first described the ethernet system in a memo while working at -the Xerox Palo Alto Research Center in 1973 ([oreilly]_). It was based on -the earlier *Aloha* system developed by Norman Abramson at the University of +Bob Metcalfe first described the ethernet system in a memo while working at the +Xerox Palo Alto Research Center in 1973 ([oreilly]_). It was based on the +earlier *Aloha* system developed by Norman Abramson at the University of Hawaii. *Aloha* was a radio network for inter-island communications. Structure @@ -34,16 +35,114 @@ Checksum 32 The preamble originally served as a "warm up" period for hardware to stabilize and prepare for the rest of the frame. + The last 8 bits are the preamble are a particular "start frame delimiter" + pattern to help hardware notice the beginning of signal transmission. + .. topic:: Source and Destination addresses Manufacturers are given a 24 bit id (first half), and are expected to ensure the uniqueness of the second half of each device's address. + If the first bit of the destination is high (1), the destination is + multicast; if low (0), then unicast. Under IEEE, if the second bit is high, + global administration rules should be followed, and if low, local + administration rules should be followed. + The IEEE-SA (Standards Association) delegates addresses. .. topic:: Checksum The checksum (or Frame Check Sequence) is a Cyclic Redundancy Checksum. +Inter-Frame Gap +~~~~~~~~~~~~~~~~~ +The Inter-Frame Gap (IFG) is a pause in between signal frames; it is 96 +bit-times long. + +.. _collision: + +Collisions +============= +Collision management is the heart of Ethernet; a collision occurs when two +devices try to transmit at the same time and their signals overlap and the +transmission is unreadable. This problem is made worse the further apart +stations are because it takes longer for signal fronts to propagate, so there +is a longer overlap period when the first device has started transmitting but +the second hasn't noticed and may start transmitting on its own. The network +size (in distance, not nodes) is determined by the maximum collision period +(also called slot time). This period is 512 bit-times, so usually the faster a +network is, the smaller it should be (in distance); at gigabit speeds the +slot is expanded, see Speeds_. + +Under Ethernet, if any device detects a collision, it sends out a 32 bit +"collision enforcement jam signal" to ensure that all devices notice the +collision. Then each device that wishes to transmit waits a random amount of +bit-times r before transmitting again. If there is another collision, a new +r is randomly chosen with a larger maximum; up to 15 retries are allowed before +the devices will give up and drop the frame. The constraints for the random +backoff time r are `$0\leq r \leq 2^k$`:latex:, where r is in bit times and +k is the number of retry attempts up to 10 (for 11th to 15th retries, use +k=10). + +Speeds +========= +At 10mb, bit time is 100ns (nano-seconds); at 100mb, 10ns; at 1gb, 1ns. + +At gigabit speeds, the slot time would limit network size to 20 meters, so +it gets padded with a null "carrier extension" signal to 4096 bits (512 bytes). +On high speed half-duplex gigabit links (which are rare!), frame bursting is +a technique to allow several small data frames to be transmitted at the same +time: one frame is sent regularly to capture the channel, then up to 65536 +bit times of short non-carrier extended (only IFG) frames are sent, then +a single last regular frame is sent. + +Phrases +========= + +Auto-negotiation + Optional protocol for direct links (eg, from switch to switch) to + determine network speed. Can be reinitiated by dropping and restarting + the link. + +802.1 + IEEE working group for higher level networking. + +802.2 + IEEE working group for "logical link control" (LLC), which is related + to the type/length frame field. + +802.3 + For _`CSMA/CD` LANs + +802.5 + For Token Ring LANs + +CSMA/CD Protocol + Stands for Carrier Sense Multiple Access/Collision Detect. The two main + implementations are DIX (DEC-Intel-Xerox) and IEEE. (Can't remember how + this works...) + +VLAN + Optional 4-byte field in between "source" and "type" fields. The first + two bytes are a valid type field; this increases the max length to + 1522 bits. Only used by switches. + +Channel Capture + This phenomena is a result of _collision management. After a few + sequential collisions, the device that ultimately transmits first gets + its backoff reset to zero, while all other devices retain a high backoff; + this means the first device is much much more likely to retransmit again + faster than any of the others, and if it has a lot of frames to send it + will dominate the carrier until it is done transmitting. + +Jabber + When a broken station/device keeps a carrier open and prevents other + transmissions. + +PAUSE + A PAUSE frame is a MAC control (higher level, type 0x8808) frame which + causes switches to stop for up to 65536 slot times to allow a switch or + station to clear its buffers. + .. [oreilly] `Ethernet: The Definitive Guide`:title:, by Charles Spurgeon. O'Reilly, 2000 diff --git a/math/algebra b/math/algebra new file mode 100644 index 0000000..b337a2e --- /dev/null +++ b/math/algebra @@ -0,0 +1,71 @@ +==================== +Algebra +==================== + +.. note:: Most of the definitions and notation in the section are based on [rudin]_ or [meserve]_ + +.. list-table:: Closure of binary operators on given sets of numbers + * Operation + - :latex:`$+$` + - :latex:`$\times$` + - :latex:`$-$` + - :latex:`$\divide$` + - :latex:`$^$` + - :latex:`$\sqrt{\text{ }}$` + * Positive Integers + - Y + - Y + - N + - N + - Y + - N + * Positive rationals + - Y + - Y + - N + - Y + - Y + - N + * Rationals (and zero) + - Y + - Y + - Y + - Y + - Y + - N + * Reals wrt positive integers + - Y + - Y + - Y + - Y + - Y + - Y + * Complex numbers + - Y + - Y + - Y + - Y + - Y + - Y + +Definitions +============= + +*involution* + to raise a number to a given power + +*evolution* + to take a given root of a number + +*associative* + :latex:`$(a+b)+c=a+(b+c)$` + +*comutative* + :latex:`$a+b=b+c$` + +*distributive* + :latex:`$(a+b)c=ac+bc$` + +.. [rudin] `Principles of Mathematical Analysis (3rd ed)`:title:, by Walter Rudin. McGraw-Hill, 1976 + +.. [meserve] `Fundamental Concepts of Algebra`:title:, by Bruce Meserve. diff --git a/math/books to read b/math/books to read new file mode 100644 index 0000000..ba75d8e --- /dev/null +++ b/math/books to read @@ -0,0 +1,33 @@ +=============================================== +Math books that look interesting +=============================================== + +`On formally undecidable propositions of Principa Mathematica and related systems`:title:, by Kurt Godel. + +`Computability and Unsolvability`:title:, by Martin Davis. + +`Mathematical Foundations of Information Theory`:title:, by A.I. Khinchin. + +`Calculus of Variations with Applications to Physics and Engineering`:title:, by Robert Weinstock. + +`Relativity, Thermodynamics, and Cosmology`:title:, by Richard Tolman. + +`Mathematics Applied to Continuum Mechanics`:title:, by Lee Segel. + +`Optimization Theory and Applications`:title:, by Donald Pierre. + +`The Variational Principles of Mechanics`:title:, by Cornelius Lanczos. + +`Tensor Analysis for Physicists`:title:, by J.A. Schonten. + +`Investigations on the Theory of Brownian Movement`:title:, by Albert Einstein. + +`Great Experiments in Physics`:title:, ed. by ???. + +`Curvature and Homology`:title:, by Samuel Goldberd. + +`The Philosophy of Mathematics`:title:, by Stephan Korner. + +`The Various and Ingenious Machines of Agostino Ramelli`:title:, by A. Ramelli (!). + +`Experiments in Topology`:title:, by Stephan Barr. diff --git a/math/good books b/math/good books new file mode 100644 index 0000000..bc3efe5 --- /dev/null +++ b/math/good books @@ -0,0 +1,5 @@ +========================================== +Recommended Math Reading +========================================== + +BLANK diff --git a/math/integers b/math/integers new file mode 100644 index 0000000..b946ce8 --- /dev/null +++ b/math/integers @@ -0,0 +1,5 @@ +==================== +Integers +==================== + +definition via Peano's Postulates: meserev 1-4 diff --git a/math/logic b/math/logic new file mode 100644 index 0000000..65ceba9 --- /dev/null +++ b/math/logic @@ -0,0 +1,18 @@ +======================= +Mathematical Logic +======================= + +.. note:: + Incomplete; in progress + +definition of induction: meserev 1-4 + +Proofs +=========== + +Indirect Proof: "reductio ad absurdum" + Show a paradox or impossibility in all cases by assuming the proposition + is false; then the proposition is true. + +Proof by elimination + Propose a complete set of propositions and remove all but one. diff --git a/math/numbers b/math/numbers new file mode 100644 index 0000000..541d174 --- /dev/null +++ b/math/numbers @@ -0,0 +1,54 @@ +======================== +Numbers +======================== + +.. note:: + incomplete + +.. note:: + Most of the definitions and notation in the section are based on [rudin]_ or [meserve]_ + +.. contents:: + +*incommensurable* + objects are incommensurable when their ratio isn't rational + +Real Numbers +================== +The *real numbers* are defined via Dedakind cuts in [rudin]_, or [meserve]_ +(1-12). + +Complex Numbers +================== +The *complex numbers* are constructed as an ordered pair of real numbers. + +Algebraic and Transendental Numbers +=============================================== +*Algebraic numbers* are solutions of polynomials, such as x in +:latex:`$a_0 x^n + a_1 x^{n-1} + a_2 x^{n-2} + ... a_n = 0$`, where all a are +real numbers. *Transcendental numbers* are not solutions to any such +polynomials. + +All real numbers are either algebraic or transcendental. + +Some algebraic numbers aren't real (such as :latex:`$i = \sqrt{-1}$`). They +can be rational or irrational. All transcendental numbers are irrational; +some are not real. + +Exersize: is the square root of 5 algebraic or transcendental? + +e +======== +:latex:`$e = \lim_{x \rightarrow 0} (1+x)^{\frac{1}{x}}$` + +Infinities +================== +*aleph-zero* (:latex:`$\aleph_0$`) is the countably infinite set. + +Positive integers, integers, and rational numbers are all countably infinite. + +It is unproven that the real numbers are *aleph-one* (:latex:`$\aleph_1$`). + +.. [rudin] `Principles of Mathematical Analysis (3rd ed)`:title:, by Walter Rudin. McGraw-Hill, 1976 + +.. [meserve] `Fundamental Concepts of Algebra`:title:, by Bruce Meserve. diff --git a/math/sets b/math/sets index 6d75a55..42eb831 100644 --- a/math/sets +++ b/math/sets @@ -2,11 +2,46 @@ Sets ==================== -.. warning:: Under progress! +.. note:: Most of the definitions and notation in the section are based on [rudin]_ or [meserve]_ -.. note:: Most of the definitions and notation in the section are based on [rudin]_ +Basics +============= +If every element :latex:`$a \in A$` is also :latex:`$a \in B$`, then we call +A a *subset* of B and write :latex:`$A \subset B$`. If there are elements of B +which are not elements of A, then we call A a *proper subset* of B. -If :latex:`$A \supset B$` and :latex:`$B \supset A$` we write :latex:`$A = B$`; otherwise :latex:`$A \neq B$`. +If :latex:`$A \supset B$` and :latex:`$B \supset A$` we write :latex:`$A = B$`; +otherwise :latex:`$A \neq B$`. -.. [rudin] `Principles of Mathematical Analysis (3rd ed)`:title:, by Walter Rudin. - McGraw-Hill, 1976 +The null or empty set, which has no elements, is a subset of all others. + +A relation on a space of sets S is something that can be definted as either +true or false (holding or not holding) for any binary pair in S. + +Binary Operators +================== +Binary operators defined on a set apply to any two elements of that set; order +may or may not be important. A set is *closed* with regards to a binary +operator if it contains the result of the binary operator. A set is *uniquely +defined* with regards to a binary operator if the result of the operator on two +elements of the set is unique from the results from all other pairs of +elements. + +Some equivalence relations are +:latex:`$\identity$` (NOTE: = with three lines) (*identity*); +:latex:`$\congruence$` (NOTE: = with tilde on top) (*congruence*; eg of +geometric figures); and +:latex:`$~$` (NOTE: tilde) (*similarity*; eg of geometric figures). + +Some properties of equivalence relations are + +*reflexive* + if :latex:`$a=a$` is true for all a +*symetric* + if :latex:`$a=b$` implies :latex:`$b=a$` +*transitive* + if :latex:`$a=b$` and :latex:`$b=c$` implies :latex:`$a=c$` + +.. [rudin] `Principles of Mathematical Analysis (3rd ed)`:title:, by Walter Rudin. McGraw-Hill, 1976 + +.. [meserve] `Fundamental Concepts of Algebra`:title:, by Bruce Meserve. diff --git a/restructured text cheatsheet b/restructured text cheatsheet deleted file mode 100644 index e105cba..0000000 --- a/restructured text cheatsheet +++ /dev/null @@ -1,127 +0,0 @@ -===================================================== - The reStructuredText_ Cheat Sheet: Syntax Reminders -===================================================== -:Info: See for introductory docs. -:Author: David Goodger -:Date: $Date: 2006-01-23 02:13:55 +0100 (Mon, 23 Jan 2006) $ -:Revision: $Revision: 4321 $ -:Description: This is a "docinfo block", or bibliographic field list - -Section Structure -================= -Section titles are underlined or overlined & underlined. - -Body Elements -============= -Grid table: - -+--------------------------------+-----------------------------------+ -| Paragraphs are flush-left, | Literal block, preceded by "::":: | -| separated by blank lines. | | -| | Indented | -| Block quotes are indented. | | -+--------------------------------+ or:: | -| >>> print 'Doctest block' | | -| Doctest block | > Quoted | -+--------------------------------+-----------------------------------+ -| | Line blocks preserve line breaks & indents. [new in 0.3.6] | -| | Useful for addresses, verse, and adornment-free lists; long | -| lines can be wrapped with continuation lines. | -+--------------------------------------------------------------------+ - -Simple tables: - -================ ============================================================ -List Type Examples -================ ============================================================ -Bullet list * items begin with "-", "+", or "*" -Enumerated list 1. items use any variation of "1.", "A)", and "(i)" - #. also auto-enumerated -Definition list Term is flush-left : optional classifier - Definition is indented, no blank line between -Field list :field name: field body -Option list -o at least 2 spaces between option & description -================ ============================================================ - -================ ============================================================ -Explicit Markup Examples (visible in the `text source `_) -================ ============================================================ -Footnote .. [1] Manually numbered or [#] auto-numbered - (even [#labelled]) or [*] auto-symbol -Citation .. [CIT2002] A citation. -Hyperlink Target .. _reStructuredText: http://docutils.sf.net/rst.html - .. _indirect target: reStructuredText_ - .. _internal target: -Anonymous Target __ http://docutils.sf.net/docs/ref/rst/restructuredtext.html -Directive ("::") .. image:: fig/biohazard.png -Substitution Def .. |substitution| replace:: like an inline directive -Comment .. is anything else -Empty Comment (".." on a line by itself, with blank lines before & after, - used to separate indentation contexts) -================ ============================================================ - -Inline Markup -============= -*emphasis*; **strong emphasis**; `interpreted text`; `interpreted text -with role`:emphasis:; ``inline literal text``; standalone hyperlink, -http://docutils.sourceforge.net; named reference, reStructuredText_; -`anonymous reference`__; footnote reference, [1]_; citation reference, -[CIT2002]_; |substitution|; _`inline internal target`. - -Directive Quick Reference -========================= -See for full info. - -================ ============================================================ -Directive Name Description (Docutils version added to, in [brackets]) -================ ============================================================ -attention Specific admonition; also "caution", "danger", - "error", "hint", "important", "note", "tip", "warning" -admonition Generic titled admonition: ``.. admonition:: By The Way`` -image ``.. image:: picture.png``; many options possible -figure Like "image", but with optional caption and legend -topic ``.. topic:: Title``; like a mini section -sidebar ``.. sidebar:: Title``; like a mini parallel document -parsed-literal A literal block with parsed inline markup -rubric ``.. rubric:: Informal Heading`` -epigraph Block quote with class="epigraph" -highlights Block quote with class="highlights" -pull-quote Block quote with class="pull-quote" -compound Compound paragraphs [0.3.6] -container Generic block-level container element [0.3.10] -table Create a titled table [0.3.1] -list-table Create a table from a uniform two-level bullet list [0.3.8] -csv-table Create a table from CSV data (requires Python 2.3+) [0.3.4] -contents Generate a table of contents -sectnum Automatically number sections, subsections, etc. -header, footer Create document decorations [0.3.8] -target-notes Create an explicit footnote for each external target -meta HTML-specific metadata -include Read an external reST file as if it were inline -raw Non-reST data passed untouched to the Writer -replace Replacement text for substitution definitions -unicode Unicode character code conversion for substitution defs -date Generates today's date; for substitution defs -class Set a "class" attribute on the next element -role Create a custom interpreted text role [0.3.2] -default-role Set the default interpreted text role [0.3.10] -title Set the metadata document title [0.3.10] -================ ============================================================ - -Interpreted Text Role Quick Reference -===================================== -See for full info. - -================ ============================================================ -Role Name Description -================ ============================================================ -emphasis Equivalent to *emphasis* -literal Equivalent to ``literal`` but processes backslash escapes -PEP Reference to a numbered Python Enhancement Proposal -RFC Reference to a numbered Internet Request For Comments -raw For non-reST data; cannot be used directly (see docs) [0.3.6] -strong Equivalent to **strong** -sub Subscript -sup Superscript -title Title reference (book, etc.); standard default role -================ ============================================================ diff --git a/sheets/rst b/sheets/rst new file mode 100644 index 0000000..e105cba --- /dev/null +++ b/sheets/rst @@ -0,0 +1,127 @@ +===================================================== + The reStructuredText_ Cheat Sheet: Syntax Reminders +===================================================== +:Info: See for introductory docs. +:Author: David Goodger +:Date: $Date: 2006-01-23 02:13:55 +0100 (Mon, 23 Jan 2006) $ +:Revision: $Revision: 4321 $ +:Description: This is a "docinfo block", or bibliographic field list + +Section Structure +================= +Section titles are underlined or overlined & underlined. + +Body Elements +============= +Grid table: + ++--------------------------------+-----------------------------------+ +| Paragraphs are flush-left, | Literal block, preceded by "::":: | +| separated by blank lines. | | +| | Indented | +| Block quotes are indented. | | ++--------------------------------+ or:: | +| >>> print 'Doctest block' | | +| Doctest block | > Quoted | ++--------------------------------+-----------------------------------+ +| | Line blocks preserve line breaks & indents. [new in 0.3.6] | +| | Useful for addresses, verse, and adornment-free lists; long | +| lines can be wrapped with continuation lines. | ++--------------------------------------------------------------------+ + +Simple tables: + +================ ============================================================ +List Type Examples +================ ============================================================ +Bullet list * items begin with "-", "+", or "*" +Enumerated list 1. items use any variation of "1.", "A)", and "(i)" + #. also auto-enumerated +Definition list Term is flush-left : optional classifier + Definition is indented, no blank line between +Field list :field name: field body +Option list -o at least 2 spaces between option & description +================ ============================================================ + +================ ============================================================ +Explicit Markup Examples (visible in the `text source `_) +================ ============================================================ +Footnote .. [1] Manually numbered or [#] auto-numbered + (even [#labelled]) or [*] auto-symbol +Citation .. [CIT2002] A citation. +Hyperlink Target .. _reStructuredText: http://docutils.sf.net/rst.html + .. _indirect target: reStructuredText_ + .. _internal target: +Anonymous Target __ http://docutils.sf.net/docs/ref/rst/restructuredtext.html +Directive ("::") .. image:: fig/biohazard.png +Substitution Def .. |substitution| replace:: like an inline directive +Comment .. is anything else +Empty Comment (".." on a line by itself, with blank lines before & after, + used to separate indentation contexts) +================ ============================================================ + +Inline Markup +============= +*emphasis*; **strong emphasis**; `interpreted text`; `interpreted text +with role`:emphasis:; ``inline literal text``; standalone hyperlink, +http://docutils.sourceforge.net; named reference, reStructuredText_; +`anonymous reference`__; footnote reference, [1]_; citation reference, +[CIT2002]_; |substitution|; _`inline internal target`. + +Directive Quick Reference +========================= +See for full info. + +================ ============================================================ +Directive Name Description (Docutils version added to, in [brackets]) +================ ============================================================ +attention Specific admonition; also "caution", "danger", + "error", "hint", "important", "note", "tip", "warning" +admonition Generic titled admonition: ``.. admonition:: By The Way`` +image ``.. image:: picture.png``; many options possible +figure Like "image", but with optional caption and legend +topic ``.. topic:: Title``; like a mini section +sidebar ``.. sidebar:: Title``; like a mini parallel document +parsed-literal A literal block with parsed inline markup +rubric ``.. rubric:: Informal Heading`` +epigraph Block quote with class="epigraph" +highlights Block quote with class="highlights" +pull-quote Block quote with class="pull-quote" +compound Compound paragraphs [0.3.6] +container Generic block-level container element [0.3.10] +table Create a titled table [0.3.1] +list-table Create a table from a uniform two-level bullet list [0.3.8] +csv-table Create a table from CSV data (requires Python 2.3+) [0.3.4] +contents Generate a table of contents +sectnum Automatically number sections, subsections, etc. +header, footer Create document decorations [0.3.8] +target-notes Create an explicit footnote for each external target +meta HTML-specific metadata +include Read an external reST file as if it were inline +raw Non-reST data passed untouched to the Writer +replace Replacement text for substitution definitions +unicode Unicode character code conversion for substitution defs +date Generates today's date; for substitution defs +class Set a "class" attribute on the next element +role Create a custom interpreted text role [0.3.2] +default-role Set the default interpreted text role [0.3.10] +title Set the metadata document title [0.3.10] +================ ============================================================ + +Interpreted Text Role Quick Reference +===================================== +See for full info. + +================ ============================================================ +Role Name Description +================ ============================================================ +emphasis Equivalent to *emphasis* +literal Equivalent to ``literal`` but processes backslash escapes +PEP Reference to a numbered Python Enhancement Proposal +RFC Reference to a numbered Internet Request For Comments +raw For non-reST data; cannot be used directly (see docs) [0.3.6] +strong Equivalent to **strong** +sub Subscript +sup Superscript +title Title reference (book, etc.); standard default role +================ ============================================================ -- cgit v1.2.3