Download 35251231 Programski Jezici i Strukture Podataka Dusan Malbaski PDF

Title35251231 Programski Jezici i Strukture Podataka Dusan Malbaski
File Size668.9 KB
Total Pages137
Table of Contents
                            Dobra upotreba identifikatora eliminiše najveći deo potrebe za komentarima.
Ovaj tip ima dve logičke vrednosti: tačno i netačno.
	Važno!
false < true
	Dužina stringa se može unapred zadati ako ga deklarišemo pomoću:
	string[duzina]
	Datoteke se čuvaju takve kakve jesu dok se eksplicitno ne promene.
	Tekući elemenat je onaj na kojim se izršavaju procedure i funkcije.
	U Pascalu se za označavanje pokazivača koristio simbol , a u Turbo Pascalu se koristi ^.
	Konstante koje u programu imaju određeno značenje bi trebalo da budu imenovane.
Naredba dodele je dvoznak.
	Upravljačka promenljiva se zove i kontrolna promenljiva.
Naredbe skoka treba izbegavati.
	Da bi mogli koristiti Low() i High() prevodiocu moramo zadati direktivu {&P+}.
	U početku biblioteke nisu imale strukturu, predstavljale su skup neuređenih programa koji se koriste po potrebi.
Bez modula nema profesionalne izrade programa ni na jednom proceduralnom programskom jeziku.
Information Hiding Principle
	Šta se dešava sa ulazom i kako se transformiše u izlaz, klijenta se ne tiče.
	Potprogram nije modul, jer nije autonomno realizovan, već kao deo modula (tj. glavnog programa).
	Ukoliko se desi da deklarišemo neki potprogram u interfejsu, a ne realizujemo ga u implementaciji, prevodilac će nam prijaviti grešku.
	Ovog dela obično nema, jer ima vrlo specifičnu namenu.
	Izračunljive funkcije su one čija se vrednost može izračunati algoritmom.
	UTM se može svesti na specijalnu.
	Nizovi mogu biti statički i dinamički. Ovde ćemo se baviti statičkim nizovima.
	Niz čiji su elementi skalari jeste vektor, a niz vektora je matrica.
Deskriptor je obavezan!
	Dve bitne osobine slogova su semantička konvergencija i pitanje relacije.
	U prevodu, stack znači „naređana gomila“.
Četiri aspekta koje treba razjasniti prilikom programiranja
Hijerarhija operatora
Logički tip
	Logičke operacije
	Relacioni operatori
Celobrojni tip
	Operacije
	Funkcije
	Tipovi byte i word
	Bit operacije
Realni tip
	Operacije
	Funkcije
Znakovni tip
	Relacioni operatori
	Funkcije
String
	Operacije
Enumeracija
	Opšti oblik
	Operacije
Intervalni tip
	Opšti oblik
Nizovi
	Opšti oblik
Skupovi
	Opšti oblik
	Operacije
Slog
	Opšti oblik
	Dodela vrednosti
	Iterator with
Datoteke
	Tipizirana datoteka
	Tekstualna datoteka
	Netipizirana datoteka
Pokazivači
	Netipizirani pokazivači
	Tipizirani pokazivači
	Pokazivačka konstanta nil
Primer
	Globalna struktura programa
Zaglavlje
Deklaracije
	Labele
	Konstante
	Tipovi
	Promenljive
	Direktno zadavanje tipa
	Potprogrami
Algoritamski deo
Naredba dodele
Složena naredba (sekvenca)
Naredbe selekcije
	If then i if then else
	Case
Petlje
	For
	While
	Repeat
Naredbe skoka
	Deklaracija unapred
	Lokalne i globalne promenljive
	Formalni i stvarni parametri
	Parametri vrednosti i parametri imena
	Nizovi kao parametri potprograma
	Low() i High()
	Potprogrami kao parametri drugih potprograma
	Rekurzivni potprogrami
Moduli
Opšta struktura modula
	Šta se nalazi u modulu
Uniti u Turbo Pascalu
	Zaglavlje unita
	Interfejs
	Implementacija
	Inicijalizacija
Pascalovi gotovi uniti
Primer
	Kompajler generator
Bekus-Naurova forma – BNF
Poboljšana Bekus-Naurova forma – EBNF
Sintaksni dijagram
	Primeri
