summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorbryan newbold <bnewbold@snark.mit.edu>2008-06-10 10:48:24 -0400
committerbryan newbold <bnewbold@snark.mit.edu>2008-06-10 10:48:24 -0400
commit397cefef7929e6cd49959db1d891f5b0654ebd05 (patch)
treeec197475d62c9149288863f89c97e26131959815
parent80b4628e5a94dfedd2c6ee91bdb608c531a78598 (diff)
downloadknowledge-397cefef7929e6cd49959db1d891f5b0654ebd05.tar.gz
knowledge-397cefef7929e6cd49959db1d891f5b0654ebd05.zip
added a bunch of math content based on alaska notes. added more ethernet content
-rw-r--r--Ethernet107
-rw-r--r--math/algebra71
-rw-r--r--math/books to read33
-rw-r--r--math/good books5
-rw-r--r--math/integers5
-rw-r--r--math/logic18
-rw-r--r--math/numbers54
-rw-r--r--math/sets45
-rw-r--r--sheets/rst (renamed from restructured text cheatsheet)0
9 files changed, 329 insertions, 9 deletions
diff --git a/Ethernet b/Ethernet
index 6b4be44..6240871 100644
--- a/Ethernet
+++ b/Ethernet
@@ -1,14 +1,15 @@
========
Ethernet
========
+:Author: Bryan Newbold <bnewbold@mit.edu>
-.. 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/sheets/rst
index e105cba..e105cba 100644
--- a/restructured text cheatsheet
+++ b/sheets/rst