Esercizi di Linguaggi di Programmazione

A social network is a social structure made of individuals (or organizations) called nodes, which are tied (connected) by one or more specific types of interdependency, such as friendship, kinship, financial exchange, dislike, sexual relationships, or relationships of beliefs, knowledge or prestige.

A graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges.

The exercise consists of:

1. implementing the social network as a graph, i.e., to define the graph data structure with the operations you consider necessary to implement a social network
2. implementing an operation that visits in a convenient way all the elements of the graph
3. testing it against a dummy social network.

A monoid is an algebraic structure consisting of a set together with a single associative binary operation and an identity element. E.g., the set of booleans with the or operator is a monoid whose identity is false.

A group is an algebraic structure consisting of a set together with an operation that combines any two of its elements to form a third element. To qualify as a group, the set and the operation must satisfy a few conditions called group axioms, namely closure, associativity, identity and invertibility. E.g., the set Z (the integers with sign) with the + operator is a group but with the * is not since inverting the operation break the closure property.

A ring is an algebraic structure consisting of a set together with two binary operations (usually called addition and multiplication), where each operation combines two elements to form a third element. To qualify as a ring, the set together with its two operations must satisfy certain conditions, namely, the set must be an abelian (i.e., commutative) group under addition and a monoid under multiplication such that multiplication distributes over addition.

Write the Monoid, Group and Ring modules implementing the monoids, groups and rings algebraic structures respectively. Each module must be parametric on the algebraic sort, in the sense that the operations and the sets are not a priori defined and they should implement operations to check the properties characterizing the algebraic structure.

Test your implementation with the following examples (S is the set, add=additive operation, mul=multiplicative operation, i=identity):

Monoids

• S = {True, False} add = or i = False
• S = Zn={0,1,...,n-1} add = + where a+b=(a+b)%n i = 0

Groups

• S = {True, False}, add = or, i = False
• S = Z, add = +, i = 0
• S = Z4 = {0, 1, 2, 3}, add = * where a*b=(a*b)%4, i = 1
• S = {a}*, add: {a}*×{a}* --> {a}* where x1·x2 is x1 if #x1 > #x2, x2 otherwise, i = the empty string

Rings

• S = {0} add = + where 0+0=0 mul = * where 0*0=0 i = 0
• S = Z add = + mul = * i = 0
• S = Z4 = {0,1,2,3} add = + where a+b=(a+b)%4 mul = * where a*b=(a*b)%4 i = 0

Note property checks on infinite sets should be on a finite subset.

A KeWord In Context (KWIC) index is a simple index for a list of lines or titles. This assignment involves creating a KWIC index for an input list of titles stored in a file. Here's a small example. For the input file:

Casablanca

The Maltese Falcon

The Big Sleep

your program should produce the output:

3                              The Big Sleep    .

1                                  Casablanca   .

2                      The Maltese Falcon       .

2                              The Maltese Falcon

3                          The Big Sleep        .

As you can see, each title is listed for each word (omitting some minor words). The titles are arranged so that the word being indexed is shown in a column on the page. The position the lines have in the input file is shown on the left in the result.

Your solution should follow the following rules:

• The input is just a series of titles, one per line. Any leading or trailing spaces should be removed. Internal spaces should be retained (trimmed to one).
• A word is a maximal sequence of non-blank characters.
• The output line is at most 79 characters wide.
  • The number is 5 characters wide, right-justified.
  • There is a space after the number.
  • The key word starts at position 40 (numbering from 1).
  • If the part of the title left of the keyword is longer than 33, trim it (on the left) to 33.
  • If the part of the keyword and the part to the right is longer than 40, trim it to 40.
• Each title appears in the output once for each word that isn't minor. Any word of length two or less is minor, and and the words are minor words.
• If a title has a repeated word, it should be listed for each repetition.
• Sorting should be case-insensitive.

Goldbach's conjecture is one of the oldest unsolved problems in number theory and in all of mathematics. It states:

Every even integer greater than 2 is a Goldbach number, i.e., a number that can be expressed as the sum of two odd primes.

Expressing a given even number as a sum of two primes is called a Goldbach partition of the number. For example,

04 = 2 +  2           6 = 3 +  3           8 = 3 +  5

10 = 7 +  3          12 = 5 +  7          14 = 3 + 11

16 = 5 + 11          18 = 7 + 11          20 = 7 + 13

Write the following functions:

• goldbach(n) that returns a Goldbach partition for n
• goldbach_list(n,m) that returns a list of Goldbach partitions for the even numbers in the range (n,m).

You have to write a module Matrix to represent and manipulate integer matrices. The module should be parametric and will provide the operations of matrix equivalence, matrix copy, matrix addition, scalar-matrix multiplication, matrix-matrix multiplication, matrix transposition, and matrix norm -- the "size" of a matrix. Override the appropriate operators and raise the appropriate exceptions.

We first define these operations, and then give a skeleton of the Matrix module showing the signatures for all methods and constructors you must implement.

The operations

Let aᵢⱼ denotes the i,j-th element of matrix A, located at row i, column j. Using this notation, the matrix operations listed above may be defined precisely as follows:

• matrix equivalence A ≃ B where A in Ζᵐˣⁿ, B in Zp×q when m = p and n = q and bᵢⱼ = aᵢⱼ for i = 1,...,m j = 1,...,n;
• matrix copy B = A where A, B in Ζᵐˣⁿ (bᵢⱼ = aᵢⱼ for i = 1,...,m j = 1,...,n);
• matrix addition C = A + B where A, B, C in Ζᵐˣⁿ (cᵢⱼ = aᵢⱼ + bᵢⱼ for i = 1,...,m j = 1,...,n);
• scalar-matrix multiplication B = aA where A, B in Ζᵐˣⁿ, a in Z (bᵢⱼ = a·aᵢⱼ for i = 1,...,m j = 1,...,n);
• matrix-matrix multiplication C = A·B where A in Zᵐˣᵖ, B in Zᵖˣⁿp×n, C in Ζᵐˣⁿ (cᵢⱼ = Σₖ=1, ..., p aᵢₖ·bₖⱼ for i = 1,...,m j = 1,...,n);
• matrix transposition B = AT where A in Ζᵐˣⁿ, B in Zⁿˣᵐ (bⱼᵢ = aᵢⱼ for i = 1,...,m j = 1,...,n);
• matrix norm (matrix 1-norm) a = ‖A‖ where a in Z, A in Ζᵐˣⁿ (a = maxⱼ Σᵢ | aᵢⱼ | for i = 1,...,m j = 1, ..., n).

Note that in each case we state the proper matrix dimensions for the operation to be valid. For example, when multiplying two matrices A and B, the number of columns of A must match the number of rows of B.