Bevezetés a programozásba
   Következő

Bevezetés a programozásba

Copyright © 2005 Fóthi Ákos, Horváth Zoltán

A mű digitális megjelenítése az Oktatási Minisztérium támogatásával, a Felsőoktatási Tankönyv- és Szakkönyv-támogatási Pályázat keretében történt.

2005. március 31.

Tartalom

I. Bevezetés a programozáshoz (Fóthi Ákos)
1. Alapfogalmak
1.1Halmazok
1.2Sorozatok
1.3Relációk
1.3.1Műveletek
1.3.2Logikai relációk
1.4Direktszorzat
1.5Függvényterek
1.6Példák
1.7Feladatok
2. A programozás alapfogalmai
2.1Az állapottér fogalma
2.2A feladat
2.3A program
2.4A programfüggvény
2.5Megoldás
2.6Programozási feladat
2.7Példák
2.8Feladatok
3. Specifikáció
3.1A leggyengébb előfeltétel
3.2A feladat specifikációja
3.3A változó fogalma
3.4Példák
3.5Feladatok
4. Kiterjesztések
4.1A feladat kiterjesztése
4.2A program kiterjesztése
4.3Kiterjesztési tételek
4.4A megoldás fogalmának kiterjesztése
4.5A feladat kiterjesztése és a specifikáció tétele
4.6Példák
4.7Feladatok
5. A típus
5.1A típusspecifikáció
5.2A típus
5.3A típusspecifikáció tétele
5.4Példák
5.5Feladatok
6. Elemi programok
6.1Feladatok
7. Programkonstrukciók
7.1Megengedett konstrukciók
7.2A programkonstrukciók programfüggvénye
7.3Levezetési szabályok
7.4Példák
7.5Feladatok
7.6A programkonstrukciók és a kiszámíthatóság
7.6.1Parciális rekurzív függvények
7.6.2A parciális rekurzív függvények kiszámítása
7.6.3Következmény
7.6.4Relációk
8. Típuskonstrukciók
8.1A megengedett konstrukciók
8.2Szelektorfüggvények
8.3Az iterált specifikációs függvényei
8.4A függvénytípus
8.5A típuskonstrukciók típusműveletei
II. Programozási módszertan (Fóthi Ákos)
9. Alapvető programozási tételek
9.1Összegzés
9.2Számlálás
9.3Maximumkeresés
9.4Feltételes maximumkeresés
9.5Lineáris keresés
9.6Logaritmikus keresés
10. Függvényérték kiszámítása
10.1Függvénykompozícióval adott függvény kiszámítása
10.2Esetszétválasztással adott függvény kiszámítása
10.3Rekurzív formulával adott függvény kiszámítása
10.4Elemenként feldolgozható függvény
10.4.1Egyváltozós-egyértékű eset
10.4.2Kétváltozós-egyértékű eset
10.4.3Egyváltozós kétértékű eset
10.4.4Általános változat
11. Visszalépéses keresés
12. Programtranszformációk
12.1Koordináta transzformációk
12.1.1Típustranszformációk
12.2Állapottér transzformáció
12.3Egyszerű programtranszformációk
Nem megengedett feltétel kitranszformálása elágazásból
Nem megengedett ciklusfeltétel kitranszformálása
Szimultán értékadás helyettesítése egyszerű értékadásokkal
Szekvencia sorrendjének felcserélése
Ciklusmag-beli szekvencia sorrendjének felcserélése
Függvény helyettesítése változóval
Rekurzívan definiált függvény helyettesítése
13. Szekvenciális megfelelő
14. Programinverzió
14.1Egyváltozós eset
14.2Kétváltozós eset
15. Időszerűsítés
15.1Az időszerűsítés definíciója
15.2Időszerűsítés egyértelmű módosítófile-lal
15.2.1Visszavezetés halmazok uniójára
15.2.2Visszavezetés kétváltozós elemenkénti feldolgozásra
15.3Időszerűsítés nem egyértelmű módosítófile-lal
15.3.1Megoldás adatabsztrakcióval
III. Párhuzamos és elosztott programozás (Horváth Zoltán)
16. Előszó
17. Bevezetés
Az egyes fejezetekről
18. Gyakran használt jelölések
19. A relációs modell alapfogalmai
19.1.Feladat: étkező filozófusok
19.2.Absztrakt program: rendezés
19.3.A relációs modell alapfogalmai
20. A feladat fogalmának általánosítása
20.1.Specifikációs feltételek
20.2.A programozási feladat definíciója
20.3. Feladat kiterjesztése
20.4.A feladat finomítása
21. Párhuzamos absztrakt program
21.1.Az absztrakt program szerkezete
21.1.1.A feltételes értékadás fogalma
21.2.Állapotátmenetfák
21.2.1.Utasítások kiterjesztése, szuperpozíciója
21.2.2.Program kiterjesztése
21.3.Pártatlan ütemezés fogalma
21.4.Az absztrakt program tulajdonságai
21.4.1.A leggyengébb előfeltétel és általánosítása
21.4.2.Invariánsok és elérhető állapotok
21.4.3.Biztonságossági tulajdonságok
21.4.4.Haladási tulajdonságok
21.4.5.Fixpont tulajdonságok
21.4.6.Terminálási tulajdonságok
21.5.Az absztrakt program viselkedési relációja
21.6.Feladatok
22. A megoldás fogalma
22.1.A megoldás definíciója
22.2.Átmenetfeltételek
22.2.1.Biztonságossági feltételek
22.2.2.Haladási feltételek
22.3.Peremfeltételek
22.3.1.Fixpont feltételek
22.4.Megoldás invariáns tulajdonság mellett
22.5.A megoldás definíciójának vizsgálata
23. Levezetési szabályok
23.1.Biztonságossági feltételek finomítása
23.2.Haladási feltételek finomítása
23.3.Feladatok
24. Programkonstrukciók
24.1.Unió
24.2.Szuperpozíció
24.3.Szekvencia
25. A modell tulajdonságai
25.1.Szemantika
25.2.Kifejezőerő
25.2.1.Programhelyesség
26. Programozási tételek
26.1.Asszociatív művelet eredményének kiszámítása
26.1.1.A feladat specifikációja
26.1.2.A megoldás
26.1.3.Programtranszformáció
26.1.4.A specifikáció finomítása
26.1.5.A transzformált program
26.1.6.Hatékonyság és általánosság
26.2.Csatornaváltozók használata
26.3.Természetes számok generátora
26.4.Adatcsatorna tétele
26.5.Elemenként feldolgozható függvények
26.5.1.A feladat specifikációja
26.5.2.A megoldás
26.5.3.Teljesen diszjunkt felbontás párhuzamos előállítása
26.5.4.Diszjunkt halmazok uniója
26.5.5.A párhuzamos elemenkénti feldolgozás tétele
26.5.6.Hatékonyság és általánosság
26.6.Feladatok
26.7.Természetes számok generátora
26.8.Adatcsatorna tétele
27. Modellek és tulajdonságaik
27.1.Szemantikai modellek
28. Irodalmi áttekintés
28.1.A Hoare logika kiterjesztései
Interferenciamentesség bizonyítása
Globális invariánsok bevezetése
28.2.Egy reláció alapú modell
28.3.Folyamatok viselkedésének algebrai leírása
Trace-ek
Címkézett átmenetrendszerek
CSP
28.4.Temporális logikai modellek
28.5.További modellek
29. Matematikai eszközök
29.1.Temporális logika
29.1.1.Elágazó idejű temporális logika
29.1.2.Lineáris temporális logika alapműveletei
29.2. Leképezések fixpontja
29.2.1.Parciális rendezés, irányított halmaz
29.2.2.Teljes hálók
29.2.3.Monoton leképezések tulajdonságai, fixpontok
30. Összefoglalás
A. Absztrakt programok megvalósítása C/PVM-ben
B. Fontosabb tételek és lemmák
C. Absztrakt programok
31. Irodalomjegyzék

