Tools and Utilities for Knowledge Spaces
(Table of Contents)
Most programs listed below have been written by Cord Hockemeyer,
using
a lot of ideas of the
Knowledge space project group at the
Technical University of Braunschweig, especially from
Cornelia
Dowling, Katja
Baumunk, and
Rainer Kaluscha. The latter has also written parts of the programs
mentioned below. Recent changes and extensions were also inspired
by the group around Dietrich
Albert in Graz.
Files contain in general a data matrix preceded by two header lines
specifying the number of columns and the number of rows.
Knowledge space files
and answer pattern files have matrices
of 0's and 1's; basis files have matrices
of 0's, 1's, and 2's. In knowledge space files
a '1' means that the item described by the column is element of
the state described by the row. In answer
pattern files a '1'
describes a student (row) who has answered a question for an item
(column) correctly. In both file types we use a '0' otherwise. In
basis files we use a '1' to
denote that a basis element (row) is minimal for
an item (column), a '2' to show that the basis element just contains the
item and a '0' otherwise.
For each program there is a note stating the program language and - if
appropriate - other programs used. There are three languages used:
C, C++, and bash (the latter meaning shell
scripts using the bash). The scripts may be not portable. For the
shell scripts the C/C++ programs used within which have been
written especially for knowledge spaces
are also mentioned. Other programs used in the scripts, however, which
are part of the UNIX operating system and its standard utilities have
not been mentioned. Examples for the latter are sed, cut,
paste, [ef]grep, head, or tail.
Most of these programs should be available via ftp for members
of cooperating groups until July 1996.
As far as they are available, their documentation will
also be available via WWW. The documentation exists in several
formats, HTML, man-page, TeX, and Postscript. Links to already
existing parts of the documentation are placed in this text.
The manual for Ex3 students of Prof. Albert are a bit sloppy in
one point in order to keep things easier and better
understandable. The basis file
format differs from the format described in that manual. This
is due to the fact that within Ex3, bases are used only with the
constr program which does not necessarily need a
real basis file. If you work with other programs using the basis
you must follow the correct format.
(Table of Contents)
- basis: Computes the basis of a
knowledge structure. (C)
- constr: Constructs the knowledge
space for a given knowledge structure. The original structure
must be in ASCII space file format or in
basis file format.
The format of the space file (ASCII or binary) can be chosen via
command line options. (C)
(Table of Contents)
Comment: Rules is used here in the sense of surmise systems.
- rule-cnt: Just count the rules rejected by a basis. (C,
needs a lot of computing time if you have items with many clauses)
(Table of Contents)
- basis-print: Print a list of the basis elements as number
lists with one element per line. Items for which an element is minimal
are marked with an underscore. (C++, it is a good idea to
postprocess the list for including it into e.g. TeX-sources)
- equivalence: Compute and print classes of equivalent items
in a knowledge spaces given by its basis. (C)
- heights: Compute for each item its height within a
knowledge space defined as the minimal size of its clauses. (C)
(Table of Contents)
- basis-union: Compute
the basis of the union of two knowledge spaces given by their bases.
(bash, using the basis program
mentioned above)
- basis-section: Computes the basis of the section of two
knowledge spaces described by their bases. (C; still has limited
number of items and basis elements which are set at compiling time)
(Table of Contents)
- comp-rules: Compute different coefficients concerning
rules common to two knowledge spaces. (bash, using the
rule-cnt program mentioned above)
- sigma-distance: Compute for each item coefficients
concerning their clause sets in the surmise systems. (C)
(Table of Contents)
- s-closure: Compute the closure under intersection of a
knowledge space (given by its basis). The resulting spaces is also
given by its basis. (bash, using the constr
and the basis programs mentioned above)
- red-basis: Reduce a basis to a subset of items. (bash,
using the >basis program mentioned above)
- select-cols: Extension of the red-basis
program. Order of items in the destination basis can be freely
selected. Does not allow regions in the specification of the item
list. (bash, using the basis program mentioned
above)
- permute-basis: Permute the columns of a basis according to
a random permutation. (bash, using a small C-program called
permute for randomly choosing a
permutation)
- select: Select randomly a number of
knowledge states from a given knowledge space and store it in the
format of a knowledge space. (C)
(Table of Contents)
- diagonal-basis: Create a basis building a
diagonal matrix, i.e. a basis representing the knowledge space which
contains all subsets of the item set. (bash, using a C-program
called count; should be rewritten
in C for efficiency)
- mk-empty-space: Just the
complement program to
diagonal-basis. Write a spacefile which contains only the
empty set and the complete item set as its knowledge states.
(C)
- random-patterns: Create a family of randomly
selected subsets in binary
patternfile/spacefile format. (C)
(Table of Contents)
- dep-matrix: Show a surmise relation as
a matrix. (C, link to dep-pairs)
- dep-pairs: Show a surmise relation as
a list of pairs. (C, behaving depending on its name)
- dep-all: Show for each pair of items
whether or not it is contained in the surmise relation given. (C,
link to dep-pairs)
- comp-s-closure-rules: Compute different coefficients
concerning rules common to two knowledge spaces which must be closed under
intersection. (bash, using the
base-union, dep-pairs, and s-closure programs
mentioned above)
(Table of Contents)
- rule-errors: Compute for each pair in a surmise relation
the number of students' answer patterns which contradict the pair.
(bash, using the dep-pairs program mentioned above)
- all-rule-errors: Create for a given basis and a set of
answer patterns a table of all pairs of different items describing
whether or not the expert has accepted the pair as member of the
surmise relation and how many answer patterns contradict this pair.
(bash, using the dep-all program mentioned above)
- rule-error-table:
Print a table which shows for each pair of different items how many
answer patterns in a datafile contradict this pair and, for a list of
bases representing surmise relations, whether or not the pair is an
element of the surmise relations.
- quad-table: Print for a set of answer patterns and for
all 2-item-sets a table showing the frequencies of the four possible
0-1-pairs of managing the items. Each table is printed into an own
file. (bash, using just a small utility called
count which
prints the list of numbers from 1 to n)
- distance: Compute the frequency distribution
for the different possible distances between students' answer patterns
and the states of a knowledge space given in binary format. This
program was strongly influenced by a program named di.exe which
was originally written by Theo
Held. In the meantime, it has been extended to the computation of
several measures on the invalidity of items and prerequisite
relationships. (C)
- clause-val: This program computes a measure for
the validity of item-clause pairs in a given basis with respect to a
specified data set of answer patterns. (C)
Last Change: January 19, 1998
(Cord.Hockemeyer@kfunigraz.ac.at)