Linguaggio Java e Algoritmi
( 09CBIPC, 09CBIMQ )
Corsi di Laurea in
Ingegneria del cinema e dei mezzi di comunicazione
Matematica per l’Ingegneria
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
1
Java language
• Originally developed by James Gosling at Sun Microsystems
and released in 1995
• It derives much of its syntax from C and C++
• Java applications are typically compiled to bytecode that can run on any
Java Virtual Machine (JVM) regardless of computer architecture
• As of May 2007 Sun relicensed most of its Java technologies under the
GNU General Public License
• Sun Microsystems was acquired by Oracle Corporation's in 2010
• Java is as of 2012 one of the most popular programming languages in
use, particularly for client-server web applications, with a reported 10
million users
• Google and Android, Inc. have chosen to use Java to design applications
for the Android operating system, an open-source operating system built
on the Linux 2.6 kernel, designed primarily for touchscreen mobile
devices (smartphones, tablet PCs, mobile Internet devices, …)
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
2
Java Environment
• Java bytecodes
• platform-independent intermediate language
• Java Virtual Machine (Java VM)
• virtual machine able to execute Java bytecodes
Java source
Java bytecodes
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
3
Java Portability
• any implementation of Java VM can execute Java bytecodes
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
4
Java Security
Check of correctness of
parameter types and
compliance with access
rules
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
5
Java Platform
• Java Application Programming Interface (Java API)
• set of Java bytecodes libraries (packages) supporting a large range of
functionalities
• http://docs.oracle.com/javase/7/docs/api/index.html
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
6
Java Technology
CDC = Connected
Device Configuration
CLDC = Connected Limited
Device Configuration
PDA = Personal Digital
Assistant (palmare)
POS = Point Of Sale
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
7
Java Platform - Standard Edition
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
8
Java Development Kit (JDK) Tools
•
javac
•
•
The compiler for the Java programming language.
java
•
•
The launcher for Java applications.
javadoc
•
•
API documentation generator.
appletviewer
•
•
Run and debug applets without a web browser.
jar
•
•
jdb
•
•
C header and stub generator. Used to write native methods.
javap
•
•
The Java Debugger.
javah
•
•
Manage Java Archive (JAR) files.
Class file disassembler
extcheck
•
Utility to detect Jar conflicts.
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
9
Java: HelloWorld program
HelloWorld.java
public class HelloWorld
{
/* The HelloWorld class implements an application that
displays "Hello World!" to the standard output */
public static void main ( String[] args ) {
System.out.println( "Hello World!" );
}
}
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
10
Eclipse Integrated Development Environment (IDE)
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
11
Java: Primitive Data Types
Keyword
Description
Size/Format
(integers)
byte
Byte-length integer
8-bit two's complement
short
Short integer
16-bit two's complement
int
Integer
32-bit two's complement
Long integer
64-bit two's complement
Literal
Data type
178
int
8864L
long
long
37.266
double
(real numbers)
37.266D
double
87.363F
float
float
Single-precision floating point
26.77e3
double
double
Double-precision floating point 64-bit IEEE 754
' c'
char
(other types)
true
boolean
char
A single character
false
boolean
boolean
A boolean value (true or false) true or false
(real numbers)
32-bit IEEE 754
(other types)
16-bit Unicode character
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
12
Java: Arithmetic Operators
Operator
Use
Description
+
op1 + op2
Adds op1 and op2
*
op1 - op2
op1 * op2
Subtracts op2 from op1
Multiplies op1 by op2
/
op1 / op2
Divides op1 by op2
%
op1 % op2
Computes the remainder of dividing op1 by op2
Operator Use
Description
++
op++
Increments op by 1; evaluates to the value of op before it was incremented
++
++op
Increments op by 1; evaluates to the value of op after it was incremented
--
op--
Decrements op by 1; evaluates to the value of op before it was decremented
--
--op
Decrements op by 1; evaluates to the value of op after it was decremented
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
13
Java: Relational and Conditional Operators
Operator
Use
Returns true if
>
>=
<
<=
==
!=
op1 > op2
op1 >= op2
op1 < op2
op1 <= op2
op1 == op2
op1 != op2
op1 is greater than op2
op1 is greater than or equal to op2
op1 is less than op2
op1 is less than or equal to op2
op1 and op2 are equal
op1 and op2 are not equal
Operator
Use
Returns true if
&&
op1 && op2
op1 and op2 are both true , conditionally evaluates op2
||
either op1 or op2 is true , conditionally evaluates op2
&
op1 || op2
! op
op1 & op2
|
op1 | op2
either op1 or op2 is true , always evaluates op1 and op2
^
op1 ^ op2
if op1 and op2 are different--that is if one or the other of
the operands is true but not both
!
op is false
op1 and op2 are both true , always evaluates op1 and op2
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
14
Java: Shift and Logical Operators
Operator
Use
Operation
>>
op1 >> op2
shift bits of op1 right by distance op2
<<
op1 << op2
shift bits of op1 left by distance op2
>>>
op1 >>> op2
shift bits of op1 right by distance op2 (unsigned)
Operator
Use
Operation
&
op1 & op2
bitwise and
|
op1 | op2
bitwise or
^
op1 ^ op2
bitwise xor
~
~op2
bitwise complement
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
15
Java: Assignment Operators
op1= op2;
Operator
Use
Equivalent to
+=
op1 += op2
op1 = op1 + op2
-=
op1 -= op2
op1 = op1 - op2
*=
op1 *= op2
op1 = op1 * op2
/=
op1 /= op2
op1 = op1 / op2
%=
op1 %= op2
op1 = op1 % op2
&=
op1 &= op2
op1 = op1 & op2
|=
op1 |= op2
op1 = op1 | op2
^=
op1 ^= op2
op1 = op1 ^ op2
<<=
op1 <<= op2
op1 = op1 << op2
>>=
op1 >>= op2
op1 = op1 >> op2
>>>=
op1 >>>= op2
op1 = op1 >>> op2
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
16
Java: Other Operators
Operator
Use
Description
?:
op1 ? op2 : op3
If op1 is true, returns op2. Otherwise, returns op3.
[]
type [ ]
Declares an array of unknown length, which contains type elements.
[]
type [ op1 ]
[]
op1[ op2 ]
.
op1.op2
()
op1(params)
(type)
(type) op1
new
new op1
instanceof
op1 instanceof op2 Returns true if op1 is an instance of op2
Creates and array with op1 elements. Must be used with the new
operator.
Accesses the element at op2 index within the array op1. Indices begin at 0
and extend through the length of the array minus one.
Is a reference to the op2 member of op1.
Declares or calls the method named op1 with the specified parameters.
The list of parameters can be an empty list. The list is comma-separated.
Casts (converts) op1 to type . An exception will be thrown if the type of
op1 is incompatible with type.
Creates a new object or array. op1 is either a call to a constructor, or an
array specification.
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
17
Java: Control Flow Statements - looping
while (boolean expression) {
}
statement(s)
do {
statement(s)
} while (boolean expression);
for (initialization ; termination ; increment ) {
}
statement(s)
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
18
Java: Control Flow Statements – decision making
if (boolean expression) {
}
statement(s)
switch (expression) {
case constant expression :
statement(s)
...
...
default:
if (boolean expression) {
}
else {
}
statement(s)
statement(s)
}
break;
statement(s)
break;
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
19
Java: Control Flow Statements – branching
label: someJavaStatement ;
break;
terminates the innermost switch , for , while , or do-while
statement
break label;
terminates an outer switch , for , while , or do-while
statement with the given label
continue;
terminates the current iteration of the innermost loop
continue label;
terminates the current iteration of the loop with the given label
return;
terminates the current method
return value;
terminates the current method and returns a value to the
method's caller
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
20
Java: Creating Arrays
Declaring a Variable to Refer to an Array
int[] anArray; // declare an array of integers
float[] anArrayOfFloats;
boolean[] anArrayOfBooleans;
Object[] anArrayOfObjects;
String[] anArrayOfStrings;
Creating an Array
anArray = new int[10]; // create an array of 10 integers
Declaring, Creating and Initializing an Array
boolean[] answers = { true, false, true, true, false };
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
21
Java: Using Arrays
Accessing an Array Element
Getting the Size of an Array
anArray[i]
arrayname.length
Copying Arrays
System.arraycopy (Object source, int srcIndex,
Object dest, int destIndex,
int length)
source
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
22
Java: Iterating through Arrays (for statement)
Iterating through Arrays
class ForDemo
{
public static void main(String[] args)
{
int[] numbers = {1,2,3,4,5,6,7,8,9,10};
for (int i=0 ; i<numbers.length ; i++)
System.out.print(" " + numbers[i]);
}
}
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
23
Java: Iterating through Arrays (enhanced for statement)
Iterating through Arrays
class EnhancedForDemo
{
public static void main(String[] args)
{
int[] numbers = {1,2,3,4,5,6,7,8,9,10};
for (int item : numbers)
System.out.print(" " + item);
}
}
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
24
Software Quality
Functionality
Usability
Performance
Software Quality
to perform the requirements
and specification
to be user friendly
to provide appropriate response
and processing time
Reliability
to be in a failure-free
condition at all times
Efficiency
to perform appropriately, relative
to the amount of resources used
Scalability
to be easily and transparently
upgradable
Extensibility
Security
Maintainability
to have consideration for future
growth
to keep away from security
threats
to be easily modifiable
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
25
Complessità computazionale
• algoritmo :
sequenza finita di operazioni, capace di risolvere un determinato problema
in un tempo finito
• programma :
rappresentazione di un algoritmo mediante un linguaggio di
programmazione
• dimensione di un problema :
intero positivo n proporzionale allo spazio occupato dai dati di ingresso
relativi al problema
• complessità temporale ( o spaziale ) di un algoritmo :
indicazione del tempo ( o dello spazio) richiesto dall'algoritmo in
funzione della dimensione n del problema
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
26
Complessità worst/average case
• complessità nel caso peggiore ( worst-case ) :
W(n) = max { t(I) I Dn }
•
Dn è l'insieme degli ingressi I di dimensione n
•
t(I) è il tempo di esecuzione relativo all'ingresso I
• complessità media ( average-case ) :
A(n) = 
I
•

