commit d83820ba80452af68197128584d2f65ca7a732bc
parent 210d6a93e0b09bd9e718a76be1bd28b4078525e8
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date: Tue, 28 Jan 2025 06:08:30 -0600
Took notes on linear algebra, ToC, and comp. security
Diffstat:
9 files changed, 112 insertions(+), 17 deletions(-)
diff --git a/definitions/ComputerSecurity.md b/definitions/ComputerSecurity.md
@@ -68,3 +68,4 @@ Chapter 2: Introduction to Number Theory
2.2 - The Euclidean Algorithm
- [EuclideanAlgorithm](EuclideanAlgorithm.md)
+- [GCD](GCD.md)
diff --git a/definitions/EuclideanAlgorithm.md b/definitions/EuclideanAlgorithm.md
@@ -4,8 +4,35 @@ Ch 2.4
## Notes
-**Definition:** The Euclidean algorithm is an algorithm used to determine the greatest common factor of two numbers.
+**Definition:** The Euclidean algorithm is an algorithm used to determine the greatest common factor of two positive integers.
This is done as an alternative to the prime factoziation method which is too slow.
-To perform the Euclidean algorithm we
+The euclidean algorithm is shown below in python:
+
+```python
+
+# This has not been validated as working.
+
+def gcd(a,b):
+ if(a > b):
+ temp = b
+ b = a
+ a = temp
+
+ r = 1
+ while(r > 0):
+ coeff = int(a / b)
+ r = a - (coeff*b)
+ if r > 0:
+ a = b
+ b = r
+ return b
+
+print(gcd(10, 3))
+
+```
+
+# Extended Euclidean Algorithm
+
+**Definition:** Let a,b \in Z such that a,b > 0 & a >= b. Then there exists u,v \in Z such that gcd(a,b) = a * u + b * v.
diff --git a/definitions/FiniteStateAutomata.md b/definitions/FiniteStateAutomata.md
@@ -6,4 +6,4 @@
## Notes
-**Definition:**
+**Definition:** A finite state machine is a five tuple
diff --git a/definitions/LUDecomposition.md b/definitions/LUDecomposition.md
@@ -0,0 +1,15 @@
+# LU Decomposition (Lower-upper)
+
+**Source:** Strang Lectures
+
+**Lecture:** 4
+
+## Notes
+
+**Definition:** LU decomposition is the process of decomposing a matrix into an upper triangular matrix and a lower triangular matrix.
+
+LU decomposition is stated as the equation A = LU where L is the lower triangular and U is the upper triangular.
+
+Basically, L becomes the multipliers required to go from the upper triangular matrix to the original matrix A.
+
+LU decomposition is useful because subsequent solutions to linear equations and determinants are cheap to calculate.
diff --git a/definitions/Language.md b/definitions/Language.md
@@ -0,0 +1,36 @@
+# Language
+
+**Source:** Theory of Computation
+
+**Lecture:** 2
+
+## Notes
+
+**Definition:** A language (alphabet) is a finite set of symbols.
+
+Examples:
+
+\Sigma = {0,1}
+
+\Sigma = {a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z}
+
+#### Operations
+
+We can take the intersection and union of languages because they are simply sets.
+
+We can also concatenate two languages which is all combinations of elements of the first set followed by an element of the second set. Given this, we see languages are not commutative.
+
+Given that words can only happen once in a language, the concatenation of two languages is **at most** m * n in size where m is t he size of the first set and n is the size of the second set.
+
+### Strings
+
+#### Definition
+
+A string over an alphabet is a finite sequence (ordered) of symbols from the alphabet.
+
+w_1 = 01010010
+
+w_2 = abracadabra
+
+\epsilon = empty string
+
diff --git a/definitions/LinearAlgebra.md b/definitions/LinearAlgebra.md
@@ -54,6 +54,17 @@ Lecture 3:
- [Determinant](Determinant.md)
- [GaussianElimination](GaussianElimination.md)
+Lecture 4:
+
+- [Transpose](Transpose.md)
+- [InverseMatrix](InverseMatrix.md)
+- [LUDecomposition](LUDecomposition.md)
+- [PermutationMatrix](PermutationMatrix.md)
+
+Lecture 5:
+
+- Not started.
+
Khan Academy:
Khan Unit 1 (mostly):
diff --git a/definitions/PermutationMatrix.md b/definitions/PermutationMatrix.md
@@ -8,6 +8,9 @@
**Definition:** A permutation matrix is a matrix that when multiplied by exchanges rows of the other matrix.
+Permutation matrices are necessary for LU decomposition and Gaussian elimination because sometimes we find there are 0's in the pivot positions.
+
+Something interesting about permutation matrices is that P^-1 = P^T.
#### ROWS
diff --git a/definitions/RegularExpressions.md b/definitions/RegularExpressions.md
@@ -1,8 +1,8 @@
# Regular Expressions
-**Source:**
+**Source:** ToC Lecture
-**Chapter:**
+**Lecture:** 1
## Notes
diff --git a/definitions/TheoryOfComputation.md b/definitions/TheoryOfComputation.md
@@ -4,15 +4,17 @@
### Math 421 (Course Resources)
-- AutomataTheory
- - [FiniteStateAutomata](FiniteStateAutomata.md)
- - [DeterministicFiniteAutomata](DeterministicFiniteAutomata.md)
- - [RegularExpressions](RegularExpressions.md)
- - [RegularLanguages](RegularLanguages.md)
- - [NonDeterministicFiniteAutomata](NonDeterministicFiniteAutomata.md)
- - ContextFreeGrammars
- - Alphabet
- - PushdownAutomata
- - TuringMachines
-- ComputabilityTheory
-- ComplexityTheory
+Lecture 01/22
+
+- [FiniteStateAutomata](FiniteStateAutomata.md)
+- [RegularExpressions](RegularExpressions.md)
+
+Lecture 01/24
+
+- [Language](Language.md)
+
+From (Later) Lecture Slides
+
+- [RegularLanguages](RegularLanguages.md)
+- [DeterministicFiniteAutomata](DeterministicFiniteAutomata.md)
+- [NonDeterministicFiniteAutomata](NonDeterministicFiniteAutomata.md)
