Inteligenta Artificial A Curs

download Inteligenta Artificial A Curs

of 183

  • date post

    10-Jul-2015
  • Category

    Documents

  • view

    333
  • download

    0

Embed Size (px)

Transcript of Inteligenta Artificial A Curs

Programare LogicNicolae Constantinescu

2

CuprinsPrefa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 0.1 Introducere. Fapte. Reguli . . . . . . . . . . . . . . . . . . . . . 15 0.1.1 0.1.2 0.1.3 0.1.4 0.2 Fundamente teoretice . . . . . . . . . . . . . . . . . . . . 15 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 Exerciii propuse . . . . . . . . . . . . . . . . . . . . . . 28 Teme de studiu . . . . . . . . . . . . . . . . . . . . . . . 28

Termeni. Variabile. Backtracking. Predicatele-sistem trace, read, write . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 0.2.1 0.2.2 0.2.3 Fundamente teoretice . . . . . . . . . . . . . . . . . . . . 29 Exerciii propuse . . . . . . . . . . . . . . . . . . . . . . 40 Teme de studiu . . . . . . . . . . . . . . . . . . . . . . . 40

0.3

Unicarea. Operaiile aritmetice . . . . . . . . . . . . . . . . . . 41 0.3.1 0.3.2 0.3.3 0.3.4 Fundamente teoretice . . . . . . . . . . . . . . . . . . . . 41 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 Exerciii propuse . . . . . . . . . . . . . . . . . . . . . . 48 Teme de studiu . . . . . . . . . . . . . . . . . . . . . . . 48 3

0.4

Recursivitate. Predicatele !(cut) i fail . . . . . . . . . . . . . . 49 0.4.1 0.4.2 0.4.3 0.4.4 Fundamente teoretice . . . . . . . . . . . . . . . . . . . . 49 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 Exerciii propuse . . . . . . . . . . . . . . . . . . . . . . 64 Teme de studiu . . . . . . . . . . . . . . . . . . . . . . . 64

0.5

Turnurile din Hanoi. Funciile Fibonacci i Ackermann . . . . . 65 0.5.1 0.5.2 0.5.3 0.5.4 Fundamente teoretice . . . . . . . . . . . . . . . . . . . . 65 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 Exerciii propuse . . . . . . . . . . . . . . . . . . . . . . 71 Teme de studiu . . . . . . . . . . . . . . . . . . . . . . . 72

0.6

Liste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 0.6.1 0.6.2 0.6.3 0.6.4 Fundamente teoretice . . . . . . . . . . . . . . . . . . . . 73 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 Exerciii propuse . . . . . . . . . . . . . . . . . . . . . . 98 Teme de studiu . . . . . . . . . . . . . . . . . . . . . . . 99

0.7

Grafuri. Arbori . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 0.7.1 0.7.2 0.7.3 0.7.4 Fundamente teoretice . . . . . . . . . . . . . . . . . . . . 100 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 101 Exerciii propuse . . . . . . . . . . . . . . . . . . . . . . 105 Teme de studiu . . . . . . . . . . . . . . . . . . . . . . . 105

0.8

Probleme speciale . . . . . . . . . . . . . . . . . . . . . . . . . . 106 0.8.1 0.8.2 Problema Damelor . . . . . . . . . . . . . . . . . . . . . 106 Problema mutrii calului . . . . . . . . . . . . . . . . . . 108 4

0.8.3 0.8.4 0.9

Exerciii propuse . . . . . . . . . . . . . . . . . . . . . . 110 Teme de studiu . . . . . . . . . . . . . . . . . . . . . . . 110

Fiiere. Baze de date dinamice . . . . . . . . . . . . . . . . . . . 112 0.9.1 0.9.2 0.9.3 0.9.4 Fundamente teoretice . . . . . . . . . . . . . . . . . . . . 112 Exemple . . . . . . . . . . . . . . . . . . . . . . . . . . . 115 Exerciii propuse . . . . . . . . . . . . . . . . . . . . . . 120 Teme de studiu . . . . . . . . . . . . . . . . . . . . . . . 121 123

1 Probleme de la concursurile de programare 1.1

Probleme de la concursurile de programare . . . . . . . . . . . . 124 1.1.1 1.1.2 1.1.3 1.1.4 1.1.5 1.1.6 1.1.7 1.1.8 1.1.9 Ascii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 Staii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125 Triplete . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 Spirala . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 Perioada . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 Numere . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 Triunghi . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 Diamant . . . . . . . . . . . . . . . . . . . . . . . . . . . 130 Drum . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134

1.1.10 Tabla

1.1.11 arpele belgian . . . . . . . . . . . . . . . . . . . . . . . 135 1.1.12 Hexagon . . . . . . . . . . . . . . . . . . . . . . . . . . . 136 2 Soluiile problemelor propuse 5 139

2.1

Introducere. Fapte. Reguli . . . . . . . . . . . . . . . . . . . . . 139 2.1.1 2.1.2 2.1.3 Soluie teoretic . . . . . . . . . . . . . . . . . . . . . . . 139 Apel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141 Cod surs . . . . . . . . . . . . . . . . . . . . . . . . . . 142

2.2

Termeni. Variabile. Backtracking. Predicatele-sistem trace, read, write . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144 2.2.1 2.2.2 2.2.3 Soluie teoretic . . . . . . . . . . . . . . . . . . . . . . . 145 Apel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 Cod surs . . . . . . . . . . . . . . . . . . . . . . . . . . 146

2.3

Unicarea. Operaiile aritmetice . . . . . . . . . . . . . . . . . . 149 2.3.1 2.3.2 2.3.3 Soluie teoretic . . . . . . . . . . . . . . . . . . . . . . . 150 Apel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 Cod surs . . . . . . . . . . . . . . . . . . . . . . . . . . 150

2.4

Recursivitate. Predicatele !(cut) i fail . . . . . . . . . . . . . . 151 2.4.1 2.4.2 2.4.3 Soluie teoretic . . . . . . . . . . . . . . . . . . . . . . . 151 Apel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 Cod surs . . . . . . . . . . . . . . . . . . . . . . . . . . 152

2.5

Turnurile din Hanoi. Funciile Fibonacci i Ackermann . . . . . 152 2.5.1 2.5.2 2.5.3 Soluie teoretic . . . . . . . . . . . . . . . . . . . . . . . 152 Apel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 Cod Surs . . . . . . . . . . . . . . . . . . . . . . . . . . 153

2.6

Liste . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 2.6.1 Soluie teoretic . . . . . . . . . . . . . . . . . . . . . . . 153 6

2.6.2 2.6.3 2.7

Apel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154 Cod surs . . . . . . . . . . . . . . . . . . . . . . . . . . 155

Probleme speciale . . . . . . . . . . . . . . . . . . . . . . . . . . 156 2.7.1 2.7.2 2.7.3 Soluie teoretic . . . . . . . . . . . . . . . . . . . . . . . 156 Apel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 Cod surs . . . . . . . . . . . . . . . . . . . . . . . . . . 157

2.8

Fiiere. Baze de date dinamice . . . . . . . . . . . . . . . . . . . 158 2.8.1 2.8.2 Soluia problemei 0.9.1 . . . . . . . . . . . . . . . . . . . 159 Soluia problemei 0.9.2 . . . . . . . . . . . . . . . . . . . 163 167

3 Anexa Predicate 3.1

Anexa predicate . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 3.1.1 3.1.2 3.1.3 3.1.4 3.1.5 3.1.6 3.1.7 3.1.8 3.1.9 Notaiile predicatelor . . . . . . . . . . . . . . . . . . . . 168 ncrcarea ierelor surs . . . . . . . . . . . . . . . . . . 168 Compararea i unicarea termenilor . . . . . . . . . . . . 168 Predicate de control . . . . . . . . . . . . . . . . . . . . 169 Baze de date dinamice . . . . . . . . . . . . . . . . . . . 170 Intrri i Ieiri . . . . . . . . . . . . . . . . . . . . . . . . 170 Predicate primitive pentru I/O . . . . . . . . . . . . . . 173 Citirea i scrierea termenilor . . . . . . . . . . . . . . . . 174 Predicate pentru operaii cu liste . . . . . . . . . . . . . 175

3.1.10 Predicate aritmetice . . . . . . . . . . . . . . . . . . . . 176 3.1.11 Funcii aritmetice . . . . . . . . . . . . . . . . . . . . . . 177 3.1.12 Urmrirea execuiei programului . . . . . . . . . . . . . . 179 7

8

List de guri1 1.1 1.2 1.3 1.4 1.5 1.6 Fereastra pentru trace n mod grac . . . . . . . . . . . . . . . . 35 Exemple de apel pentru N=5 i respectiv N=3 . . . . . . . . . . 124 Exemplu de display digital . . . . . . . . . . . . . . . . . . . . . 129 Tabla nemodicat de spiritul ru . . . . . . . . . . . . . . . . . 132 Tabla alterat . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 Exemplu de tabl i reprezentarea corespunztoare . . . . . . . 134 Hexagon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

9

10

List de tabele1 2 3 4 5 Funcii trigonometrice disponibile n SWI-Prolog . . . . . . . . . 43 Funcii matematice disponibile n SWI-Prolog . . . . . . . . . . 44 Predicatele aritmetice in SWI-Prolog . . . . . . . . . . . . . . . 45 Cteva valori ale funciei Ackermann . . . . . . . . . . . . . . . 70 Valorile funciei Ackerman calculate n SWI-Prolog . . . . . . . 71

11

PrefaProgramarea logic este o paradigm a programrii declarative, bazat pe logica de ordinul I. Teza potrivit creia logica de ordinul I este un util i practic limbaj de programare non-deterministic de nivel nalt cu un solid fundament teoretic aparine lui R. Kowalsky, care dezvolt un punct de vedere relaional al calculabilitii ca deducie, sintetizat prin urmtoarea formul: Calculabilitate = Logic + Control Dac punem n antitez relaia lui Kowalsky cu cea a lui N. Wirth potrivit creia: Program = Structuri de date + Algoritm observm c, n domeniul programrii procedurale - trebuie rezolvate la nivelul codului att aspectele logice, ct i cele de control declarative - trebuie rezolvate numai cele de control. Considernd c un program logic este constituit dintr-o familie de axiome i o int, iar regulile de inferen determin faptul c axiomele sunt suciente pentru a proba veridicitatea intei, execuia unui program logic corespunde construciei unei demonstraii a intei pe baza axiomelor ataate programului. Practic, execuia unei secvene de cod n programarea logic