wpf.pdf

(4477 KB) Pobierz
Wstęp do programowania
(potok funkcyjny)
Marcin Kubica
2017/2018
Spis treści
Wstęp
Podstawy języka programowania
Dekompozycja problemu, weryfikacja rozwiązania
Struktury danych
Moduły
Procedury wyższych rzędów jako abstrakcje konstrukcji programistycznych
Procedury wyższych rzędów i listy
Model obliczeń
Analiza kosztów
5
15
30
38
62
75
86
103
115
Zasada „dziel i rządź” i analiza złożoności na przykładzie algorytmów sortowa-
nia
132
Zasada „dziel i rządź” i analiza złożoności na przykładzie algorytmów sortowa-
nia, c.d.
140
Funktory
Programowanie imperatywne
Imperatywne wskaźnikowe struktury danych
Logika Hoare’a — dowodzenie poprawności programów imperatywnych
Przeszukiwanie grafów
Back-tracking
152
161
173
190
200
213
1
Technika spamiętywania
Programowanie dynamiczne
Kody Huffmana i algorytmy zachłanne
Algorytmy zachłanne c.d.
Algorytm mini-max
Gry typu wygrana/przegrana i drzewa AND-OR
Wyszukiwanie wzorców
Tablica sufiksowa
Procedury dużo wyższych rzędów
Strumienie
Programowanie obiektowe
Co jeszcze?
225
229
241
249
256
267
273
279
281
290
300
304
2
Kilka słów na początek
0.1
Programowanie funkcyjne vs. imperatywne
Cel jaki chcemy osiągnąć za pomocą programu możemy opisać za pomocą pojęć z dziedziny al-
gorytmicznej, jako funkcje/relacje między danymi, a wynikami. Tak więc nasz cel jest pewnym
tworem matematycznym. Do osiągnięcia tego celu możemy podejść na dwa sposoby:
Imperatywnie:
Dane są to pewne przedmioty, na których należy wykonywać określone czyn-
ności, w wyniku których przeistoczą się one w wyniki. Podejście to bierze się stąd, że
zwykle dane i wyniki modelują elementy otaczającego nas świata, a ten składa się z
przedmiotów i zachodzą w nim zdarzenia. W tym podejściu mówimy procesom, jakie
czynności mają kolejno wykonywać.
Funkcyjnie:
Zarówno podstawowe pojęcia i typy, jak i nasz cel są pojęciami matematycz-
nymi. Nasze programy opisują, jak z prostszych pojęć matematycznych konstruować
bardziej skomplikowane, aż uda nam się skonstruować matematyczny obiekt odpowia-
dający naszemu celowi. Ponieważ często konstruujemy tu różnego rodzaju funkcje —
stąd nazwa.
Stosując podejście funkcyjne łatwiej uzyskać pewność, że osiągniemy zamierzony cel, choć nie
zawsze łatwo uzyskać efektywny program.
Charakterystyczne dla programowania funkcyjnego jest również to, że funkcje są „obywa-
telami pierwszej kategorii”, tzn. przysługują im wszystkie te prawa, co innym wartościom. W
tej chwili nie jest jeszcze jasne o jakie prawa może chodzić. Można jednak śmiało powiedzieć,
że jest to jedna z fundamentalnych zasad programowania funkcyjnego.
0.2
Dwa potoki: imperatywny i funkcyjny
Dlaczego funkcyjnie? Nie chcemy nauczyć Państwa języka programowania, ale pewnych tech-
nik tworzenia programów. Stosując programowanie funkcyjne odrywamy niektórych z Państwa
od już nabytych złych nawyków. Jest to nieustający eksperyment — coroczny.
Jeśli nie jesteś pewien swoich sił lub nie programowałeś wcześniej w żadnym języku impe-
ratywnym, lepiej wybierz potok imperatywny. Jeśli znasz Pascala, C lub C++, to programo-
wanie funkcyjne może być ciekawsze.
0.3
Kwestie organizacyjne
•
Zasady zaliczenia — 2–3 kolokwia + laboratorium + ew. egzamin pisemny.
•
Zadania z kolokwiów i egzaminów z lat poprzednich zostały umieszczone w niniejszym
skrypcie, choć nie zostało to w żaden szczególny sposób zaznaczone.
0.4
Podziękowania
Niniejsze materiały powstały na podstawie notatek do prowadzonych przeze mnie, na prze-
strzeni kilku lat, wykładów ze Wstępu do programowania i Metod programowania (potok
funkcyjny). Chciałbym gorąco podziękować moim kolegom, którzy w tym czasie prowadzili
ćwiczenia z tych przedmiotów: Jackowi Chrząszczowi, Bogusławowi Kluge, Mikołajowi Konar-
skiemu, Łukaszowi Lwowi, Robertowi Maronowi i Kubie Pawlewiczowi. Ich uwagi i propozycje
3
miały wpływ na postać prowadzonych zajęć, a więc i również na te materiały. W szczególności
część zamieszczonych tu zadań pochodzi od nich.
Szczególnie chciałbym podziękować Piotrowi Chrząstowskiemu, który prowadził równolegle
ze mną wykłady ze Wstępu do programowania i Metod programowania dla potoku imperatyw-
nego. Współpracując ze sobą wymienialiśmy się różnymi pomysłami. Tak więc podobieństwo
pewnych elementów materiałów do naszych wykładów jest nie tylko nieuniknione, ale wręcz
zamierzone. W szczególności, niektóre zamieszczone tutaj zadania pochodzą z materiałów
opracowanych przez Piotra i umieszczonych w portalu:
http://wazniak.mimuw.edu.pl.
Podziękowania należą się również Krzysztofowi Diksowi, za to, że nakłonił mnie do prze-
tłumaczenia na język polski książki H. Abelsona i G. J. Sussmana,
Struktura i interpretacja
programów komputerowych.
Książka ta była punktem wyjścia przy opracowywaniu programu
zajęć na potoku funkcyjnym, w pierwszych latach jego istnienia. Jej dogłębne poznanie dało
mi dobre podstawy do poprowadzenia wykładów. Na koniec chciałbym podziękować mojej
żonie Agnieszce, za to, że wytrzymała ze mną gdy tłumaczyłem wspomnianą książkę.
0.5
Literatura
•
[HA02] H. Abelson, G. J. Sussman,
Struktura i interpretacja programów komputerowych,
WNT 2002.
•
[Ler] X. Leroy,
The Objective Caml system,
http://caml.inria.fr/pub/docs/manual-ocaml/index.html.
•
[Kub] M. Kubica,
Programowanie funkcyjne,
notatki do wykładu,
http://wazniak.mimuw.edu.pl/index.php?title=Programowanie_funkcyjne.
•
[CMP] E. Chailloux, P. Manoury, B. Pagano,
Developing Applications with Objective
Caml,
http://caml.inria.fr/pub/docs/oreilly-book/.
•
[Ben08] J. Bentley,
Perełki Oprogramowania,
WNT 2008.
4
Wykład 1. Wstęp
1.1
Programowanie jako dziedzina magii
Wbrew powszechnie panującym opiniom programowanie jest gałęzią magii. W „Nowej ency-
klopedii powszechnej PWN” możemy znaleźć następujące określenie magii: „zespół działań, za-
sadniczo pozaempirycznych, symbolicznych, których celem jest bezpośrednie osiągnięcie [. . . ]
pożądanych skutków [. . . ]”. Wyróżniamy przy tym następujące składniki działań magicznych:
•
zrytualizowane działania (manipulacje),
•
materialne obiekty magiczne (amulety, eliksiry itp.),
•
reguły obowiązujące przy praktykach magicznych (zasady czystości, reguły określające
czas i miejsce rytuałów),
•
formuły tekstowe mające moc sprawczą (zaklęcia).
Programowanie mieści się w ramach ostatniego z powyższych punktów. Programy kompute-
rowe są zapisanymi w specjalnych językach (zwanymi językami programowania) zaklęciami.
Zaklęcia te są przeznaczone dla specjalnego rodzaju duchów żyjących w komputerach, zwa-
nych procesami obliczeniowymi. Ze względu na to, że komputery są obecnie produkowane
seryjnie, stwierdzenie to może budzić kontrowersje. Zastanówmy się jednak chwilę, czym cha-
rakteryzują się duchy. Są to obiekty niematerialne, zdolne do działania. Procesy obliczeniowe
ewidentnie spełniają te warunki: nie można ich dotknąć ani zobaczyć, nic nie ważą, a można
obserwować skutki ich działania, czy wręcz uzyskać od nich interesujące nas informacje.
Nota bene, w trakcie zajęć można się spotkać również z przejawami pozostałych wymie-
nionych składników działań magicznych. „Logowanie” się do sieci oraz wyłączanie komputera
to działania o wyraźnie rytualnym charakterze. Przedmioty takie jak indeks, czy karta zali-
czeniowa wydają się mieć iście magiczną moc.
W trakcie zajęć z tego przedmiotu zajmiemy się podstawowymi zasadami formułowania
zaklęć/programów, a także związkami łączącymi zaklinającego (programistę), program i pro-
ces obliczeniowy. W szczególności zajmiemy się również analizą sposobu, w jaki procesy
obliczeniowe realizują programy oraz metodami upewniania się, że programy realizują zamie-
rzone cele. Będziemy jednak pamiętać, że zaklęcia są przeznaczone dla procesów żyjących w
komputerze, stąd będziemy je wyrażać w języku programowania
Ocaml.
Nie jest to jednak
kurs programowania w tym języku, lecz kurs podstawowych zasad formułowania zaklęć dla
procesów obliczeniowych.
1.2
Kilka podstawowych pojęć
Jako adepci magii związanej z zaklinaniem procesów obliczeniowych będziemy nazywać siebie
informatykami.
W naszych działaniach będziemy sobie stawiać
cele,
które chcemy osiągnąć
i, używając rozumu, będziemy formułować zaklęcia mające zmusić procesy obliczeniowe do
doprowadzenia do postawionych celów oraz upewniać się, że cele te będą osiągnięte. For-
mułowane zaklęcia będziemy nazywać
programami,
a ich formułowanie
programowaniem.
Upewnianie się, co do skutków zaklęć będziemy nazywać
weryfikacją
programów.
Pro-
cesy obliczeniowe
nie są zbyt inteligentnymi duchami, za to są bardzo szybkie. Dlatego
też programy muszą szczegółowo opisywać czynności, jakie mają wykonać te duchy. Sposób
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin