gitweb on Svarog
projekti pod git sistemom za održavanje verzija -- projects under the git version control system
diff --git a/skripta-spa1.tex b/skripta-spa1.tex
--- a/skripta-spa1.tex
+++ b/skripta-spa1.tex
% osnovne informacije koje ce se prikazati na naslovnoj strani,
% kao i u informacijama u generisanom pdfu
\newcommand{\autor}{Vladimir Kurbalija, Milos Radovanovic, Doni Pracner}
-\newcommand{\naslov}{Skripta za vezbe iz predmeta strukture podataka
- i algoritmi 1}
-\newcommand{\datum}{April 2012, Novi Sad}
-\newcommand{\verzija}{ver 12b}
-%sc=single-column
+\newcommand{\naslov}{Skripta za vezbe iz predmeta "Strukture podataka
+ i algoritmi 1"}
+\newcommand{\datum}{Februar 2013, Novi Sad}
+\newcommand{\verzija}{ver 13a-jk}
+%jk=jedna kolona, dk=dve kolone
+
+\newcommand{\mainstart}{
+%\begin{multicols}{2}
+}
+
+\newcommand{\mainend}{
+%\end{multicols}
+}
+
\usepackage[serbian]{babel}
\usepackage{fancyhdr}
\pagestyle{fancy}
%change the default font
\usepackage{lmodern}
+\usepackage{beramono}
\renewcommand{\familydefault}{\sfdefault}
\usepackage{pifont}
}
\lstdefinestyle{codeblock}{
- basicstyle=\footnotesize,
+ basicstyle=\footnotesize\ttfamily,
keywordstyle=\textbf,
columns=[l]fixed,
breakatwhitespace=true,
\lstnewenvironment{codeblock}{\lstset{style=codeblock}}{}
+
% ----------------==================--------------------------------------
% Pravi pocetak rada
Programi u ovoj skripti su testirani sa kompajlerom 'Native XDS Modula
-2' sa instaliranim dodatnim paketom TSCP (Top Speed Compatibility
-Pack), potrebnim za neke od modula koji se ne nalaze u ISO standardu
-Module 2.
+2'. Za verzije pre 2.60 je neophodno dodatno instalirati i TSCP (Top
+Speed Compatibility Pack), pošto je potreban za neke od modula koji se
+ne nalaze u ISO standardu Module 2. U novijim verzijama su i ovi
+moduli uključeni u standardnu instalaciju.
+
+Sav sadržaj se može koristiti u skladu sa {\ttfamily CC-BY-NC-SA} licencom. \url{http://creativecommons.org/licenses/by-nc-sa/3.0/}
\tableofcontents
\newpage
-\begin{multicols}{2}
+\mainstart
+
\section{Ilustracija efikasnosti algoritma}
\subsection{Zadatak: Pronaći sve pitagorine
trojke do zadate granice}
+Pitagorina trojka su tri broja $a,b,c$ za koje važi $a^2 + b^2 = c^2\\$
\begin{lstlisting}[style=codeblock]
MODULE Trojke1;
END Trojke2.
\end{codeblock}
+Sledeći primer koristi Euklidovu teoremu i malo drugačiji pristup.
+Ako uzmemo neka dva prirodna broja $m$ i $n$, tada se iz njih može
+izvesti jedna Pitagorina trojka koja lako zadovoljava potrebne uslove:
+\[
+\begin{array}{l}
+a = 2mn\\
+b = m^2 - n^2\\
+c = m^2 + n^2
+\end{array}
+\]
+Odnosno kad probamo da proverimo da li je ovo
+Pitagorina trojka dobijamo:
+\[
+\begin{array}{r@=l}
+a^2 + b^2 & c^2\\
+(2mn)^2 + (m^2 - n^2)^2 & (m^2 + n^2)^2
+\end{array}
+\]
+
\begin{codeblock}
MODULE Trojke3;
(* Pitagorine trojke koriscenjem teoreme *)
END Trojke3.
\end{codeblock}
+Sledeća dva metoda traže trojke sa nekim specifičnim osobinama.
+
\begin{codeblock}
MODULE Trojke4;
(* Pitagorine trojke kod kojih je razlika
END MaxNiza4.
\end{codeblock}
+\section{Stringovi}
+
+
+Stringovi -- odnosno nizovi znakova -- ne postoje kao ugrađeni tip u
+jeziku Modula 2. Ovo daje slobodu da se niz znakova definiše na dužinu
+najadekvatniju za konkretnu primenu. U opštem slučaju definišemo npr:
+\begin{codeblock}
+ TYPE
+ String = ARRAY [1..30] OF CHAR;
+\end{codeblock}
+
+Operacije nad stringovima se najčešće uvoze iz modula \kod{Str}. One
+sve prihvataju \emph{otvorene nizove znakova} (strukture definisane sa
+\kod{ARRAY OF CHAR}), tako da im se može proslediti niz proizvoljne
+dužine.
+
+Određivanje stvarne dužine stringa (tj koliko od maksimalnog
+kapaciteta niza je zapravo zauzeto sadržajem) se može izvesti na
+sledeći način:
+\begin{codeblock}
+ duzina := Length(str)
+\end{codeblock}
+
+Leksikografsko poređenje dva stringa se ne može vršiti standardnim
+operatorima kao što su \kod{< > =}. Ovo je delom zato što se radi o
+nizovima, a delom i zato što se ne vidi direktno koji deo niza je
+popunjen stvarnim sadržajem. Za ovo se koristi komanda \kod{Compare},
+koja prihvata dva stringa kao parametre, a vraća broj koji predstavlja
+njihov odnos. Taj broj će biti 0 ako su stringovi jednaki, veći
+od nule ako je prvi string ``veći'', i manji od nule ako je prvi
+string ``manji''. Ovo se lako pamti kad primetimo da je odnos
+između \kod{Compare} i 0 isti kao i između prvog i drugog stringa.
+
+\begin{codeblock}
+ IF Compare(str1, str2) > 0 THEN
+ WriteString("Prvi string je veci");
+ ELSIF Compare(str1, str2) < 0 THEN
+ WriteString("Prvi string je manji");
+ ELSE (* moraju biti jednaki *)
+ WriteString("Jednaki su");
+ END;
+\end{codeblock}
+
+Postoji i modul \kod{Strings} koji ima nešto drugačije definisane
+procedure, no na njih se sada nećemo fokusirati.
+
\section{Rad sa fajlovima}
\subsection{Modul FIO}
U ovom modulu je definisan tip \kod{File}, koji predstavlja jedan fajl
-sa kojim radimo.
+sa kojim radimo. Da bi ga koristili moramo ga uvesti u program (isto
+kao što uvozimo i komande).
-U primerima se pretpostavlja da je „f“ tipa \kod{File}, „str“ niz
-znakova, „i“ tipa \kod{INTEGER}, „c“ tipa \kod{CARDINAL} i „ch“ tipa
-\kod{CHAR}. Dodatna promenljiva „n“ tipa \kod{INTEGER} služi za
+\begin{quote}U primerima se pretpostavlja da je ``f'' tipa \kod{File}, ``str'' niz
+znakova, ``i'' tipa \kod{INTEGER}, ``c'' tipa \kod{CARDINAL} i ``ch''
+tipa \kod{CHAR}. Dodatna promenljiva ``n'' tipa \kod{INTEGER} služi za
formatiranje slično kao u modulu \kod{InOut}.
+\end{quote}
Promenljiva tipa \kod{File} se mora vezati za neki fajl
-jednom od sledećih komandi:\\
-\kod{f := Open(str);} -- otvara se postojeci fajl za čitanje\\
-\kod{f := Create(str);} -- kreira se fajl za pisanje\\
-\kod{f := Append(str);} -- otvara se postojeći za dopisivanje na kraj
+jednom od sledećih komandi:
+\begin{itemize}
+\item \kod{f := Open(str);} -- otvara se postojeci fajl za čitanje\\
+\item \kod{f := Create(str);} -- kreira se fajl za pisanje\\
+\item \kod{f := Append(str);} -- otvara se postojeći fajl za
+ dopisivanje na kraj
+\end{itemize}
+
+Po završetku rada fajl se mora zatvoriti, u našem primeru to bi bilo
+\kod{Close(f);}
-\kod{Close(f);} -- po završetku rada fajl se mora zatvoriti
+Procedure za čitanje i pisanje su vrlo slične onima iz modula
+\kod{IO}, osim što imaju dodatni parametar „\kod{f}“ koji označava
+fajl sa kojim se radi.
+\begin{itemize}
+\item \kod{RdStr(f,str)} -- učitava ceo red u string str\\
+\item \kod{RdItem(f,str)} -- učitava jednu reč u string str (učitava znakove iz fajla dok ne naiđe na separator)\\
+\item \kod{i:= RdInt(f); c:= RdCard(f)} -- učitava broj, koji se dobija kao rezultat procedure\\
+\item \kod{ch:= RdChar(f)} -- vraća jedan znak iz fajla
+\end{itemize}
-Procedure za čitanje i pisanje imaju parametar „\kod{f}“ koji označava
- fajl sa kojim se radi.\\
-\kod{RdStr(f,str)} -- učitava ceo red u string str\\
-\kod{RdItem(f,str)} -- učitava jednu reč u string str (učitava znakove iz fajla dok ne naiđe na separator)\\
-\kod{i:= RdInt(f); c:= RdCard(f)} -- učitava broj, koji se dobija kao rezultat procedure\\
-\kod{ch:= RdChar(f)} -- vraća jedan znak iz fajla
+Analogne su i procedure za pisanje različitih tipova u fajl:
+\begin{itemize}
+\item \kod{WrStr(f,str); WrInt(f,i,n);}\ \kod{WrCard(f,c,n);}\
+ \kod{WrChar(f,ch);}
+\end{itemize}
-Procedure za pisanje različitih tipova u fajl:
-\kod{WrStr(f,str); WrInt(f,i,n); WrCard(f,c,n);WrChar(f,ch);}
-\kod{WrLn(f);} -- upisuje prelom reda u fajl
+Prelom reda se eksplicitno upisuje u fajl komandom \kod{WrLn(f);}.
-\kod{EOF} -- logička promenljiva, označava da li smo poslednjom
+Da bi odredili da li smo stigli do kraja fajla možemo koristiti
+\kod{EOF}. U pitanju je logička promenljiva koja se uvozi iz modula
+FIO kao bilo kakva normalna komanda. Ona označava da li smo poslednjom
operacijom čitanja stigli do kraja fajla. Ne menja joj se vrednost
pri operacijama otvaranja i zatvaranja fajlova, odnosno neće se pri
-tome resetovati na \kod{FALSE}.
-
+tome resetovati na \kod{FALSE}, pa na ovo treba obratiti pažnju pri
+radu.
\subsection{Zadatak: ispis sadržaja fajla na ekran}
\section{Liste i pokazivači}
-Za rad sa pokazivačima je potrebno iz modula Storage uvesti procedure
+Za rad sa pokazivačima je potrebno iz modula \kod{Storage} uvesti procedure
\kod{ALLOCATE} i \kod{DEALLOCATE}. U kodu se tada mogu koristiti i njihovi
skraćeni oblici \kod{NEW} i \kod{DISPOSE}.
liste osoba koje dele sadržaj, jedna sortirana po visini, druga po
težini}
-Sa tastature ucitavati po dva broja koji opisiuju osobu (visina i
-tezina) i smestati ih u povezane listu, tako da postoji neopadajuce
-uredjenje i po visini i po tezini.
+Sa tastature učitavati po dva broja koji opisuju osobu (visina i
+težina) i smeštati ih u povezane listu, tako da postoji neopadajuće
+uređenje i po visini i po težini.
\begin{lstlisting}[style=codeblock]
MODULE VisTez;
Polinomi su predstavljeni pomoću pokazivača. Apstraktni tip podataka
\kod{Polinom} je definisan u globalnom modulu.
+\paragraph{PolinomL.DEF} \
+
\begin{lstlisting}[style=codeblock]
DEFINITION MODULE PolinomL;
TYPE
PROCEDURE DisposePolinom(VAR p: Polinom);
END PolinomL.
-(* --- kraj definicionog modula --- *)
+\end{lstlisting}
+
+\paragraph{PolinomL.MOD} \
+\begin{codeblock}
+(* Modul za rad sa polinomima preko listi
+ verzija 2012, rev 1 *)
IMPLEMENTATION MODULE PolinomL;
FROM InOut IMPORT Write, WriteString, WriteLn,
WriteCard, ReadCard, Done;
PROCEDURE Anuliraj(VAR p: Polinom);
BEGIN
- IF p # NIL THEN
- DisposePolinom(p);
- END;
+ p := NIL;
END Anuliraj;
-PROCEDURE Kopiraj(p: Polinom;
- VAR kopija: Polinom);
+PROCEDURE Kopiraj(p: Polinom; VAR kopija: Polinom);
VAR
pomocni: Polinom;
BEGIN
END
END Stampaj;
-PROCEDURE UbaciMonom(mon :Polinom;
- VAR p: Polinom);
+PROCEDURE UbaciMonom(mon:Polinom; VAR p: Polinom);
VAR
stari, tekuci, kopija: Polinom;
BEGIN
ELSE
stari^.veza := kopija
END;
- IF (tekuci#NIL) AND
- (kopija^.st = tekuci^.st) THEN
+ IF (tekuci#NIL) AND (kopija^.st = tekuci^.st) THEN
kopija^.k := kopija^.k + tekuci^.k;
kopija^.veza := tekuci^.veza;
DISPOSE(tekuci);
NEW(novi);
WITH novi^ DO
REPEAT
- WriteString('koeficijent monoma br.');
+ WriteString('Unesite koeficijent monoma br.');
WriteCard(i, 1);
- WriteString(' (<> 0):');
+ WriteString(' (<> 0) ');
ReadReal(k);
WriteLn
UNTIL k <> 0.0;
REPEAT
WriteLn;
- WriteString('eksponent monoma br.');
+ WriteString('Unesite eksponent monoma br.');
WriteCard(i, 1);
- WriteString(' (>= 0): ');
+ WriteString(' (>=0) ');
ReadCard(st);
UNTIL Done;
WriteLn;
END
END Unos;
-PROCEDURE Saberi(p1, p2: Polinom;
- VAR zbir: Polinom);
+PROCEDURE Saberi(p1, p2: Polinom; VAR zbir: Polinom);
BEGIN
Kopiraj(p1, zbir);
WHILE p2 <> NIL DO
END
END Saberi;
-PROCEDURE SaberiNa(p: Polinom;
- VAR rez: Polinom);
+PROCEDURE SaberiNa(p: Polinom; VAR rez: Polinom);
BEGIN
WHILE p <> NIL DO
UbaciMonom(p,rez);
END
END PromeniZnak;
-PROCEDURE Oduzmi(p1,p2: Polinom;
- VAR razlika: Polinom);
+PROCEDURE Oduzmi(p1,p2: Polinom; VAR razlika: Polinom);
BEGIN
Kopiraj(p2, razlika);
PromeniZnak(razlika);
END
END Oduzmi;
-PROCEDURE MonomPuta(p, mon: Polinom;
- VAR mp: Polinom);
+PROCEDURE MonomPuta(p, mon: Polinom; VAR mp: Polinom);
VAR
tekuci: Polinom;
BEGIN
END
END Puta;
-PROCEDURE Kolicnik(p1, p2: Polinom;
- VAR kol, ost: Polinom;
- VAR ok: BOOLEAN);
+PROCEDURE Kolicnik(p1, p2: Polinom; VAR kol, ost: Polinom; VAR ok: BOOLEAN);
PROCEDURE Deli(VAR kol, ost: Polinom);
VAR
rez^.st := 0;
rez^.veza := NIL;
ELSIF n = 1 THEN
- Kopiraj( rez, p );
+ Kopiraj( p, rez );
ELSE
rez := p;
FOR i := 2 TO n DO
END DisposePolinom;
END PolinomL.
-\end{lstlisting}
+\end{codeblock}
\subsection{Zadatak: Sabiranje sa unapred određenim polinomom}
Prvo se prikazuje ugovor o korišćenju koji na dnu treba potvrditi da ste
razumeli i da ćete ga se pridržavati.
-Na stranici koja se potom otvara je potrebno odabrati sledeće pakete za
-download:
-
-* Native XDS-x86 2.51 for Windows (6.5MB)
-\url{http://www.excelsior-usa.com/download/xds25x/xds-x86-251-enduser-win32.exe}
-
-* TSCP add-on (2.4MB)
-\url{http://www.excelsior-usa.com/download/xds25x/tscp-x86-251-enduser-win32.exe}
+Na stranici koja se potom otvara je potrebno odabrati ``XDS 2.6 beta 2
+for Windows'' i snimiti je na računar.
\subsection*{Instalacija okruženja}
-Prvo treba instalirati osnovno okruženje (xds-x86...), a potom i Top
-Speed Compatibility Pack (tscp-x86...), koji je potreban za neke
-module koji se koriste.
+Osnovno okruženje (xds-x86...) se instalira pokretanjem prethodno pomenute
+ instalacione arhive.
\emph{Korisnicima Windows-a 7 preporučujemo da pokrenu instalacione
pakete pomoću opcije ``Run as administrator'' do koje se stiže desnim
Moguće je namestiti da u dijalogu za novi projekat drugo polje ``Template''
uvek bude prazno. Potrebno je u tom istom dijalogu kliknuti na
``Configure'', a potom isprazniti polje ``default template''.
-\end{multicols}
+
+\subsection{Mogući problemi}
+
+\subsubsection*{Nedostajući sistemski moduli}
+
+Verzije pre 2.6 nisu imale uključene u glavni paket sve module koji se
+koriste u okviru kursa, i bilo je neophodno da se dodatno instalira i
+``Top Speed Compatibility Pack'' (tscp-x86...). Bez njega je kompajler
+prijavljivao da ne postoje neki moduli - najčešće je problem bio da
+nedostaje \kod{FIO} modul.
+
+\subsubsection*{Problemi u pokretanju - nemoguće naći exe}
+
+Ako pri pokušaju kompajliranja/pokretanja programa kompajler prijavi
+da ne može da nađe exe i pri tome prijavljuje kraću putanju od one
+koja je stvarno u pitanju, obično se radi o tome da je postojao razmak
+u okviru putanje do modula. Npr ``C:\textbackslash Moj prvi program''
+će prouzrokovati probleme, a kompajler će prijaviti da ne može da nađe
+``C:\textbackslash Moj''.
+
+Ovo je nažalost problem okruženja i dok se ne ispravi u nekoj budućoj
+verziji ne može se zaobići, tako da je jedino rešenje premestiti
+fajlove, odnosno ako je moguće preimenovati problematične foldere.
+
+\mainend
\end{document}