Jump to content

Wikipedia:School and university projects/Discrete and numerical mathematics/Learning plan/Sandbox

From Wikipedia, the free encyclopedia

Minihackathons

[edit]

Important: 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

[edit]
[edit]

Combinations with repetition

[edit]

Definition

[edit]

A 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

[edit]

The 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

[edit]

Trivially:

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

[edit]

Trivially:

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

[edit]

Potential residues

[edit]

General divisibility rule (base )

[edit]

Let us consider , and , where . For all , let be the -potential residue of , modulo , that is, . Then: .

General divisibility rule (any base)

[edit]

Let us consider , and , where . For all , let be the -potential residue of , modulo , that is, . Then: .

Examples

[edit]
Divisibility by 2 in decimal (base 10)
[edit]
Divisibility by 3 in decimal (base 10)
[edit]
Divisibility by 7 in decimal (base 10)
[edit]
Divisibility by 11 in decimal (base 10)
[edit]
Divisibility by 101 in decimal (base 10)
[edit]
Divisibility by 2 in septenary (base 7)
[edit]
[edit]

Inverting programs

[edit]

Introduction

[edit]

History

[edit]

Concepts

[edit]

Inverse 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

[edit]

An 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

[edit]

Theoretical applications

[edit]

Practical applications

[edit]

See also

[edit]

Notes

[edit]

References

[edit]

Bibliography

[edit]
[edit]

Newton’s divided-difference interpolating polynomials

[edit]
[edit]

Permutation generation methods

[edit]

Listing in lexicographic order

[edit]

Let 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.

For example, 1234657 follows to 1234576 in the sequence.

Target:

Deduce the method for the general case.

See also

[edit]

More

[edit]

RSA (cryptosystem)

[edit]

RSA (Rivest, Shamir, Adleman, 1978).

Explorations and tools

[edit]
Programming
[edit]

See also

[edit]
[edit]

Transitive closure of a binary relation

[edit]

Introduction

[edit]

There 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

[edit]

The 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

[edit]

Let 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

[edit]

State of the art

[edit]

The 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

[edit]

Practical applications

[edit]

In 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

[edit]

Notes

[edit]

References

[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]
[edit]

Union-find algorithms for sets

[edit]

Introduction

[edit]

In 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

[edit]

Union-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

[edit]

Examples

[edit]

State of the art

[edit]

Theoretical applications

[edit]

Practical applications

[edit]

See also

[edit]

Notes

[edit]

References

[edit]

Bibliography

[edit]

Disjoint-set data structure, English Wikipedia

[edit]

References

[edit]
  1. ^ [1]M Yang. Methods on The Transitive Closure of Binary Relation[J]. Network Security Technology and Application, 2006,(04):48-49+84.

See also

[edit]

See also

[edit]

Inner links
Interwiki links

To keep track, know more or write a comment

[edit]

About this page on the English Wikipedia

[edit]