Az ábrák listája

7.1.
7.2.
19.1.
19.2.
20.1.
20.2.
21.1.
21.2.
21.3.
21.4.
26.1.
26.2.
26.3.
26.4.
26.5.
26.6.
26.7. 26.6. ábra. Adatcsatorna
26.8. 26.7. ábra. Elemenkénti feldolgozás
26.9.
26.10. 26.9. ábra. Párhuzamos páronként teljesen diszjunkt felbontás
26.11.
26.12. 26.10. ábra. Természetes számok generátora.
26.13. 26.11. ábra. Adatcsatorna
26.14.

Az egyenletek listája

1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
1.0.
2.0.
2.0.
2.0.
2.0.
2.0.
2.0.
2.0.
2.0.
2.0.
2.0.
2.0.
2.0.
2.0.
2.0.
2.0.
2.0.
2.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
3.0.
4.0.
4.0.
4.0.
4.0.
4.0.
4.0.
4.0.
4.0.
4.0.
4.0.
4.0.
4.0.
4.0.
4.0.
4.0.
4.0.
4.0.
4.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
5.0.
6.0.
6.0.
6.0.
6.0.
6.0.
6.0.
6.0.
6.0.
6.0.
6.0.
6.0.
6.0.
6.0.
6.0.
6.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
7.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
8.0.
9.0.
9.0.
9.0.
10.0.
10.0.
10.0.
10.0.
10.0.
10.0.
10.0.
10.0.
10.0.
11.0.
11.0.
12.0.
12.0.
12.0.
12.0.
12.0.
13.0.
13.0.
13.0.
13.0.
13.0.
13.0.
13.0.
13.0.
13.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
15.0.
20.0.
20.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
23.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
26.0.
   Következő
   I. rész - Bevezetés a programozáshoz (Fóthi Ákos)