Genericity - Revision history

Weihe: /* Comparison */

2015-05-21T12:45:16Z

Comparison

← Older revision		Revision as of 12:45, 21 May 2015
Line 15:		Line 15:

	===Remark===		===Remark===
	Note that <math>c(x,y)=0</math> does '''not''' imply <math>x=y</math>. If <math>c(x,y)=0</math> actually implies <math>x=y</math> for all <math>x,y</math>, such a binary relation is usually called a '''total''' or '''linear order''' - as opposed to '''partial orders''', in which ~~pairs of elements may be~~ incomparable.		Note that <math>c(x,y)=0</math> does '''not''' imply <math>x=y</math>. If <math>c(x,y)=0</math> actually implies <math>x=y</math> for all <math>x,y</math>, such a binary relation is usually called a '''total''' or '''linear order''' - as opposed to '''partial orders''', in which <math>c(x,y)=0</math> is possible for <math>x\neq y</math>. In the last case, we say <math>x</math> and <math>y</math> are '''incomparable'''.

Weihe: /* Comparison */

2015-05-21T12:29:59Z

Comparison

← Older revision		Revision as of 12:29, 21 May 2015
Line 10:		Line 10:
	A '''comparison''' on a finite or infinite set <math>S</math> is a binary relation <math>c:S\times S \rightarrow \{ -1,0,+1\}</math> with the following properties:		A '''comparison''' on a finite or infinite set <math>S</math> is a binary relation <math>c:S\times S \rightarrow \{ -1,0,+1\}</math> with the following properties:
	* <math>c(x,x) = 0</math> for all <math>x \in S</math> (reflexivity),		* <math>c(x,x) = 0</math> for all <math>x \in S</math> (reflexivity),
	* <math>c(x,y)=-c(y,x)</math> for all <math>x,y \in S</math> (anti-~~commutativity~~), and		* <math>c(x,y)=-c(y,x)</math> for all <math>x,y \in S</math> (anti-symmetry), and
	* <math>(c(x,y) = 1 \land c(y,z) = 1) \Rightarrow c(x,z)=1</math> for all <math>x,y,z \in S</math> (transitivity)		* <math>(c(x,y) = 1 \land c(y,z) = 1) \Rightarrow c(x,z)=1</math> for all <math>x,y,z \in S</math> (transitivity).
	For convenience, we write <math>x<y</math> in case <math>c(x,y)=1</math>, <math>x\le y</math> in case <math>c(x,y)\ge 0</math>, and so on.		For convenience, we write <math>x<y</math> in case <math>c(x,y)=1</math>, <math>x\le y</math> in case <math>c(x,y)\ge 0</math>, and so on.

	===Remark===		===Remark===
	Note that <math>c(x,y)=0</math> does '''not''' imply <math>x=y</math>. If <math>c(x,y)=0</math> actually implies <math>x=y</math> for all <math>x,y</math>, such a binary relation is usually called a '''total''' or '''linear order''' - as opposed to '''partial orders''', in which pairs of elements may be incomparable.		Note that <math>c(x,y)=0</math> does '''not''' imply <math>x=y</math>. If <math>c(x,y)=0</math> actually implies <math>x=y</math> for all <math>x,y</math>, such a binary relation is usually called a '''total''' or '''linear order''' - as opposed to '''partial orders''', in which pairs of elements may be incomparable.

Weihe at 12:29, 21 May 2015

2015-05-21T12:29:15Z

← Older revision		Revision as of 12:29, 21 May 2015
Line 4:		Line 4:
	An algorithmic problem, algorithm, abstract data structure, or implementation of a data structure is '''generic''' if one or more related types are left open in the definition. The choice of these types is deferred until the algorithm is called or an object of the data structure is created.		An algorithmic problem, algorithm, abstract data structure, or implementation of a data structure is '''generic''' if one or more related types are left open in the definition. The choice of these types is deferred until the algorithm is called or an object of the data structure is created.

	~~===~~Remark~~===~~		'''Remark:'''
	Typically, there are requirements on the open types. ~~A typical requirement is that a comparison as defined below is given for~~ that ~~type~~.		Typically, there are requirements on the open types. This means an open type must offer some methods with prescribed syntax and semantics. Quite different concepts to formulate and ensure syntactical requirements are implemented in the various programming languages that support genericity.

	==Comparison==		==Comparison==

Cuozzo: Created page with "Category:Background Category:Checkup ==Definition== An algorithmic problem, algorithm, abstract data structure, or implementation of a data structure is '''generic'''..."

2014-10-02T13:14:07Z

Created page with "Category:Background Category:Checkup ==Definition== An algorithmic problem, algorithm, abstract data structure, or implementation of a data structure is '''generic'''..."

New page

[[Category:Background]]
[[Category:Checkup]]
==Definition==
An algorithmic problem, algorithm, abstract data structure, or implementation of a data structure is '''generic''' if one or more related types are left open in the definition. The choice of these types is deferred until the algorithm is called or an object of the data structure is created.

===Remark===
Typically, there are requirements on the open types. A typical requirement is that a comparison as defined below is given for that type.

==Comparison==
A '''comparison''' on a finite or infinite set <math>S</math> is a binary relation <math>c:S\times S \rightarrow \{ -1,0,+1\}</math> with the following properties:
* <math>c(x,x) = 0</math> for all <math>x \in S</math> (reflexivity),
* <math>c(x,y)=-c(y,x)</math> for all <math>x,y \in S</math> (anti-commutativity), and
* <math>(c(x,y) = 1 \land c(y,z) = 1) \Rightarrow c(x,z)=1</math> for all <math>x,y,z \in S</math> (transitivity)
For convenience, we write <math>x<y</math> in case <math>c(x,y)=1</math>, <math>x\le y</math> in case <math>c(x,y)\ge 0</math>, and so on.

===Remark===
Note that <math>c(x,y)=0</math> does '''not''' imply <math>x=y</math>. If <math>c(x,y)=0</math> actually implies <math>x=y</math> for all <math>x,y</math>, such a binary relation is usually called a '''total''' or '''linear order''' - as opposed to '''partial orders''', in which pairs of elements may be incomparable.