Wybrane zagadnienia informatyki teoretycznej - SERGII KRYVYI, NORBERT SCZYGIOL

SŁOWO WSTĘPNE [fragment] :

W czasach globalnego wykorzystania komputerów i rozwoju systemów informatycznych powstają problemy o charakterze teoretycznym, sięgające samych podstaw informatyki teoretycznej.
W związku z tym przygotowanie specjalisty wysokiej klasy z zakresu informatyki wymaga przekazania mu obszernej wiedzy zarówno praktycznej, jak i teoretycznej.

W książce czytelnik spotka się z szeroko wykorzystywanymi w praktyce teoretycznymi podstawami informatyki.
Pierwsze cztery podrozdziały opisują działy współczesnej matematyki:
- teorię mnogości,
- algebrę relacji, algebry uniwersalne i algebrę Boole'a,
- teorię grafów i działania na grafach.

Sposób opisu powyższych zagadnień ukierunkowany jest na zastosowanie praktyczne w technikach informatycznych.

Następny rozdział zawiera podstawowe pojęcia z teorii algorytmów.
Przedstawione zostały najważniejsze systemy algorytmiczne:
- funkcje częściowo rekurencyjne oraz pojęcia problemu rozstrzygalnego i nierozstrzygalnego,
- maszyny Posta i maszyny Turinga,
- normalne algorytmy Markowa.

Wiadomości z zakresu algebry uniwersalnej i algebry relacji oraz normalnych algorytmów Markowa wykorzystuje się do tworzenia algebraicznego systemu struktur listowych oraz algebry relacyjnej.

Wiedza, obejmująca teorię grafów i algebrę Boole 'a, znajduje zastosowanie do przedstawienia funkcji boole 'owskich w postaci tzw. uporządkowanych diagramów binarnych decyzji (UDBD) (ang. OBDD - Ordered Binary Decision Diagrams).
Można je wykorzystać do przedstawienia obiektów informatycznych, takich jak: automaty skończone, systemy tranzytywne, grafy etykietowane itd.

Jednym z najobszerniejszych rozdziałów jest rozdział poświęcony formalnym językom logicznym, nazywanym logikami:
- logice zdań,
- logice predykatów pierwszego rzędu,
- logice modalnej i temporalnej logice liniowej.

Powyższe logiki są podstawą specyfikacji właściwości systemów tranzytywnych oraz analizy rozumowań.
W książce opisano metodę rezolucyjną oraz algorytm unifikacji w absolutnie wolnej algebrze.
Ostatnie dwa rozdziały opisują systemy tranzytywne oraz specyfikacje logiczne pewnych właściwości tychże systemów.

Wszystkie rozdziały oraz niektóre z podrozdziałów zawierają ćwiczenia niezbędne do lepszego zrozumienia przekazywanego tam materiału...


SPIS TREŚCI :

SŁOWO WSTĘPNE

1. ZBIORY, RELACJE, ALGEBRY, GRAFY

1.1. TEORIA MNOGOŚCI
1.1.1. Zbiory
1.1.2. Działania na zbiorach
1.2. RELACJE
1.2.1. Definicje i ogólne właściwości relacji
1.2.2. Przykłady relacji
1.2.3. Relacja równoważności
1.2.4. Domknięcie relacji
1.2.5. Odwzorowania i funkcje
1.2.6. Relacja porządku częściowego
1.2.7. Przykłady odwzorowań
1.3. ALGEBRA
1.3.1. Algebry uniwersalne
1.3.2. Pewne algebry wolne i ich właściwości
1.3.3. Algebry Boole'a
1.3.4. Kraty
1.3.5. Algebry nieuniwersalne
1.4. GRAFY
1 4.1. Podstawowe definicje
1.4.2. Drogi, cykle, spójność
1.4.3. Rodzaje grafów nieskierowanych i najprostsze właściwości grafów
1.4.4. Izomorfizm grafów. Podgrafy
1.4.5. Działania na grafach
1.4.6. Grafy nieskończone
1.4.7. Drzewa

2. SYSTEMY ALGORYTMICZNE

2.1. POJĘCIE ALGORYTMU I SYSTEMU ALGORYTMICZNEGO
2.1.1. Intuicyjne pojęcie algorytmu
2.1.2. Funkcje częściowo rekurencyjne. Teza Churcha
2.1.3. Problem rozstrzygalności algorytmicznej
2.1.4. Maszyny Posta
2.1.5. Maszyna Turinga
2.1.6. Maszyna Turinga i ogólne problemy programowania
2.1.7. System algorytmiczny Markowa
2.2. ZASTOSOWANIA ALGEBR I SYSTEMU MARKOWA
2.2.1. Algebra struktur listowych
2 2.2. Algebra relacyjna
2.3. FUNKCJE BOOLE'OWSKIE I ICH REPREZENTACJA
2.3.1. Diagramy binarnych decyzji
2.3.2. Działania na UDBD
2.3.3. Budowa i przekształcanie UDBD
2.3.4. UDBD i przedstawienie obiektów matematycznych

3. LOGIKI KLASYCZNE I NIEKLASYCZNE

3.1. RACHUNEK ZDAŃ
3.1.1. Syntaktyka i semantyka rachunku zdań
3.1.2. Pełny system spójników
3.1.3. System aksjomatyczny dla rachunku zdań
3.1.4. Niesprzeczność i zupełność rachunku zdań
3.1.5. Rachunek zdań i algebra Boole'a
3.1.6. Metody dowodzenia tautologii w rachunku zdań
3.2. LOGIKI NIEKLASYCZNE
3.2.1. Logika modalna zdań (LMZ)
3.2.2. Zdaniowa logika temporalna (ZLT)
3.2.3. Metoda tablo semantycznego dla ZLT
3.2.4. Przykład zastosowania ZLT
3.2.5. Rozszerzenie ZLT (R2LT)
3.3. RACHUNEK PREDYKATÓW PIERWSZEGO RZĘDU
3.3.1. Syntaktyka - alfabet i formuły
3.3.2. Semantyka - spełnialność, interpretacje, modele
3.3.3. System aksjomatyczny i prawa dowodu
3.3.4. Podstawowe właściwości rachunku predykatów i teorii pierwszego rzędu
3.3.5. Postaci normalne formuł logiki predykatów pierwszego rzędu
3.4. PREDYKATY I AUTOMATYZACJA ROZUMOWAŃ
3.4.1. Metoda Herbranda prostowania twierdzeń rachunku predykatów
3.4.2. Drzewa semantyczne
3.4.3. Twierdzenie Herbranda
3.4.4. Metoda rezolucji dowodu twierdzeń w rachunku predykatów

4. SYSTEMY TRANZYTYWNE

4.1. LOGIKI I SYSTEMY TRANZYTYWNE
4.1.1. Definicje
4.1.2. Przykłady systemów tranzytywnych
4.2. SPECYFIKACJA WŁAŚCIWOŚCI ST ZA POMOCĄ LOGIK
4.2.1. Logika zdań
4.2.2. Zdaniowa logika temporalna
4.3. TEORIA AUTOMATÓW SKOŃCZONYCH
4.3.1. Definicje podstawowe
4.3.2. Sposoby przedstawienia automatów
4.3.3. Podautomaty. Homomorfizm automatów
4.3.4. Twierdzenie o automacie minimalnym
4.3.5. Automaty niedeterministyczne
4.4. AUTOMATY SKOŃCZONE I JĘZYKI REGULARNE
4.4.1. Działania na językach
4.4.2. Twierdzenie o analizie automatów skończonych
4.4.3. Twierdzenia o syntezie automatów skończonych
4.5. PRAKTYCZNE ALGORYTMY SYNTEZY I ANALIZY
4.5.1. Algorytm analizy automatów skończonych
4.5.2. Zastosowania układu równań do analizy automatów
4.5.3. Algorytm syntezy automatów skończonych
4.5.4. Zasady budowy reprezentacji graficznej
4.5.5. Synteza automatu na podstawie reprezentacji graficznej
4.5.6. Synteza automatu na podstawie układu wyrażeń regularnych
4.5.7. Algorytm minimalizacji automatów

BIBLIOGRAFIA

SKOROWIDZ