p(I) t(I)
Dn
p(I) è la probabilità di I
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
27
Complessità Asintotica
insieme delle funzioni che crescono
con rapidità non superiore a quella di
f(n)
O( f(n) )
Q( f(n) )
insieme delle funzioni che crescono
con rapidità uguale a quella di f(n)
W( f(n) )
insieme delle funzioni che crescono
con rapidità non inferiore a quella di
f(n)
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
28
Notazione O
O( f(n) ) è l'insieme di tutte le funzioni g(n) tali che esistano
due costanti positive c e m per cui :
g(n) c f(n) , "n ( n  m )
g(n)  O( f(n) ) se lim
n 
g(n)
f(n)
=c
O(c)O(log n) O( (log n)k ) O(n) O( n(log n)k ) 
O(nk) O( nk(log n)h ) O(nk+1) O(dn)
La notazione O delimita superiormente la crescita asintotica
della complessità e fornisce quindi una indicazione della
bontà di un algoritmo
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
29
Notazione W
W( f(n) ) è l'insieme di tutte le funzioni g(n) tali che
esistano due costanti positive c e m per cui :
g(n)  c f(n) ,
g(n)  W(f(n)) se
f(n)  O( g(n) )
"n ( n  m )
lim
n 
g(n)
f(n)
=

c>0
se e solo se
g(n)  W( f(n) )
Un algoritmo di complessità O( f(n) ) si dice ottimo se
qualunque algoritmo che risolva lo stesso problema ha
complessità W ( f(n) )
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
30
Programming in the Small/Large
• Programming in the small
• software projects are developed by single programmers
• main problems to be solved:
• choice of appropriate data structures
• development of efficient algorithms
• Programming in the large
• software projects are developed by large groups of programmers
• different groups make
• development (analysis, design, coding, integration, testing)
• maintenance (extensions, upgrading)
over large time intervals
• main problems to be solved:
• good choice of software components
• communication of information among components
• component integration
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
31
Sviluppo di algoritmi per raffinamenti successivi
start
definizione delle specifiche
del problema
la soluzione del problema è
esprimibile direttamente nel linguaggio
di programmazione prescelto ?
si
no
scomposizione del problema in
una sequenza , o selezione ,
o iterazione di sottoproblemi
e definizione delle specifiche
di ciascun sottoproblema
codifica
della
soluzione
si
uno dei sottoproblemi generati
coincide con uno dei problemi
da cui è stato derivato ?
no
soluzione ricorsiva
del problema
scelta di un
problema
si
ancora problemi
da risolvere ?
no
stop
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
32
Massimo Comune Divisore (1)
P /* a,b interi positivi */
CALCOLA MassimoComuneDivisore(a,b)
/* MCD(a,b) */
MCD(a,b) = MCD(b,a)
MCD(a,a) = a
MCD(a,0) = a
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
33
Massimo Comune Divisore (2)
MCD(a,a) = a
P
/* a,b interi positivi */
{ int x,y;
P1: INIZIALIZZA x,y ;
/* MCD(x,y) = MCD(a,b) */
while (x!=y)
P2: RIDUCI |x-y| SENZA VARIARE MCD(x,y) ;
}
/* x = MCD(a,b) */
P1 /* a,b interi positivi */
{
x=a;
y=b;
}
/* MCD(x,y) = MCD(a,b) */
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
34
Massimo Comune Divisore (3)
Se k è divisore comune di x e y
 x = k qx ; y = k qy
 |x-y| = k |qx - qy|
 k è divisore comune di |x-y|
P2 /* MCD(x,y) = MCD(a,b); x!=y */
{
if (x>y)
x -= y;
else
y -= x;
}
/* MCD(x,y) = MCD(a,b) */
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
35
Massimo Comune Divisore (4)
P
/* a,b interi positivi */
{ int x,y;
/* P1: INIZIALIZZA x,y */
x=a;
y=b;
/* MCD(x,y) = MCD(a,b) */
while (x!=y)
/* P2: RIDUCI |x-y| SENZA VARIARE MCD(x,y) */
if (x>y)
x -= y;
else
y -= x;
}
/* x = MCD(a,b) */
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
36
Massimo Comune Divisore (5)
public class Mcd1
{
public static void main( String[] args )
{
System.out.println("MCD(42,56)= "+ mcd(42,56));
}
static int mcd(int a, int b)
{
while (a!=b)
if (a>b)
a -= b;
else
b -= a;
return a;
}
}
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
37
Massimo Comune Divisore (6)
MCD(a,0) = a
P
/* a,b interi positivi */
{ int x,y;
P1: INIZIALIZZA x,y ;
/* MCD(x,y) = MCD(a,b) */
while (y!=0)
P3: RIDUCI y SENZA VARIARE MCD(x,y) ;
}
/* x = MCD(a,b) */
P1 /* a,b interi positivi */
{
x=a;
y=b;
}
/* MCD(x,y) = MCD(a,b) */
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
38
Massimo Comune Divisore (7)
Se k è divisore comune di x e y
 x = k qx ; y = k qy
 x % y = x – (x / y) y = k(qx – (x / y) qy)
 k è divisore comune di x % y
P3 /* MCD(x,y) = MCD(a,b); y!=0 */
{
r = x % y;
x = y;
y = r;
}
/* MCD(x,y) = MCD(a,b) */
MCD(x,y) = MCD(y,x%y)
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
39
Massimo Comune Divisore (8)
P
/* a,b interi positivi */
{ int x,y,r;
/* P1: INIZIALIZZA x,y */
x=a;
y=b;
/* MCD(x,y) = MCD(a,b) */
while (y!=0)
/* P2: RIDUCI y SENZA VARIARE MCD(x,y) */
{
r = x % y;
x = y;
y = r;
}
}
/* x = MCD(a,b) */
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
40
Massimo Comune Divisore (Euclide)
public class Mcd2
{
public static void main( String[] args )
{
System.out.println("MCD(42,56)= "+ mcd(42,56));
}
static int mcd(int a, int b)
{
int r;
while (b!=0) {
r = a % b;
a = b;
b = r;
}
return a;
}
}
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
41
Ricorsione
n! = n*(n-1)!
1! = 1
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
42
Algoritmi ricorsivi (MCD)
MCD(a,b) = MCD(b,a%b)
MCD(a,0) = a
/* a,b interi positivi */
int mcd(int a, int b)
{
if (b==0)
return a;
else
return mcd(b,a%b);
}
mcd(36,42)
6
mcd(42,36)
6
mcd(36,6)
6
mcd(6,0)
6
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
43
Algoritmi ricorsivi (Fattoriale)
n! = n*(n-1)!
1! = 1
/* n intero positivo */
int fact(int n)
{
if (n==1)
return 1;
else
return n * fact(n-1);
}
fact(4)
24
fact(3)
6
fact(2)
2
fact(1)
1
complessità: O(n)
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
44
Algoritmi ricorsivi (Potenza)
b¹ = b
be = b * be-1
/* b,e interi positivi */
int pot(int b, int e)
{
if (e==1)
return b;
else
return b * pot(b,e-1);
}
pot(3,4)
81
pot(3,3)
27
pot(3,2)
9
pot(3,1)
3
complessità: O(e)
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
45
Algoritmi ricorsivi (Potenza)
b¹ = b
e pari  be = (b * b)e/2
e dispari  be = b * be-1 = b * (b * b)e/2
/* b,e interi positivi */
int pot(int b, int e)
{
if (e==1)
return b;
else
if ((e & 1)==1)
return b*pot(b*b,e/2); //e dispari
else
return pot(b*b,e/2);
//e pari
}
pot(3,5)
243
pot(9,2)
81
pot(81,1)
81
complessità: O(log2 e)
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
46
Algoritmi ricorsivi (Torri di Hanoi)
1
n
sorgente
intermedia
destinazione
P /* n dischi ordinati in s */
Sposta n dischi da s a d utilizzando i,
muovendo un disco per volta e mantenendo
l’ordinamento
/* n dischi ordinati in d */
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
47
Algoritmi ricorsivi (Torri di Hanoi)
1
n
n-1
sorgente
intermedia
destinazione
1
n-1
n
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
48
Algoritmi ricorsivi (Torri di Hanoi)
P
/* n dischi ordinati in s */
{
P: Sposta n-1 dischi da s a i utilizzando d,
muovendo un disco per volta e mantenendo
l’ordinamento;
/* n-1 dischi ordinati in i */
P1: Sposta il disco n da s a d;
P: Sposta n-1 dischi da i a d utilizzando s,
muovendo un disco per volta e mantenendo
l’ordinamento;
}
/* n dischi ordinati in d */
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
49
Algoritmi ricorsivi (Torri di Hanoi)
P
/* n dischi ordinati in s */
void hanoi(int n, char s, char i, char d)
{
if (n==1)
System.out.println("muovi 1 da " + s + " a " + d);
else
{
hanoi(n-1,s,d,i);
/* n-1 dischi ordinati in i */
System.out.println("muovi " + n + " da " + s +
" a " + d);
hanoi(n-1,i,s,d);
}
}
/* n dischi ordinati in d */
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
50
Algoritmi ricorsivi (Torri di Hanoi)
public class Hanoi
{
public static void main( String[] args )
{
hanoi(5,'S','I','D');
}
static void hanoi(int n, char s, char i, char d)
{
if (n==1)
System.out.println("muovi 1 da " + s + " a " + d);
else
{
hanoi(n-1,s,d,i);
System.out.println("muovi " + n + " da " + s + " a " + d);
hanoi(n-1,i,s,d);
}
}
}
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
51
Algoritmi ricorsivi (Torri di Hanoi)
n
n-1
n-2
20
n-1
n-2
n-2
21
n-2
22
1
1
1
1
1
1 1
1
…
2n-1
20 + 21 + 22 +…+ 2n-1 = 2n - 1
complessità: O(2n)
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
52
Algoritmi ricorsivi (Fibonacci)
• L'intento di Fibonacci (Pisa, 1170-1240) era quello di trovare una legge
matematica che potesse descrivere la crescita di una popolazione di conigli
• Assumendo per ipotesi che:
•
•
•
•
si disponga di una coppia di conigli appena nati
questa coppia diventi fertile al compimento del primo mese e dia alla luce una nuova coppia al
compimento del secondo mese
le coppie fertili, dal secondo mese di vita in poi, diano alla luce una coppia di figli al mese
le nuove coppie nate si comportino in modo analogo
• si verifica quanto segue:
•
•
•
•
•
•
•
nel primo mese c’è 1 coppia di conigli (non fertile)
nel secondo mese c’è 1 coppia (fertile)
nel terzo mese ci saranno 1+1=2 coppie (1 fertile , 1 non fertile)
nel quarto mese ci saranno 1+2=3 coppie (2 fertili , 1 non fertile)
nel quinto mese ci saranno 2+3=5 coppie (3 fertili , 2 non fertili)
…
in ogni mese il numero totale di coppie è uguale alla somma dei numeri di coppie presenti nei
due mesi precedenti:
1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 , 89 , 144 , 233 , …
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
53
Algoritmi ricorsivi (Fibonacci)
fib(n) = fib(n-1) + fib(n-2)
fib(1) = 1
fib(0) = 0
Mario Merz: Il volo dei numeri
Torino, Luci d’artista
/* n intero positivo */
int fib(int n)
{
if (n<=1)
return n;
else
return fib(n-1) + fib(n-2);
}
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
54
Algoritmi ricorsivi (Fibonacci)
fib(4)
fib(2)
1
fib(3)
2
fib(1)
fib(2)
1
1
fib(1)
3
fib(1)
fib(0)
1
0
fib(0)
1
0
complessità: O(2n)
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
55
Ricorsione  Iterazione (Fibonacci)
/* n intero positivo
int fib(int n)
{
int f1=1;
int f0=0;
for (int i=1; i<n;
{
/* f1 = fib(i) ,
f1 += f0;
/* f1 = fib(i+1)
f0 = f1-f0;
/* f1 = fib(i+1)
}
return f1;
}
*/
i++)
f0 = fib(i-1) */
, f0 = fib(i-1) */
, f0 = fib(i) */
complessità: O(n)
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
56
Algoritmi di ordinamento
v
insieme non ancora ordinato
v
insieme ordinato
P
v
N-1
0
v
0
i
N-1
v
0
int[] v;
...
for(i=0; i<v.length; i++)
{
P1: SPOSTA UN ELEMENTO
DI v DALLA PORZIONE
NON ORDINATA A QUELLA
ORDINATA
}
N-1
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
57
Algoritmi di ordinamento (crescente)
P1
P12: SELEZIONA IL PIU’PICCOLO ELEMENTO DELLA PORZIONE
NON ORDINATA E SCAMBIALO CON QUELLO DI INDICE i
v
m
0
P1
N-1
i
P13: INSERISCI L’ELEMENTO DI INDICE i NELLA PORZIONE
ORDINATA, SPOSTANDO IN AVANTI QUELLI PIU’ GRANDI
v
0
i
N-1
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
58
Ordinamento per selezione
3
m
1
P12
v
0
im
i
2
N-1
m = v[i] ;
im = i ;
for(j=i+1; j<N; j++)
if( v[j] < m )
{
m = v[j];
im = j;
}
v[im] = v[i];
v[i] = m;
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
59
Ordinamento per selezione
void selectSort(int[] v)
{
int i,j,m,im;
int n = v.length;
for (i=0; i<n-1; i++)
{
m = v[i];
im = i;
for (j=i+1; j<n; j++)
if( v[j] < m )
{
m = v[j];
im = j;
}
v[im] = v[i];
v[i] = m;
}
}
complessità: O(n2)
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
60
Ordinamento per selezione
public class Selectsort
{
public static void main(String[] args)
{
int[] a = {3,2,4,6,3,9,8,7,5};
selectSort(a);
for(int i:a)
System.out.print(i+" ");
}
static void selectSort(int[] v)
{
...
}
}
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
61
Ordinamento per inserimento
v
i
0
N-1
x
1
4
v
0
P13
3
2 i
N-1
x = v[i] ;
for( j=i-1; j>=0 && x<v[j]; j-- )
v[j+1] = v[j];
v[j+1] = x;
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
62
Ordinamento per inserimento
void insertSort(int[] v)
{
int i,j,x;
int n = v.length;
for (i=1; i<n; i++)
{
x = v[i];
for (j=i-1; j>=0 && x<v[j]; j--)
v[j+1] = v[j];
v[j+1] = x;
}
}
complessità: O(n2)
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
63
Ordinamento per inserimento
public class Insertsort
{
public static void main(String[] args)
{
int[] a = {3,2,4,6,3,9,8,7,5};
insertSort(a);
for(int i:a)
System.out.print(i+" ");
}
static void insertSort(int[] v)
{
...
}
}
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
64
Quicksort
v
l
P
m
h
int[] v;
...
{
P1: PARTIZIONA GLI ELEMENTI DI v IN MODO TALE CHE OGNI
ELEMENTO DELLA PARTIZIONE VERDE SIA MINORE DI
(O UGUALE A) OGNI ELEMENTO DELLA PARTIZIONE ROSSA
}
P:
ORDINA GLI ELEMENTI NELLA PARTIZIONE VERDE
P:
ORDINA GLI ELEMENTI NELLA PARTIZIONE ROSSA
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
65
Quicksort
void quickSort(int[] v, int l, int h)
{
int m;
if ( l < h )
{
m = partition(v, l, h); /* P1 */
quickSort(v, l, m);
quickSort(v, m+1, h);
}
}
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
66
Quicksort
v[ i ] < x
v[ j ] > x
v
i
P1
j
int partition ( int[] v, int i, int j )
{
SCEGLI COME PERNO UN QUALUNQUE ELEMENTO x DI v
while (true)
{
FINCHÈ v[i] < x INCREMENTA i
/* v[i]>=x */
FINCHÈ v[j] > x DECREMENTA j
/* v[j]<=x */
if ( i < j ) SCAMBIA TRA LORO v[i] E v[j]
}
}
else return j
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
67
Quicksort
P1
int partition(int[] v, int i, int j)
{
int x,t;
x = v[(i+j)/2];
while (true)
{
while ( v[i] < x ) i++ ;
while ( v[j] > x ) j-- ;
if ( i < j )
{
t = v[i]; v[i] = v[j]; v[j] = t;
i++;
j--;
}
else
return j;
}
}
complessità(partition): O(n)
compl_media(quickSort): O(n log2 n)
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
68
Quicksort
public class Quicksort
{
public static void main(String[] args)
{
int[] a = {3,2,4,6,3,9,8,7,5};
quickSort(a, 0, a.length-1);
for(int i:a)
System.out.print(i+" ");
}
static void quickSort(int[] v, int l, int h)
{
...
}
static int partition(int[] v, int i, int j)
{
...
}
}
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
69
Mergesort
v
l
P
l+h
2
h
int[] v;
...
{
P:
ORDINA LA PRIMA METÀ DI v
P:
ORDINA LA SECONDA METÀ DI v
P1: FONDI LE DUE METÀ IN UN UNICO INSIEME ORDINATO
}
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
70
Mergesort
void mergeSort(int[] v, int l, int h)
{
int m;
if ( l < h )
{
m = (l+h)/2;
mergeSort(v, l, m);
mergeSort(v, m+1, h);
merge(v, l, h);
/* P1 */
}
}
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
71
Mergesort
P1
void merge ( int[] v, int l, int h )
{
COPIA LA PRIMA METÀ DI v IN aux
NELLO STESSO ORDINE
COPIA LA SECONDA METÀ DI v IN aux
IN ORDINE INVERSO
i = l;
j = h;
for (k = l; k <= h; k++)
v[k] = (aux[j] < aux[i])? aux[j--]: aux[i++];
}
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
72
Mergesort
P1
void merge(int[] v, int l, int h)
{
int i,j,k,m;
m = (l+h)/2;
for (i = l; i <= m; i++)
aux[i] = v[i];
for (j = m+1; j <= h; j++)
aux[j] = v[h-j+m+1];
i = l;
j = h;
for (k = l; k <= h; k++)
v[k] = (aux[j] < aux[i])? aux[j--]: aux[i++];
}
complessità(merge): O(n)
complessità(mergeSort): O(n log2 n)
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
73
Mergesort
public class Mergesort
{
static int[] aux;
public static void main(String[] args)
{
int[] a = {3,2,4,6,3,9,8,7,5};
aux = new int[a.length];
mergeSort(a, 0, a.length-1);
for(int i:a)
System.out.print(i+" ");
}
static void mergeSort(int[] v, int l, int h)
{
...
}
static void merge(int[] v, int l, int h)
{
...
}
}
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
74
Algoritmi di ricerca
insieme
v
x
P
int[] v;
int x;
...
{
if ( x È UN ELEMENTO DI v )
return LA POSIZIONE DI x IN v ;
else
return -1 ;
}
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
75
Ricerca in insiemi non ordinati
int search(int[] v, int x)
{
int i;
int n = v.length;
for (i=0; i<n; i++)
if (x == v[i] )
return i;
return -1;
}
complessità: O(n)
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
76
Ricerca in insiemi ordinati (crescenti)
int search(int[] v, int x)
{
int i;
int n = v.length;
for (i=0; i<n && x >= v[i]; i++)
if (x == v[i] )
return i;
return -1;
}
complessità: O(n)
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
77
Ricerca dicotomica (binaria) in insiemi ordinati (crescenti)
v
l
P
l+h
2
h
int[] v;
int x;
int m;
...
{
m = (l+h)/2;
if ( x == v[m] )
return m ;
else
if ( x < v[m] )
P: RICERCA x NELLA PRIMA METÀ DI v;
else
P: RICERCA x NELLA SECONDA METÀ DI v;
}
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
78
Ricerca binaria (ricorsiva)
int rbsearch(int[] v, int l, int h, int x)
{
int m;
if ( l > h )
return -1;
else
{
m = (l+h)/2;
if ( x == v[m] )
return m;
if ( x < v[m] )
return rbsearch(v, l, m-1, x);
else
return rbsearch(v, m+1, h, x);
}
}
complessità: O(log2 n)
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
79
Ricerca binaria (iterativa)
int ibsearch(int[] v, int l, int h, int x)
{
int m;
while ( l <= h )
{
m = (l+h)/2;
if ( x == v[m] )
return m;
if ( x < v[m] )
h=m-1;
else
l=m+1;
}
return -1
}
complessità: O(log2 n)
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
80
Ricerca indicizzata da chiave
• Se gli elementi con chiave di ricerca x vengono memorizzati nella
posizione x , il tempo di accesso è costante
0
325
x = v[x]
…
325
…
673
673
…
729
729
xmax …
• Tuttavia, se l’intervallo dei valori di x è molto più grande del
numero di elementi da memorizzare, lo spreco di memoria diventa
inaccettabile
• Es: se 0 < x < 1000 e il numero di elementi è 100 , lo spreco è del 90%
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
81
Tabelle Hash
• Una funzione hash trasforma una chiave x in un indice h(x) minore
della dimensione N della tabella
• Es: h(x) = x % N
x = v[ h(x) ]
N = 100
0
…
25
325
…
29
729
…
73
673
99
…
• Se h(x1) = h(x2) , si verifica una collisione
• Es: 729%100 = 29 = 29%100 = 129%100 = 229%100 = …
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
82
Risoluzione delle collisioni (con scansione lineare)
• Quando si verifica una collisione ( la posizione h(x) è già
occupata) , l’elemento con chiave x viene inserito nella prima
posizione libera successiva
• Es: N = 100
…
25
325
x = v[ (x%N + i)%N ]
26
-1
27
127
posizione k libera: v[k] = -1
28
29
528
30
-1
31
831
32
232
insert(427)
729
…
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
83
Tabella Hash a scansione lineare
int[] v = new int[N];
for(int i=0; i< v.length; i++) v[i]= -1;
void insert(int[] v, int x) {
int i = x % v.length;
while ( v[i] != -1 )
i = (i+1) % v.length;
v[i] = x;
}
int search(int[] v, int x) {
int i = x % v.length;
while ( v[i] != -1 )
if (v[i] == x)
return i;
else i = (i+1) % v.length;
return -1;
}
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
84
Costo della scansione lineare
• Nel caso peggiore la scansione lineare ha complessità O(n)
( n = numero di elementi presenti nella tabella )
• Il costo (numero di sondaggi) medio di una ricerca è:
•
1
1
+
2
2(1-a)
(ricerca con successo)
•
1
1
+
2
2(1-a)2
(ricerca senza successo)
• dove a = n / N è il fattore di carico
• La complessità media di una ricerca è pertanto:
• O( n / (N-n) )
• O( n2 / (N-n)2 )
(con successo)
(senza successo)
Silvano Rivoira - Dipartimento di Automatica e Informatica - Politecnico di Torino
85