Projektowanie oprogramowania Wstep do programowania i techniki komputerowej.pdf

(484 KB) Pobierz
IDZ DO
PRZYK£ADOWY ROZDZIA£
SPIS TRE CI
KATALOG KSI¥¯EK
KATALOG ONLINE
ZAMÓW DRUKOWANY KATALOG
Projektowanie
oprogramowania.
Wstêp do programowania
i techniki komputerowej
Autorzy: Matthias Felleisen, Robert Bruce Findler,
Matthew Flatt, Shriram Krishnamurthi
T³umaczenie: Bartosz Grabski, Miko³aj Szczepaniak
ISBN: 83-7197-922-3
Tytu³ orygina³u:
How to Design Programs
Format: B5, stron: 644
Przyk³ady na ftp: 32 kB
Umiejêtno æ programowania nie ma ju¿ charakteru czysto zawodowego. Ksiêgowi
musz¹ siê pos³ugiwaæ arkuszami kalkulacyjnymi i edytorami tekstu, fotografowie
korzystaj¹ z edytorów zdjêæ, muzycy programuj¹ syntezatory, za profesjonalni
programi ci tworz¹ skomplikowane aplikacje. Programowanie jest wiêc bardzo
po¿¹dan¹ umiejêtno ci¹, potrzebn¹ nie tylko informatykom. Projektowanie
oprogramowania wymaga takich samych zdolno ci analitycznych, jak matematyka.
Jednak, w przeciwieñstwie do matematyki, praca z programami jest aktywnym
sposobem zdobywania wiedzy. Obcowanie z oprogramowaniem daje mo¿liwo æ sta³ej
interakcji, co pozwala na zg³êbianie wiedzy, eksperymentowanie z ni¹ oraz na sta³¹
samoocenê.
Autorzy tej klasycznej publikacji stawiaj¹ tezê, i¿ „ka¿dy powinien nauczyæ siê, jak
projektowaæ oprogramowanie” i w³a nie nauka podstaw projektowania jest jej tematem
g³ównym. W ksi¹¿ce znajdziesz wiele podstawowych algorytmów, wyja nienia takich
pojêæ, jak akumulacja wiedzy czy równo æ ekstensjonalna i intensjonalna, s³owem
wszystko to, co stanowi teoretyczn¹ podstawê wiedzy programistycznej.
Poznasz miêdzy innymi:
• Podstawowe struktury, z których sk³adaj¹ siê programy komputerowe
• Proste i z³o¿ony typy danych
• Metody przetwarzania danych
• Programowanie z u¿yciem rekurencji, algorytmy z nawracaniem
• Projektowanie abstrakcyjne
• Sposoby gromadzenia wiedzy
• Wykorzystanie wektorów
TWÓJ KOSZYK
DODAJ DO KOSZYKA
CENNIK I INFORMACJE
ZAMÓW INFORMACJE
O NOWO CIACH
ZAMÓW CENNIK
CZYTELNIA
FRAGMENTY KSI¥¯EK ONLINE
Wydawnictwo Helion
ul. Chopina 6
44-100 Gliwice
tel. (32)230-98-63
e-mail: helion@helion.pl
Z lektury ksi¹¿ki „Projektowanie oprogramowania. Wstêp do programowania i techniki
komputerowej” skorzystaj¹ zarówno studenci informatyki, jak te¿ i s³uchacze innych
kierunków oraz wszystkie osoby, które chc¹ podbudowaæ swoj¹ wiedzê praktyczn¹
solidnymi i przydatnymi podstawami teoretycznymi.
Spis treści
Przedmowa ............................................................................................................9
Dlaczego każdy powinien uczyć się programować? .................................................................... 11
Metody projektowania ....................................................................................................................... 12
Wybór Scheme i DrScheme ............................................................................................................... 14
Podział książki..................................................................................................................................... 15
Podziękowania .................................................................................................................................... 18
Część I Przetwarzanie prostych typów danych
1.
2.
19
Studenci, nauczyciele i komputery..........................................................21
Liczby, wyrażenia i proste programy .....................................................23
Liczby i arytmetyka ............................................................................................................................ 23
Zmienne i programy .......................................................................................................................... 26
Problemy ze zrozumieniem treści zadań ........................................................................................ 29
Błędy...................................................................................................................................................... 30
Projektowanie programów................................................................................................................ 33
3.
Program składa się z funkcji i definicji zmiennych ..............................39
Składanie funkcji................................................................................................................................. 40
Definicje zmiennych ........................................................................................................................... 43
Proste ćwiczenia w tworzeniu funkcji............................................................................................. 44
4.
Instrukcje warunkowe i funkcje...............................................................47
Wartości logiczne i relacje ................................................................................................................. 47
Funkcje testujące warunki ................................................................................................................. 50
Warunki i funkcje warunkowe ......................................................................................................... 54
Projektowanie funkcji warunkowych.............................................................................................. 57
5.
6.
Informacje symboliczne.............................................................................63
Proste ćwiczenia z symbolami.......................................................................................................... 65
Dane złożone. Część 1.: Struktury ...........................................................69
Struktury .............................................................................................................................................. 69
Ćwiczenie rozszerzone: rysowanie prostych obrazów .................................................................... 72
4
SPIS TREŚCI
Definicje struktur ................................................................................................................................ 75
Definicje danych.................................................................................................................................. 79
Projektowanie funkcji przetwarzających dane złożone .................................................................... 82
Rozszerzone ćwiczenie: przemieszczanie okręgów i prostokątów ............................................ 87
Rozszerzone ćwiczenie: gra w szubienicę ...................................................................................... 91
7.
Rodzaje danych...........................................................................................95
Mieszanie i rozróżnianie danych ..................................................................................................... 95
Projektowanie funkcji przetwarzających dane mieszane ........................................................... 100
Składanie funkcji — powtórka ....................................................................................................... 104
Rozszerzone ćwiczenie: przesuwanie figur.................................................................................. 107
Błędne dane wejściowe .................................................................................................................... 108
W1. Składnia i semantyka ...............................................................................111
Słownictwo języka Scheme ............................................................................................................. 112
Gramatyka języka Scheme .............................................................................................................. 112
Znaczenie w języku Scheme ........................................................................................................... 114
Błędy ........................................................ ...........................................................................................118
Wyrażenia logiczne .......................................................................................................................... 121
Definicje zmiennych ......................................................................................................................... 122
Definicje struktur .............................................................................................................................. 124
Część II Przetwarzanie danych dowolnej wielkości 127
9.
Dane złożone. Część 2.: Listy .................................................................129
Listy .....................................................................................................................................................129
Definicje danych dla list o dowolnej długości ............................................................................. 133
Przetwarzanie list o dowolnej długości ........................................................................................ 135
Projektowanie funkcji dla rekursywnych definicji danych........................................................ 139
Więcej na temat przetwarzania prostych list ............................................................................... 142
10. Więcej na temat przetwarzania list........................................................147
Funkcje zwracające listy................................................................................................................... 147
Listy zawierające struktury ............................................................................................................. 152
Rozszerzone ćwiczenie: przemieszczanie obrazów .................................................................... 158
11. Liczby naturalne .......................................................................................161
Definiowanie liczb naturalnych...................................................................................................... 161
Przetwarzanie liczb naturalnych dowolnej wielkości................................................................. 163
Rozszerzone ćwiczenie: tworzenie list, testowanie funkcji........................................................ 166
Alternatywne definicje danych dla liczb naturalnych .................................................................. 168
Więcej o naturze liczb naturalnych................................................................................................ 173
12. Łączenie funkcji. Powtórka.....................................................................177
Projektowanie skomplikowanych programów ............................................................................ 177
Rekursywne funkcje zewnętrzne ................................................................................................... 178
Uogólnianie problemów i funkcji................................................................................................... 183
Rozszerzone ćwiczenie: przestawianie słów ................................................................................ 187
W2. Skracanie list .............................................................................................191
SPIS TREŚCI
5
Część III Więcej o przetwarzaniu danych
dowolnej wielkości
197
14. Więcej rekurencyjnych definicji danych ...............................................199
Struktury w strukturach .................................................................................................................. 199
Rozszerzone ćwiczenie: drzewa poszukiwań binarnych ........................................................... 208
Listy w listach.................................................................................................................................... 212
Rozszerzone ćwiczenie: obliczanie wyrażeń języka Scheme..................................................... 215
15. Wzajemne odwołania w definicjach danych........................................217
Listy struktur. Listy w strukturach................................................................................................ 217
Projektowanie funkcji dla definicji danych zawierających wzajemne odwołania ................. 223
Rozszerzone ćwiczenie: więcej na stronach WWW..................................................................... 225
16. Tworzenie programów metodą iteracyjnego ulepszania...................227
Analiza danych.................................................................................................................................. 228
Definiowanie i ulepszanie klas danych......................................................................................... 229
Ulepszanie funkcji i programów .................................................................................................... 232
17. Przetwarzanie dwóch skomplikowanych elementów danych .........235
Jednoczesne przetwarzanie dwóch list. Przypadek 1. ................................................................. 235
Jednoczesne przetwarzanie dwóch list. Przypadek 2. ................................................................. 237
Jednoczesne przetwarzanie dwóch list. Przypadek 3. ................................................................. 240
Upraszczanie funkcji ........................................................................................................................ 245
Projektowanie funkcji pobierających dwie złożone dane wejściowe ....................................... 247
Ćwiczenia z przetwarzania dwóch złożonych danych wejściowych....................................... 248
Rozszerzone ćwiczenie: obliczanie wyrażeń języka Scheme. Część 2. .................................... 251
Równość i testowanie....................................................................................................................... 253
W3. Lokalne definicje i zasięg leksykalny ....................................................261
Organizowanie programów za pomocą słowa local................................................................... 261
Zasięg leksykalny i struktura blokowa ......................................................................................... 276
Część IV Projektowanie abstrakcyjne
281
19. Podobieństwa w definicjach ...................................................................283
Podobieństwa w funkcjach.............................................................................................................. 283
Podobieństwa w definicjach danych ............................................................................................. 292
20. Funkcje są wartościami............................................................................297
Składnia i semantyka ....................................................................................................................... 297
Kontrakty dla abstrakcyjnych i polimorficznych funkcji ........................................................... 299
21. Projektowanie funkcji abstrakcyjnych na podstawie przykładów...303
Abstrahowanie na podstawie przykładów................................................................................... 303
Ćwiczenia z abstrakcyjnymi funkcjami przetwarzającymi listy ............................................... 309
Abstrakcja i pojedynczy punkt kontroli........................................................................................ 311
Rozszerzone ćwiczenie: przemieszczanie obrazów jeszcze raz ................................................ 312
Uwaga: Projektowanie abstrakcji na podstawie szablonów ...................................................... 314
6
SPIS TREŚCI
22. Projektowanie abstrakcji .........................................................................317
Funkcje zwracające funkcje ............................................................................................................. 317
Projektowanie abstrakcji z funkcjami jako wartościami............................................................. 319
Pierwsze spojrzenie na graficzny interfejs użytkownika ........................................................... 322
23. Przykłady matematyczne........................................................................331
Ciągi i szeregi .................................................................................................................................... 331
Ciągi i szeregi arytmetyczne ........................................................................................................... 333
Ciągi i szeregi geometryczne .......................................................................................................... 334
Pole powierzchni pod wykresem funkcji...................................................................................... 338
Nachylenie funkcji ............................................................................................................................ 340
W4. Bezpośrednie definiowanie funkcji .......................................................345
Część V Rekursja generatywna
351
25. Nowa postać rekursji ...............................................................................353
Modelowanie kuli na stole .............................................................................................................. 354
Szybkie sortowanie........................................................................................................................... 357
26. Projektowanie algorytmów.....................................................................363
Zakończenie ....................................................................................................................................... 365
Rekursja strukturalna a generatywna............................................................................................ 368
Dokonywanie wyborów .................................................................................................................. 369
27. Różne algorytmy rekurencyjne ..............................................................375
Fraktale ............................................................................................................................................... 375
Od plików do linii, od list do list list............................................................................................. 380
Wyszukiwanie binarne .................................................................................................................... 384
Metoda Newtona .............................................................................................................................. 390
Rozszerzone ćwiczenie: eliminacja Gaussa .................................................................................. 392
28. Algorytmy z nawracaniem .....................................................................397
Przechodzenie grafów...................................................................................................................... 397
Rozszerzone ćwiczenie: szachowanie hetmanów........................................................................ 403
W5. Koszt obliczeniowy oraz wektory .........................................................405
Czas konkretny, czas abstrakcyjny ................................................................................................ 405
Definicja wyrażenia „rzędu”........................................................................................................... 410
Pierwsze spojrzenie na wektory..................................................................................................... 412
Część VI Gromadzenie wiedzy
423
30. Utrata wiedzy ...........................................................................................425
Problem przetwarzania strukturalnego ........................................................................................ 425
Problem rekursji generatywnej....................................................................................................... 429
31. Projektowanie funkcji z akumulatorem................................................433
Czy akumulator jest potrzebny? .................................................................................................... 433
Funkcje z akumulatorem ................................................................................................................. 434
Przekształcanie funkcji na funkcje z akumulatorem................................................................... 436

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin