VilCretas package: educational resource through the use of Mathematica software in the field of
discrete mathematics

Prof. Enrique Vílchez Quesada, School of Informatics, National University of Costa Rica

Join the Conversation #WolframTechConf

Background

Objective of the paper

Show the overall operation of a package oriented to the commercial software Mathematica. Where:

Educational support to develop each of the main topics of discrete mathematics course.

Results of a research project.

The package VilCretas is conceived:

As a latent need in the chair of the course EIF-203.

A means to address discrete mathematics (which has become an obstacle more).

A resource that transforms arid issues in visualization and conceptual possibilities of autonomous construction.

VilCretas Package

Resource bounties

Serve sponsorship teaching discrete mathematics courses.

It incorporates user-friendly commands without having a deep knowledge of programming language.

Try a practical, effective and flexible employment.

It has tools for the study of real problems internally using data analysis features and geographical elements.

VilCretas Package

Add to Wolfram Mathematica program 195 functions in the following topics:

Recursion

Recurrence relations

Analysis algorithms

Binary relations

Graph theory

Trees theory

Machines and automatas finite state

Languages and grammars

Recursion

<<VilCretas`

SumaDigi: recursively sum of the digits of a natural number. The command provides the code that was programmed and can observe the values ​​returned in each iteration by using the options “code->True” and “steps->True”, respectively. Syntax: SumaDigi[n], or, SumaDigi[n, code->Valor, steps->Valor].

Example direct calculation.

SumaDigi[1980025487]

Example where the code is displayed.

SumaDigi[1980025487,code->True]

Example where shown step by step result.

SumaDigi[1980025487,steps->True]

Example where the code and recursive iterations are shown.

SumaDigi[1980025487,code->True,steps->True]

Sumatoria: automatically builds a recursive program to calculate a sum total entered by the user, the instruction also facilitates the step by step to a value of “n” (upper sum index) specified as a parameter calculation. Syntax: Sumatoria[suma, n], suma is a vector with three components in the following order: the lower the index, the higher rate (depending on “n”) and the internal expression of the sum (depending on “i”).

Example 1: (∑_(i=1)^(n-2))20

Sumatoria[{1,n-2,20},20]

Example 2: (∑_(i=3)^(n-4))(i/(i+1))

Sumatoria[{3,n-4,(i/(i+1))},10]

Recurrence relations

MetodoRRHL: it shows step by step implementation of one of the classic methods for solving a linear relationship homogeneous recurrence with constant coefficients, through the use of an equation called “characteristic equation”. Syntax: MetodoRRHL[Coefficients, Conditions, n, b] being “Coefficients” a vector of numerical coefficients in descending order, “Conditions” the initial conditions in ascending order, “n” parameter with which the solution of the recurrence relation is displayed and “b” the name of the system variable equations employing the procedure. By default, the domain is the set of natural numbers (excluding zero). The instruction integrates alternative “decimal->True” which displays the result with a decimal format and “inicio->Valor” that defines the first element (“Valor”) of the domain if you wish to change. Originally , “decimal” has the logical value “False” and “inicio->1”.

Example 1: (Subscript[a, n])=5(Subscript[a, n-1])+6(Subscript[a, n-2])+3(Subscript[a, n-3]), (Subscript[a, 1])=9, (Subscript[a, 2])=8, (Subscript[a, 3])=1

MetodoRRHL[{5,6,3},{9,8,1}, n,b,decimal->True]

Example 2: (Subscript[a, n])=11(Subscript[a, n-1])-49(Subscript[a, n-2])+113(Subscript[a, n-3])-142(Subscript[a, n-4])+92(Subscript[a, n-5])-24(Subscript[a, n-6]), (Subscript[a, 0])=9, (Subscript[a, 1])=8, (Subscript[a, 2])=1, (Subscript[a, 3])=1, (Subscript[a, 4])=1, (Subscript[a, 5])=1

MetodoRRHL[{11,-49,113,-142,92,-24},{9,8,1,1,1,1}, n,b,inicio->0]

Example 3: (Subscript[a, n])=21(Subscript[a, n-1])-192(Subscript[a, n-2])+1002(Subscript[a, n-3])-3285(Subscript[a, n-4])+7005(Subscript[a, n-5])-9698(Subscript[a, n-6])+8388(Subscript[a, n-7])-4104(Subscript[a, n-8])+864(Subscript[a, n-9]), (Subscript[a, 5])=1, (Subscript[a, 6])=-2, (Subscript[a, 7])=3, (Subscript[a, 8])=-4, (Subscript[a, 9])=5, (Subscript[a, 10])=-6, (Subscript[a, 11])=7, (Subscript[a, 12])=1, (Subscript[a, 13])=2

MetodoRRHL[{21, -192, 1002, -3285, 7005, -9698, 8388, -4104, 864}, {1, -2, 3, -4, 5, -6, 7, 1, 2},n ,b,inicio->5]

MetodoI: shows on a linear recurrence relation of order one, their evaluations in “k” iterations ascending or descending order, as chosen by the user. The command is a direct application of the method of solving recurrence relations called “iterative”. Syntax: MetodoI[Coefficients , k], or, MetodoI[Coefficients, k, ascendente->True, inicio->Valor] where “Coefficients” is a vector of dimension one or two containing a coefficient and/or inhomogeneous part (depending on “n”) as its last component, “ascendente->True” option that displays the results in ascending order (for default is low) and “inicio->Valor”, the index value begins with the initial condition. “MetodoI” accepts only integers.

Example 1: (Subscript[a, n])=2(n^2)(Subscript[a, n-1])+2n+(3^(n-1))

MetodoI[{2(n^2),2n+(3^(n-1))},5]

Example 2: (Subscript[a, n])=2(n^2)(Subscript[a, n-1])+2n+(3^(n-1))

MetodoI[{2(n^2),2n+(3^(n-1))},5, ascendente->True,inicio->3]

Analysis algorithms

CDFGraficaNA: receives two functions where one is in the notational order asymptotic (O large or omega) other visually representing notation. Syntax: CDFGraficaNA[L, cmin, cmax, graph] where “L” is a vector containing the functions (in terms of “n”), “cmin” (real greater than zero) and “cmax” (greater than or equal to 10 integer) correspond to the minimum and maximum values that it is possible to respectively to the constant “c” of the definition of asymptotic notation and “graph” (greater or equal to 10 integer) is a number that represents the likely variation on the x axis and the y axis. The command generates an animation.

Ejemplo 1: (n^5)+(n^2)-3(n^3)-n+6 = Θ((n^5))

CDFGraficaNA[{(n^5)+(n^2)-3(n^3)-n+6,(n^5)},0.001,10,1000]

Ejemplo 2: Ln(n!) = Θ(nLn(n))

CDFGraficaNA[{Log[n!],n Log[n]},0.001,10,1000]

CompLimit: compare at the limit two functions to determine if the first is “theta”, “Big O” or “Omega” of the second. Syntax: CompLimit[L] with “L” a vector containing the functions (in terms of “n” and “j”). If any contains a “j” command generates an animation by varying “j” of one to one thousand and showing the asymptotic behavior in each case.

Ejemplo 1: (Subscript[log, 3])(n)+c = Θ(ln(n))

CompLimit[{Log[3,n]+c,Log[n]}]

Ejemplo 2: (∑_(i=1)^n)(i^7) and 2(n^j)

CompLimit[{Sum[(i^7),{i,1,n}],2(n^j)}]

Binary relations

RelBin: explicitly returns the elements of a finite binary relation, given the condition that defines and sets on which it is built. Syntax: RelBin[Condition, A, B] with “Condition” a “string” that contains the condition of creating the binary relation (according to “a”, “b”) and “A” and “B” sets that they determine it.

Example 1

A={1,3,5,7};
B={2,4,6,8};
RelBin["GCD[a,b]==1",A,B]

Example 2

A=Table[i,{i,1,20}];
RelBin["a+(b^2)==12",A,A]

TipoRelacion: classifies a binary relations in reflexive, symmetric, antisymmetric, transitive, of equivalence and partial order, given their explicitly ordered pairs. Failure to comply with any of the properties returns a counterexample. Syntax: TipoRelacion[R, A], with “R” binary relation defined on the non-empty finite set “A”.

Example 1

A={1,2,3,4};
R={{1,1},{1,2},{1,3},{1,4},{2,1},{2,2},{2,3},{2,4},{3,1},{3,2},{3,3},{3,4},{4,1},{4,2},{4,3},{4,4}};
TipoRelacion[R,A]

Example 2

A={1,2,3,4};
R={{1,2},{1,1},{1,3},{1,4},{3,3},{3,2},{4,1},{4,2},{3,4}};
TipoRelacion[R,A]

Graph theory

Grafo: builds a graph through “Wolfram System” given its edges as an array of ordered pairs. The command has six options: “dirigido->True”, “vertices->List”, “dimensions3d->True”, “pesos->List”, “mostrarpesos->True” and “shape->True”. “dirigido” creates a digraph, “vertices” adds new vertexs by a list of nodes, “dimensions3d” presents the graph in three dimensions, “pesos” generates a weighted graph, “mostrarpesos” shows the weights on each of its edges and “shape” places the nodes of the graph on disks, or spheres depending on the size graphing. Syntax: Grafo[Edges], or Grafo[Edges, dirigido->True, vertices->List, dimensions3d->True, pesos->List, mostrarpesos->True, shape->True]. In the latter invocation, you may waive any of the options.

Example 1

A=Table[2i,{i,1,10}];
aristas=RelBin["a-b>=4",A,A]
Grafo[aristas,vertices->{a,b},dirigido->True]

Example 2

Grafo[AristasWolframSystemToCombinatorica[EdgeList[GrafoRandomConexo[15,50]]],dimensions3d->True,shape->True]

Example 3

Grafo[AristasWolframSystemToCombinatorica[EdgeList[GrafoRandomConexo[15,50]]],pesos->RandomInteger[{1,10},50],mostrarpesos->True,dimensions3d->True,shape->True]

AlDijkstra: executes step’s Dijkstra algorithm or the length of the shortest path on two different vertices “a” and “b” on a graph “G” connected and simple, created or not, through the package “Combinatorica”. Also returns a shortest path route. Syntax: AlDijkstra[G, a, b].

Example 1

grafo=System`Graph[{a\[UndirectedEdge]b,a\[UndirectedEdge]c,a\[UndirectedEdge]f,a\[UndirectedEdge]g,b\[UndirectedEdge]c,b\[UndirectedEdge]d,b\[UndirectedEdge]e,c\[UndirectedEdge]d,c\[UndirectedEdge]e,c\[UndirectedEdge]f,c\[UndirectedEdge]g,d\[UndirectedEdge]e,d\[UndirectedEdge]h,e\[UndirectedEdge]f,e\[UndirectedEdge]g,e\[UndirectedEdge]h,f\[UndirectedEdge]g,f\[UndirectedEdge]h,g\[UndirectedEdge]h},VertexLabels->"Name",ImagePadding->10];
grafo=Grafo[AristasWolframSystemToCombinatorica[EdgeList[grafo]],pesos->RandomReal[{1,10},Length[EdgeList[grafo]]],mostrarpesos->True]
AlDijkstra[grafo,a,h]

Example 2

grafo=GrafoCountryRegions["CostaRica"]
AlDijkstra[grafo,(Entity["Alajuela", Entity["City",{"Alajuela","Alajuela","CostaRica"}], "Entity[\"City\", {\"Alajuela\", \"Alajuela\", \"CostaRica\"}]", "city"]),(Entity["Cartago", Entity["City",{"Cartago","Cartago","CostaRica"}], "Entity[\"City\", {\"Cartago\", \"Cartago\", \"CostaRica\"}]", "city"])]

Trees theory

ArbolR: builds a tree through the “Wolfram System” given its edges as an array of ordered pairs and a vertex “root” for the root node of the tree. The command has four options: “dirigido->True”, “pesos->List”, “mostrarpesos->True” and “shape->form”. “dirigido” creates a tree with directed edges, “weights” generates a weighted tree, “mostrarpesos” shows the weights on each of its sides and “shape” provides a way to the vertices of the graph in any of the following: “circle”, “triangle”, “square”, “rectangle”, “pentagon”, “hexagon” and “octagon”. Syntax: ArbolR[Edges, Root], or ArbolR[Edges, Root, dirigido->True, pesos->List, mostrarpesos->True, shape->form]. In the latter invocation, you may waive any of the options.

Example 1

ArbolR[{{a,b},{a,c},{b,1},{b,2},{c,3},{c,4},{c,5},{4,d},{4,e},{5,f},{5,g},{5,h}},5]

Example 2

ArbolR[{{a,b},{a,c},{b,1},{b,2},{c,3},{c,4},{c,5},{4,d},{4,e},{5,f},{5,g},{5,h}},5,dirigido->True,pesos->RandomInteger[10,12],mostrarpesos->True,shape->"hexagono"]

CDFArbolesGeneradores: build an animation given the edges of a graph “G”, their weights and an order on its vertices, showing the application of the algorithms: “seek first width”, “seek first along”, “Prim” and “Kruskal” on “G”. Syntax: CDFArbolesGeneradores[sides, weights, order], being “sides” edges “G” given as ordered pairs, “weights” a vector of weights and “order” the ordered list of vertices, through which, procedures shall apply.

Example 1

CDFArbolesGeneradores[{{a,b},{a,c},{b,c},{b,d},{b,f},{c,d},{c,g},{c,e},{d,f},{d,g},{e,g},{f,g}},{5,10,15,5,6,7,12,30,9,8,20,14},{a,b,c,d,e,f,g}]

Conclusions

The package VilCretas customize a teaching effort in order to systematize computer assisted methodology.

Mathematica software endows a number of new commands for teaching purposes.

It is a resource available to other educational institutions.

Website and download support

Estructuras discretas con Mathematica: http://www.escinf.una.ac.cr/discretas/

Email: enrique.vilchez.quesada@una.cr

Thank you very much!