Šta je to algoritam?
Algoritamski sistemi
Rekurzivne funkcije
	Primer
	Specijalne Tjuringove mašine
	Formalna definicija Tjuringovih mašina
	Konfiguracija Tjuringove mašine
	Funkcije prelaza
	Univerzalne Tjuringove mašine
	Primer
	Definicija normalnih algoritama Markova
	Opšti oblik Markovljevih normalnih algoritama
	Sredstva za analizu algoritama
	Primer
Pravilni programi
	Pravilni potprogram
Analiza algoritama
Strukturna teorema i programiranje bez goto
	Minimalna baza strukturiranih programa
Metoda Aschroft-Manna
	Primer
Pisanje programa bez upotrebe skokova
	Primer
Pojam podatka
Značaj struktura podataka
Definicija strukture podataka
Grafovi
Operacije nad strukturama podataka
Klasifikacija struktura podataka
	Klasifikacija struktura podataka prema nivou apstrakcije
	Primer
	Klasifikacija struktura podataka prema mestu memorisanja
	Klasifikacija struktura podataka prema tipu relacije
Klasifikacija operativnih struktura
Nizovi
	Fizička realizacija
	Iliffeovi vektori
Slogovi
	Fizička realizacija
Tabele
Stek (stack)
	Fizička realizacija
	Primena
Red (queue)
	Fizička realizacija
	Primena
Dek (deque)
Sekvenca
	Fizička realizacija
Liste i dinamički nizovi
Stabla
	Stablo kao struktura podataka
	N-arna stabla
	Binarna stabla
	Obilazak binarnog stabla
	Fizička struktura
	Tehnika niti
	Sekvencijalna fizička realizacija
                        
Document Text Contents
Page 68

O S N O V I T E O R I J E A L G O R I T A M A

Ukupno stanje Tjuringove mašine je
određeno stanjem upravljačkog bloka
(q), aktuelnom reči na beskonačnoj
traci (α ) i položajem upisno-čitajuće
glave (i), tj. njenim rastojanjem od
početka aktuelne reči (redni broj slova
iznad kojeg se glava nalazi).

Funkcije prelaza
Funkcija prelaza se zadaje u vidu
pesudnonaredbe, npr: qa  q'a'.

Drugi način za njihovo zadavanje (ne
isključuje prvi) je u vidu funkcionalne
sheme. To je matrica koja po jednoj
dimenziji ima oznake stanja, a po
kolonama oznake iz spoljašnjeg
alfabeta. Na preseku se nalaze urđene
trojke (q', a, P).

Osnovna teza teorije algoritama sa
stanovišta Tjuringovih mašina kaže da
se svaki algoritam može zadati u obliku
funkcionalne sheme specijalne
Tjuringove mašine, tj. svaki algoritam
je jedna Tjuringova mašina.

Univerzalne Tjuringove mašine
Postavlja se pitanje možemo li
definisati Tjuringovu mašinu koja bi
mogla predstavljati svaki algoritam. To
je univerzalna Tjuringova mašina. Ima
tu osobinu da ne služi za izvršavanje
jednog algoritma, već svakog algoritma.
Funkcionalna shema se kodira, tako da
i ona postaje deo ulaza.

Univerzalne Tjuringove mašine na
ulazu imaju reč koju treba obraditi
zajedno sa uputstvom za njenu obradu.

U savremenim računarima, ova
uputstva zovemo programima.

Primer

• T = (Κ , Γ , Σ , δ , q0, F)

• Κ = {S1, S2, S3}

Page 69

O S N O V I T E O R I J E A L G O R I T A M A

• Γ = {0, 1, ε , B}

• Σ = {0, 1}

• q0 = S1

• F = {S3}

• funkcionalna shema ove
Tjuringove mašine je:

0 1 ε B
S
1

(S2, 0, R) (S2, 1, R) - -

S
2

(S2, 1, R) (S2, 0, R) - (S3, ε ,
R)

S
3

- - - -

Page 137

S T R U K T U R E P O D A T A K A

Prednost ovakve realizacije je u tome
što se adresa elementa može
izračunati unapred, pa je pristup
direktan.

Ovakav način realizacije se koristi za
statična stabla ili za ona koja se vrlo
malo proširuju (zbog vrlo lakog
prepunjavanja memorije).

Binarna stabla se retko realizuju
samostalno, već kao pomoćna
struktura nekih algoritama (npr.
algoritma sortiranja).

Similer Documents