Wikipedia:School and university projects/Discrete and numerical mathematics/Learning plan/Sandbox
Minihackathons
editImportant: This section comes from Epistemowikia, although, to prevent confusion, the corresponding page has been whitened there, but you can see its history here.
Collatz conjecture
editExternal links
edit- Wikipedia contributors (2017) Collatz conjecture. Wikipedia, The Free Encyclopedia.
- Jeffrey C. Lagarias (v1:2003, v13:2011) The 3x+1 problem: An annotated bibliography (1963--1999) (sorted by author), arXiv:math/0309224v13 (math.NT)
- Jeffrey C. Lagarias (v1:2006, v6:2012) The 3x+1 Problem: An Annotated Bibliography, II (2000-2009), arXiv:math/0608208v6 (math.NT)
- Jeffrey C. Lagarias (2010) The Ultimate Challenge: The 3x+1 Problem. American Mathematical Society.
- Terry Tao (2011) The Collatz conjecture, Littlewood-Offord theory and powers of 2 and 3.
- John C. Turner: Paul S. Bruckman and Number Theory
- Amir Zoet, Johan Mogens Følsgaard, Rasmus Krisoffer Pedersen & Kasper Emil Dueholm Freiman (2015) On the strategies used to attack unsolved mathematical problems: a case study of the Collatz Conjecture, Roskilde University
- Collatz project at BOINC
Combinations with repetition
editDefinition
editA combination with repetition is a mapping from a set into , such that it assigns to every element in , the number of times that it occurs repeteadly (between and ), under the condition that their sum is .
Theorem
editThe total number of these combinations with repetition is:
An alternative notation for is .
Interpretations
edit- is the total number of selections, with repetition, of size , from a collection of objects.
- is the total number of multisets of elements from a set of elements.
- is the total number of ways of distributing objects among people.
- is the total number of integer solutions of the equation , where , for all .
- is the total number of ways of distributing indistinguishable objects into distinguishable bins, without any restrictions.
Theorem
editTrivially:
Derivative interpretations, I
edit- is the total number of subsets of elements from a set of elements.
- is the total number of paths on a grid of size .
- is the total number of finite sequences of ones and zeros, of length , that contains exactly ones and zeros.
Theorem
editTrivially:
Derivative interpretations, II
edit- is the total number of surjective mappings from a set of elements into a set of elements, , under the following conditions: elements of have the same image and elements of have the same image , where .
- is the total number of words of length in which it occurs only two letters and from a certain alphabet, albeit one occurs times and the other is repeated times.
Divisibility rule
editPotential residues
editGeneral divisibility rule (base )
editLet us consider , and , where . For all , let be the -potential residue of , modulo , that is, . Then: .
General divisibility rule (any base)
editLet us consider , and , where . For all , let be the -potential residue of , modulo , that is, . Then: .
Examples
editDivisibility by 2 in decimal (base 10)
editDivisibility by 3 in decimal (base 10)
editDivisibility by 7 in decimal (base 10)
editDivisibility by 11 in decimal (base 10)
editDivisibility by 101 in decimal (base 10)
editDivisibility by 2 in septenary (base 7)
editExternal links
edit- Robert T. Kurosaka (1986) Mahematical Recreations: Euclid's Algorithm (GCDs, LCMs and repeating decimals). In: Byte Magazine Volume 11 Number 01: Robotics (from https://archive.org/details/byte-magazine)
- Base-n Conversion Calculator
- The Dozenal Society of America
Inverting programs
editIntroduction
editHistory
editConcepts
editInverse programming gets information about any product available to the public. When we apply it to skip software protections is usually called Cracking. This engineering tries to take an element, a determinated product, to study its behaviour and composition and duply a program faithfuly.
This method is called that way because it proceeds in the inverse direction of the usual ingineering tasks, which consists in using technical data to elaborate a determinated product.
Generally if the product or another material which was submtted to inverse programming was obtained properly, then the process is legal. In the same way, generic products made with this technique can be legally distributed .
Samba is an example of this kind of engineering as it lets operative systems UNIX to share archives with Windows systems. Samba proyect had to investigate confidential information about technical aspects related with Windows O.S. WINE is another example, which works with Windows’ API and OpenOffice.org with Microsoft Office formats. It is also made to understand NTFS archive system structure so it can be possible to develop drivers to read and write upon itself. (mainly for GNU/Linux based systems).
Inverse programming is a resolution method. Applying it to something suppose to deepen in the study of its operation until we cand understand, modify and improve it.
Examples
editAn example of a program which is, at the same time its inverse program can be easyly implemented on Python. This example requires a password and a sentence to encrypt. Then it execute F[i] XOR C[i |L|]
(L = length(C)). If the operation is repeated on the result of F', F is obtained again.
text = input('Insert your sentence: ')
pword = input('Insert your password: ')
#At first sight, we change the strings to numbers
f_num = [ord(c) for c in text]
f_pass = [ord(c) for c in pword]
#Then, we apply the XOR operator to the data
f_res = [f_num[i] ^ f_pass[i % len(f_pass)] for i in range(len(f_num))]
result = ''.join([chr(n) for n in f_res])
print(result)
State of the art
editTheoretical applications
editPractical applications
editSee also
editNotes
editReferences
editBibliography
editExternal links
edit- Rustan, K., Leino, M., 1994, Computing permutation encodings, sección 2.4: «Inverting the program», California Institute of Technology, Pasadena, CA, USA, http://authors.library.caltech.edu/26789/1/postscript.pdf
Newton’s divided-difference interpolating polynomials
editExternal links
edit- Wikipedia contributors (2003ff.) Newton polynomial. Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/Newton_polynomial
- A. K. Dewdney on The Internet Archive
- Sequence solver, by AlteredQualia
- Leon Q. Brin (2016) Tea Time Numerical Analysis. Experiences in Mathematics, 2nd ed., CC BY-SA (§ 3.3)
- Steven C. Chapra & Raymond P. Canale (2010) Numerical methods for Engineers, McGraw-Hill Science/Engineering/Math, 6th ed., ISBN: 9780072918731, § 18.1, http://openlibrary.org/books/OL7305712M/Numerical_Methods_for_Engineers
- Steven C. Chapra & Raymond P. Canale (2007) Métodos numéricos para ingenieros, 5ª ed., § 18.1
- Steven C. Chapra & Raymond P. Canale (2010) Numerical methods for Engineers, 6th ed., § 18.1 / Steven C. Chapra & Raymond P. Canale (2007) Métodos numéricos para ingenieros, 5ª ed., § 18.1
- Walter Mora (2016) Introducción a los métodos numéricos (§ 2.6 ff.)
- Ibáñez Pérez, María José, Notas sobre Interpolación polinómica
Permutation generation methods
editListing in lexicographic order
editLet be a set of labels (letters, numbers...) for the objects, so distinguishables.
Lexicographic order:
Generating the next permutation in lexicographic order:
Note that:
If , then, .
For example, 1234576 follows to 1234567 in the sequence.
If , then,
- if , then,
- put at position , placing and at positions and in increasing order.
- if , then,
For example, 1234657 follows to 1234576 in the sequence.
Target:
Deduce the method for the general case.
See also
editMore
edit- Robert Sedgewick. Permutation Generation Methods. Computing Surveys, Vol 9, No 2, June 1977, pp. 137-164. http://homepage.math.uiowa.edu/~goodman/22m150.dir/2007/Permutation%20Generation%20Methods.pdf
- (Lexicographic algorithms: pp. 152ff.)
- Permutations: sequence A000142 at the OEIS.
RSA (cryptosystem)
editRSA (Rivest, Shamir, Adleman, 1978).
Explorations and tools
edit- Wolfram|Alpha
- factordb.com
- nettle
- ius/rsatool
- Understanding Common Factor Attacks: An RSA-Cracking Puzzle
- Understanding Common Factor Attacks (programming element)
- RSA Encryptor/Decryptor/Key Generator/Cracker
Programming
editSee also
edit- Ethical hacking (Wikipedia contributors, "Ethical hacking," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/Ethical_hacking) (En Epistemowikia, aquí)
- Integer factorization (Wikipedia contributors, "Integer factorization," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/Integer_factorization)
- RSA (cryptosystem) (Wikipedia contributors, "RSA (cryptosystem)," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/RSA_(cryptosystem))
- RSA Factoring Challenge (Wikipedia contributors, "RSA Factoring Challenge," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/RSA_Factoring_Challenge)
- Shor's algorithm (Wikipedia contributors, "Shor's algorithm," Wikipedia, The Free Encyclopedia, https://en.wikipedia.org/wiki/Shor's_algorithm)
External links
editTransitive closure of a binary relation
editIntroduction
editThere is an operation called closure in the binary relation. The idea of closure is to construct a new binary relation R’of R by adding some ordered pairs, which makes R' have some special properties such as reflexivity, symmetry and transitivity. Transitive closure is an important content of binary relations, which plays an important role in many fields such as the fundamentals of compiling, formal language and automaton[1].
History
editThe calculation of transitive closure of binary relation generally according to the definition. This method needs a number of compound set calculation, which is very prone to accidents. In 1962, Warshall proposed an efficient algorithm for computing transitive closures. The Warshall algorithm is simple and easy to implement in the computer, but it uses more time to calculate[2]. In recent years, many scholars proposed improved algorithms of transitive closure. There are algorithms simplify the calculation of the original transitive closure through reducing the number of relation compound[3-4]. Some algorithms use the relational matrices to calculate, also simplifies the calculation of transitive closure[5-6].
Concepts
editLet R be the relation on the nonempty set A, relation R’ of A is the transitive closure of R if and only if R’ satisfies: (1) R’ is transitive; (2) R⊆ R’; (3) For any transitive relation R’’ of A include R, there have R’⊆ R’’. We usually use t(R) to represent the transitive closure of R.
Examples
editState of the art
editThe transitive closure of a binary relation always exist, any binary relation can be extended until the extended relation is transitive. Besides the transitive closure that we denot here admits a very simple characterization
Theoretical applications
editPractical applications
editIn Nuutila (1995) we can find useful algoriths to calculate the transitive closure of a graph. Metods are in the worst case faster and reduce the problem to a "simple" matrix multiplication. The problem can be resolved by the Floyd-Warshall algorithm, or by extended search of width-first or depth-first search starting from each node in the graph. Recent research has explored a new efficient methods to calculate a transitive closure in distributes systems based on the MapReduce paradigm (Afrat et al.,2011)
- Floyd-Warshall algorithm:
It is a graph analysis algorithm to find the most efficient way to do weighted directed graphics. The Floyd-Warshall algorithm compares all possible paths across the graph between each pair of vertices. It does this by gradually improving an estimate of the shotest path between two vertices, until it is know that the estimate is optimal
See also
editNotes
editReferences
edit- [1]M Yang. Methods on The Transitive Closure of Binary Relation[J]. Network Security Technology and Application, 2006 (04):48-49+84.
- [2]X Wang. An Algorithm for the Transitive Closure Based on Setting Compound Position[J]. Journal of Suzhou University of Science & Technology, 2014 (3):43-45.
- [3]X Chen. On Transitivity and Transitive Closure for Binary Relation[J]. Mathematics in Practice and Theory, 2004,34(9):135-137
- [4]L Zhai, W Xie. The Computation on Transitive Closure[J]. Journal of Henan Institute of Education, 2005, 14(1):25-26.
- [5]X He, H Wang. A Method to Find the Transitive Closure of a Relation by Matrix[J]. Mathematics in Practice and Theory, 2005, 35(3):172-175.
- [6] F Su, A Resolution about the Transitive Closure Based on The Relation to the Matrix in Limited Collection[J]. Natural Science Journal of Harbin Normal University, 2007, 23(6):22-24
Bibliography
edit- Wikipedia contributors. "Transitive closure." Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia, 31 Jan. 2017. Web: https://en.wikipedia.org/w/index.php?title=Transitive_closure&oldid=762903855. 27 Feb. 2017.
External links
editUnion-find algorithms for sets
editIntroduction
editIn computer sciences, a union-find algorithm is a data structure that keeps trackof a set of elements partitioned into a number of disjoint subsets.
History
editUnion-find algorithms were first described by Bernard A. Galler and Michael J. Fischer in 1964. In 1973, their time complexity was bounded to , the iterated logarithm of , by Hopcraft and Ulllman. In 1975, Robert Tarjan was the first to prove the upper bound on the algorithm's time complexity. In 1989, Fredman and Saks showed that words must be accessed by union-find algorithms per operation.
Concepts
editExamples
editState of the art
editTheoretical applications
editPractical applications
editSee also
editNotes
editReferences
editBibliography
editDisjoint-set data structure, English Wikipedia
External links
edit- Robert Sedgewick, Princeton University, https://www.cs.princeton.edu/~rs/AlgsDS07/01UnionFind.pdf
References
edit- ^ [1]M Yang. Methods on The Transitive Closure of Binary Relation[J]. Network Security Technology and Application, 2006,(04):48-49+84.
See also
editSee also
edit
- Inner links
- Participants and major contributions of the university project, learning plan and sandbox of the learning plan
- Talk pages
- Talk page of the university project 'Discrete and numerical mathematics'
- Talk page of the page of the participants and major contributions of the university project 'Discrete and numerical mathematics'
- Talk page of the learning plan 'Discrete and numerical mathematics'
- Talk page of the sandbox of the learning plan 'Discrete and numerical mathematics'
- Interwiki links
- University project, participants and major contributions, learning plan and sandbox of the learning plan
- University project 'Matemática discreta y numérica' (equivalent university project on the Spanish Wikipedia)
- University project 'Matemática discreta y numérica': participant and major contributions (equivalent university project [partipants and major contributions page] on the Spanish Wikipedia)
- Learning plan 'Matemática discreta y numérica' (equivalent learning plan on the Spanish Wikipedia)
- Sandbox of the learning project 'Matemática discreta y numérica' (sandbox of the equivalent learning plan on the Spanish Wikipedia) (editathons are here)
- Talk pages
- Talk page of the university project 'Matemática discreta y numérica' (talk page of the equivalent university project on the Spanish Wikipedia)
- Talk page of the page of the participants and major contributions of the university project 'Matemática discreta y numérica' (talk page of the page of the participants and major contributions of the equivalent university project on the Spanish Wikipedia)
- Talk page of the learning plan 'Matemática discreta y numérica' (talk page of the equivalent learning plan on the Spanish Wikipedia)
- Talk page of the sandbox of the learning plan 'Matemática discreta y numérica' (talk page of the sandbox of the equivalent learning plan on the Spanish Wikipedia) (editathons, in Spanish, are here)