8299308024

Spis treści

1 Matematyczne korzenie informatyki    1

1.1    Wstęp........................................ 2

1.2    Matematyczne modele obliczeń.......................... 3

1.2.1    Automaty skończone............................ 4

1.2.2    Maszyny Turinga.............................. 7

1.2.2.1    Określenie ............................ 7

1.2.2.2    Maszyny Turinga jako akceptory................ 10

1.2.2.3    Maszyny Turinga jako generatory............... 11

1.2.2.4    Znaczenie maszyn Turinga................... 11

1.2.2.5    Rozstrzygalność problemów i obliczalność funkcji....... 12

1.2.3    A-rachunek................................. 14

1.2.3.1    Określenia i konwersje...................... 14

1.2.3.2    A-rachunek jako model obliczeń................. 16

1.3    O językach i gramatykach............................. 16

1.3.1    Określenie gramatyk............................ 17

1.3.2    Przykłady.................................. 18

1.3.3    Hierarchia Chomsky’ego gramatyk formalnych ............. 21

1.3.4    Generatory a akceptory.......................... 23

1.3.5    Znaczenie praktyczne klas języków formalnych ............. 23

1.4    Złożoność obliczeniowa............................... 24

1.4.1    Czas działania programu jako funkcja wielkości danych......... 24

1.4.1.1    Definicja złożoności czasowej.................. 25

1.4.1.2    Przykłady ............................ 26

1.4.2    Asymptotyczna klasyfikacja algorytmów................. 26

1.4.2.1    Asymptotyczna klasyfikacja funkcji .............. 27

1.4.2.2    Czas asymptotyczny a prędkość działania........... 29

1.4.3    Złożoność problemów ........................... 29

1.4.4    Hipoteza V ^ JfV i jej konsekwencje................... 30

1.5    Logiczne podstawy informatyki.......................... 32

1.5.1    Logika klasyczna.............................. 33

1.5.1.1    Język logiki pierwszego rzędu.................. 34

1.5.1.2    Interpretacja języka w modelu................. 35

1.5.1.3    Teoria aksjomatyczna...................... 38

1.5.2    Logiki nieklasyczne............................. 41

1.5.2.1    Logiki wielowartościowe..................... 41

1.5.2.2    Krótka informacja o logikach modalnych ........... 42

1