Dane oryginału

Authorized translation from the English language edition, entitled Computer Science: An Overview, 13th Edition, by Glenn Brookshear and Dennis Brylow, published by Pearson Education, Inc, publishing as Pearson, Copyright © 2019 by Pearson Education, Inc., Hoboken, NJ 07030.

All rights reserved. No part of this book may be reproduced or transmitted in any form or by any means, electronic or mechanical, including photocopying, recording or by any information storage retrieval system, without permission from Pearson Education, Inc.

Polish language edition published by Polish Scientific Publishers PWN, Copyright © 2022.

Przekład: Magdalena Rogulska, Mariusz Rogulski na zlecenie WITKOM Witold Sikorski

Projekt okładki polskiego wydania na podstawie oryginału: INT-MEDIA Dawid Mazur

Wydawca: Wioleta Szczygielska-Dybciak

Redaktor prowadzący: Monika Zabrocka-Kutera

Redaktor: Małgorzata Dąbkowska-Kowalik

Koordynator produkcji: Anna Bączkowska

Skład wersji elektronicznej na zlecenie Wydawnictwo Naukowe PWN S.A.: Michał Latusek

Konsultant merytoryczny:

dr inż. Wiesław Półjanowicz

Zastrzeżonych nazw firm i produktów użyto w książce wyłącznie w celu identyfikacji.

Książka, którą nabyłeś, jest dziełem twórcy i wydawcy. Prosimy, abyś przestrzegał praw, jakie im przysługują. Jej zawartość możesz udostępnić nieodpłatnie osobom bliskim lub osobiście znanym. Ale nie publikuj jej w internecie. Jeśli cytujesz jej fragmenty, nie zmieniaj ich treści i koniecznie zaznacz, czyje to dzieło. A kopiując jej część, rób to jedynie na użytek osobisty.

Szanujmy cudzą własność i prawo

Więcej na www.legalnakultura.pl

Polska Izba Książki

Copyright © for the Polish edition by Wydawnictwo Naukowe PWN S.A.

Warszawa 2022

ISBN: 978-83-01-22296-3

eBook został przygotowany na podstawie wydania papierowego z 2022r. (Wydanie XIII (I w WN PWN))
Warszawa 2022

Wydawnictwo Naukowe PWN SA

02-460 Warszawa, ul. Gottlieba Daimlera 2

tel. 22 69 54 321, faks 22 69 54 288

infolinia 801 33 33 88

e-mail: pwn@pwn.com.pl, reklama@pwn.pl
www.pwn.pl

Bezpłatny fragment

Przedmowa

Związek 13. wydania książki Informatyka w ogólnym zarysie oraz wydania AP® z AP® Computer Science Principles Curriculum Framework

Rozdział 0. Wprowadzenie

0.1 Rola algorytmów

0.2 Historia informatyki

0.3 Zawartość książki

0.4 Nadrzędne zagadnienia informatyki

Rozdział 1. Przechowywanie danych

1.1 Bity i ich przechowywanie

1.2 Pamięć główna

1.3 Pamięć masowa

1.4 Przedstawianie informacji w postaci bitów

1.5. System binarny

1.6 Przechowywanie liczb całkowitych

1.7 Przechowywanie ułamków

1.8 Dane i programowanie

1.9 Kompresja danych

1.10 Błędy komunikacji

Rozdział 2. Operowanie danymi

2.1 Architektura komputera

2.2 Język maszynowy

2.3 Wykonywanie programu

2.4 Instrukcje arytmetyczno-logiczne

2.5 Komunikacja z innymi urządzeniami

2.6 Programowanie operacji na danych

2.7 Inne architektury

Rozdział 3. Systemy operacyjne

3.1 Historia systemów operacyjnych

3.2 Architektura systemu operacyjnego

3.3 Koordynowanie działań maszyny

3.4 Obsługa konkurencji wśród procesów

3.5 Bezpieczeństwo

Rozdział 4. Sieć i Internet

4.1 Podstawy działania sieci

4.2 Internet

4.3 World Wide Web

4.4 Protokoły internetowe

4.5 Prosta komunikacja klient serwer

4.6 Cyberbezpieczeństwo

Rozdział 5. Algorytmy

5.1 Koncepcja algorytmu

5.2 Reprezentacja algorytmu

5.3 Odkrywanie algorytmów

5.4 Struktury iteracyjne

5.5 Struktury rekurencyjne

5.6 Wydajność i poprawność

Rozdział 6. Języki programowania

6.1 Perspektywa historyczna

6.2 Tradycyjne koncepcje programowania

6.3 Jednostki proceduralne

6.4 Implementacja języka

6.5 Programowanie obiektowe

6.6 Programowanie równoległych działań

6.7 Programowanie deklaratywne

Rozdział 7. Inżynieria oprogramowania

7.1 Dyscyplina inżynierii oprogramowania

7.2 Cykl życia oprogramowania

7.3 Metodologie inżynierii oprogramowania

7.4 Modułowość

7.5 Narzędzia do pracy

7.6 Zapewnienie jakości

7.7 Dokumentacja

7.8 Interfejs człowiek–maszyna

7.9 Własność i odpowiedzialność za oprogramowanie

Rozdział 8. Abstrakcje danych

8.1 Podstawowe struktury danych

8.2 Powiązane pojęcia

8.3 Implementowanie struktur danych

8.4 Krótkie studium przypadku

8.5 Niestandardowe typy danych

8.6 Klasy i obiekty

8.7 Wskaźniki w języku maszynowym

Rozdział 9. Systemy baz danych

9.1 Podstawy baz danych

9.2 Model relacyjny

9.3 Bazy obiektowe

9.4 Utrzymywanie integralności bazy danych

9.5 Tradycyjne struktury plików

9.6 Eksploracja danych

9.7 Społeczny wpływ technologii bazodanowych

Rozdział 10. Grafika komputerowa

10.1 Zakres grafiki komputerowej

10.2 Przegląd grafiki 3D

10.3 Modelowanie

10.4 Renderowanie

10.5 Sposoby na oświetlenie globalne

10.6 Animacje

Rozdział 11. Sztuczna inteligencja

11.1 Inteligencja i maszyny

11.2 Postrzeganie

11.3 Rozumowanie

11.4 Dodatkowe obszary badań

11.5 Sztuczne sieci neuronowe

11.6 Robotyka

11.7 Myśląc o konsekwencjach

Rozdział 12. Teoria obliczalności

12.1 Funkcje i ich obliczanie

12.2 Maszyna Turinga

12.3 Uniwersalne języki programowania

12.4 Funkcje nieobliczalne

12.5 Złożoność problemów

12.6 Kryptografia z kluczem publicznym

Dodatki

Przypisy

Przedmowa

Ta książka stanowi ogólny przegląd informatyki. Dotyczy obszernego zakresu tej dziedziny, jednocześnie oferując wystarczającą szczegółowość, by umożliwić zrozumienie analizowanych tematów.

Odbiorcy

Tekst ten napisaliśmy z myślą o studentach informatyki oraz innych dyscyplin. Jeśli chodzi o studentów informatyki, większość rozpoczyna studia z iluzją, że informatyka to programowanie, przeglądanie stron internetowych i udostępnianie plików w Internecie, bo w zasadzie jest to wszystko, co widzieli. Jednak informatyka to znacznie więcej. Początkujący studenci informatyki muszą zapoznać się z szerokim zakresem przedmiotu, w którym planują zdobyć specjalizację. Zapewnienie tej wiedzy jest tematem niniejszej książki. Da ona studentom przegląd informatyki – podstawę, dzięki której mogą zrozumieć znaczenie i wzajemne powiązania przyszłych kursów w tej dziedzinie. To podejście do nauki modelem stosowanym w praktyce na kursach wprowadzających w naukach przyrodniczych.

To szerokie tło jest również tym, czego potrzebują studenci z innych dyscyplin, jeśli mają należeć do społeczeństwa technicznego, w którym żyją. Kurs informatyki dla tej grupy odbiorców powinien zapewnić praktyczne, realistyczne zrozumienie całej dziedziny, a nie jedynie wprowadzenie do korzystania z Internetu lub szkolenie w zakresie korzystania z niektórych popularnych pakietów oprogramowania. Oczywiście jest miejsce na tego typu szkolenia, natomiast ten tekst dotyczy edukacji.

Podczas pisania poprzednich wydań tej książki głównym celem było zachowanie jej przystępności dla studentów nietechnicznych. W rezultacie książka była z powodzeniem wykorzystywana na kursach dla studentów z różnych dyscyplin i na różnych poziomach edukacji, od szkół średnich po kursy dla absolwentów. To, 13 wydanie, jest opracowane tak, by kontynuować tę tradycję.

Nowości w wydaniu 13.

Głównym celem podczas opracowywania tego 13. Wydania było podkreślenie wspólnych obszarów z nowym egzaminem College Board Advanced Placement® Computer Science Principles („CSP”). Ten obszerny podręcznik w zakresie wprowadzenia do informatyki zawierał wiele głównych pojęć i praktyk obliczeniowych skodyfikowanych w ramach CSP na długo przed pojawieniem się tego egzaminu. Wcześniejsze wydania książki zostały wykorzystane w pilotażowych wersjach kursów CSP oraz jako źródło rozwoju zawodowego dla nauczycieli przygotowujących się do nauczania w tym zakresie na poziomie szkół średnich. Chociaż książka ta jest przeznaczona głównie do kursów wprowadzających na poziomie szkoły wyższej, to wydanie wyraźnie zawiera wiele punktów wspólnych z treściami CSP, aby lepiej pomóc studentom i instruktorom przygotowującym się do egzaminu AP® CSP lub uczęszczającym na kurs na poziomie szkoły wyższej, który odpowiada programowi CSP.

W wydaniu 13. nadal korzystamy z przykładów kodu w Pythonie i pseudokodu podobnego do Pythona przyjętych w wydaniu 12. Wprowadziliśmy tę zmianę z kilku powodów. Przede wszystkim tekst zawierał już sporo kodu w różnych językach, a w kilku rozdziałach także w postaci szczegółowego pseudokodu. W zakresie, w jakim czytelnicy już przyswajają sporą ilość składni, właściwe jest użycie tej składni w języku, na który mogą faktycznie trafić w kolejnym kursie. Co ważniejsze, coraz większa liczba instruktorów, którzy korzystają z tej publikacji, stwierdziła, że nawet w szerokim wprowadzeniu do informatyki studentom trudno jest opanować wiele tematów, jeśli brakuje narzędzi programistycznych do eksploracji i eksperymentowania.

Ale dlaczego Python? Wybór języka jest zawsze kwestią sporną, a każdy wybór z pewnością zdenerwuje co najmniej tyle osób, ilu się spodoba. Python to doskonały wybór z następujących powodów:

• przejrzysta, łatwa do opanowania składnia,

• proste typy pierwotne we/wy,

• typy danych i struktury sterujące, które ściśle odpowiadają typom pierwotnym w pseudokodzie używanym we wcześniejszych wydaniach, oraz

• obsługa wielu paradygmatów programowania.

Jest to dojrzały język z aktywną społecznością programistyczną i bogatymi zasobami online do dalszej nauki. W pewnych kategoriach Python pozostaje jednym z pięciu najczęściej używanych języków w branży i obserwuje się gwałtowny wzrost jego wykorzystania na kursach wprowadzających do informatyki. Jest szczególnie popularny w przypadku kursów wprowadzających na kierunkach niespecjalistycznych i jest szeroko akceptowany w innych dziedzinach nauki, technologii, inżynierii i matematyki, takich jak fizyka i biologia, oraz jako język z wyboru w przypadku zastosowań w naukach obliczeniowych.

Niemniej jednak tekst nadal koncentruje się na różnych pojęciach z zakresu informatyki. Dodatki w Pythonie mają dać czytelnikom głębszy smak programowania w stosunku do poprzednich wydań, ale nie służyć jako pełnoprawne wprowadzenie do programowania. Omawiane tematy w Pythonie są związane z istniejącą strukturą tekstu. Tak więc rozdział 1 omawia składnię Pythona do przedstawiania danych – liczb całkowitych, zmiennoprzecinkowych, ASCII i łańcuchów Unicode. Rozdział 2 dotyczy operacji Pythona, które ściśle odzwierciedlają podstawowe operacje maszynowe omówione w dalszej części rozdziału. Warunki, pętle i funkcje zostały wprowadzone w rozdziale 5, gdzie te konstrukcje są potrzebne do utworzenia kompletnego pseudokodu do opisywania algorytmów. Krótko mówiąc, konstrukcje Pythona służą do podkreślania pojęć informatycznych, a nie odwracania uwagi od tematu dyskusji.

Każdy rozdział został zmieniony, zaktualizowany i poprawiony w stosunku do poprzednich wydań.

Układ książki

Tematy w niniejszej książce są ułożone od najbardziej elementarnych do bardziej złożonych, od konkretów do uogólnień – taki układ stanowi solidną pedagogiczną prezentację, w której każdy temat prowadzi do następnego. Zaczyna się od podstaw kodowania informacji, przechowywania danych i architektury komputerowej (rozdziały 1 i 2); przechodzi do analizy systemów operacyjnych (rozdział 3) i sieci komputerowych (rozdział 4); zajmuje się tematyką algorytmów, języków programowania i tworzenia oprogramowania (rozdziały od 5 do 7); analizuje techniki zwiększania dostępności informacji (rozdziały 8 i 9); rozważa kilka głównych zastosowań technologii komputerowej poprzez grafikę (rozdział 10) i sztuczną inteligencję (rozdział 11) i kończy się wprowadzeniem do ogólnej teorii obliczeń (rozdział 12).

Mimo że zawartość książki jest zgodna z tym naturalnym zagłębianiem się w tematykę, poszczególne rozdziały i podrozdziały są zaskakująco niezależne i zwykle można je czytać jako pojedyncze jednostki lub przestawiać w celu utworzenia alternatywnych sekwencji studiów. W rzeczywistości książka ta jest często używana jako podstawa do kursów, które obejmują materiał w różnej kolejności. Jedna z tych alternatyw zaczyna się od materiału z rozdziałów 5 i 6 („Algorytmy” i „Języki programowania”) i w zależności od potrzeb odwołuje się do wcześniejszych rozdziałów. Znamy również jeden kurs, który zaczyna się od materiału z rozdziału 12 na temat obliczalności. W jeszcze innych przypadkach test ten był używany w kursach będących zwieńczeniem pewnego obszaru wiedzy, gdzie służył jako szkielet, z którego można było przejść do projektów w różnych obszarach. Kursy dla mniej zorientowanych technicznie odbiorców mogą koncentrować się na rozdziałach 4 („Sieć i Internet”), 9 („Systemy baz danych”), 10 („Grafika komputerowa”) i 11 („Sztuczna inteligencja”).

Na pierwszej stronie każdego rozdziału użyliśmy gwiazdek, aby oznaczyć niektóre podrozdziały jako opcjonalne. Są to podrozdziały, które omawiają tematy w bardziej konkretnym kontekście lub po prostu omawiają je bardziej szczegółowo. Naszą intencją w książce jest jedynie zasugerowanie alternatywnych ścieżek lektury. Są oczywiście i inne możliwości. W szczególności, jeśli chcesz szybko zapoznać się z tematyką, proponujemy następującą kolejność:

Podrozdział     Temat

1.1–1.4    Podstawy zapisu i przechowywania danych

2.1–2.3    Architektura maszyny i język maszynowy

3.1–3.3    Systemy operacyjne

4.1–4.3    Sieć i Internet

5.1–5.4    Algorytmy i projektowanie algorytmów

6.1–6.4    Języki programowania

7.1–7.2    Inżynieria oprogramowania

8.1–8.3    Abstrakcje danych

9.1–9.2    Systemy baz danych

10.1–10.2    Grafika komputerowa

11.1–11.3    Sztuczna inteligencja

12.1–12.2    Teoria obliczalności

W tekście przewija się kilka wątków. Jednym z nich jest to, że informatyka jest dynamiczna. Książka wielokrotnie przedstawia tematy w ujęciu historycznym, omawia aktualny stan rzeczy oraz wskazuje kierunki badań. Kolejnym wątkiem jest rola abstrakcji i sposób, w jaki abstrakcyjne narzędzia są wykorzystywane do kontrolowania złożoności. Temat ten został przedstawiony w rozdziale 0, a następnie powtórzony w kontekście architektury systemu operacyjnego, sieci, opracowywania algorytmów, projektowania języków programowania, inżynierii oprogramowania, organizacji danych i grafiki komputerowej.

Do prowadzących szkolenia

W tej książce znajduje się więcej materiału, niż studenci mogą normalnie przerobić w ciągu jednego semestru, zatem nie należy się wahać, przy czy pominąć tematy, które nie pasują do celów kursu, lub zmienić kolejność według własnego uznania. Można przekonać się, że chociaż tekst podąża za ustaloną fabułą, tematy są poruszane w sposób w dużej mierze niezależny, co pozwala na ich wybranie według własnego uznania. Książka jest przeznaczona do wykorzystania jako zasób dla kursu, a nie jako definicja kursu. Sugerujemy, aby zachęcać studentów do czytania materiałów, które nie zostały w pełni uwzględnione w naszych własnych kursach. Nie docenimy ich, jeśli założymy, że musimy wszystko wyjaśnić na zajęciach. Powinniśmy wspierać ich w samodzielnej nauce.

Czujemy się w obowiązku powiedzieć kilka słów o układzie tekstu – od zagadnień najbardziej elementarnych po bardziej złożone oraz od konkretów do uogólnień. Jako nauczyciele akademiccy zbyt często zakładamy, że studenci docenią naszą perspektywę przedmiotu – często taką, którą wypracowaliśmy przez wiele lat pracy w danej dziedzinie. Jako nauczyciele uważamy, że radzimy sobie lepiej, prezentując materiał z perspektywy studenta. Dlatego książka rozpoczyna się od reprezentacji i przechowywania danych, architektury maszyn, systemów operacyjnych i sieci. Są to tematy, które studenci bez trudu kojarzą – najprawdopodobniej słyszeli takie terminy, jak JPEG i MP3; zapewne nagrywali dane na płytach DVD i pendrive’ach; mieli do czynienia z systemem operacyjnym i codziennie korzystają z Internetu i smartfonów. Rozpoczynając kurs od tych tematów, studenci poznają odpowiedzi na wiele pytań „dlaczego”, które zadają sobie od lat, i uczą się postrzegać kurs jako praktyczny, a nie teoretyczny. Od tego momentu naturalne jest przejście do bardziej abstrakcyjnych zagadnień związanych z algorytmami, strukturami w algorytmach, językami programowania, metodologią tworzenia oprogramowania, obliczeń i złożoności, które niektórzy z nas postrzegają jako główne tematy w tej nauce. Jak już wspomniano, tematy są przedstawione w sposób, który nie zmusza do trzymania się takiej kolejności tematów, natomiast zachęcamy do jej wypróbowania.

Wszyscy zdajemy sobie sprawę, że studenci uczą się o wiele więcej, niż my uczymy ich bezpośrednio, a nauka zdobywana pośrednio jest często lepiej przyswajana niż ta zdobywana bezpośrednio. Jest to istotne, jeśli chodzi o „nauczanie” rozwiązywania problemów. Studenci nie stają się osobami rozwiązującymi problemy, studiując metodologie rozwiązywania problemów. Staną się nimi, rozwiązując problemy – a nie tylko precyzyjnie postawione „zadania podręcznikowe”. Z tego powodu ta książka zawiera wiele zadań, z których kilka jest celowo niejasnych – co oznacza, że niekoniecznie istnieje jedno poprawne podejście lub jedna poprawna odpowiedź. Zachęcamy do korzystania z nich i rozwijania się na ich podstawie.

Inne zagadnienia z kategorii „uczenia się niebezpośredniego” to profesjonalizm, etyka i odpowiedzialność społeczna. Nie uważamy, że powinno to być przedstawiane jako odosobnione kwestie, które są po prostu dołączone do kursu. Zamiast tego powinny stanowić integralną część materiału i pojawiać się wtedy, gdy jest to istotne. Takie podejście jest stosowane w niniejszej książce. Podrozdziały 3.5, 4.6, 7.9, 9.7 i 11.7 prezentują tematy, takie jak bezpieczeństwo, prywatność, odpowiedzialność i świadomość społeczna w kontekście systemów operacyjnych, sieci, inżynierii oprogramowania, systemów baz danych i sztucznej inteligencji. Każdy rozdział zawiera również zestaw pytań zatytułowanych „Kwestie społeczne”, które zachęcają studentów do zastanowienia się nad związkiem między materiałem zawartym w tekście a społeczeństwem, w którym żyją.

Dziękujemy za skorzystanie z naszej książki w waszym szkoleniu. Niezależnie od tego, czy zdecydujecie, że jest ona właściwa w waszej sytuacji, czy nie, mamy nadzieję, że uznacie ją za wkład w literaturę edukacyjną z zakresu informatyki.

Funkcje pedagogiczne

Ta książka jest owocem wielu lat nauczania. Dzięki temu jest bogata w pomoce pedagogiczne. Najważniejszymi z nich jest obfitość problemów, które mogą pomóc zwiększyć zaangażowanie studentów – ponad tysiąc w tym 13. wydaniu. Są one oznaczone jako pytania i ćwiczenia, problemy przekrojowe i kwestie społeczne. Pytania oraz ćwiczenia pojawiają się na końcu każdego podrozdziału (z wyjątkiem rozdziału wprowadzającego). Dotyczą właśnie omówionego materiału, rozszerzają wcześniejszą dyskusję lub wskazują powiązane zagadnienia, które zostaną omówione później. Odpowiedzi na te pytania znajdują się w dodatku F.

Na końcu każdego rozdziału (z wyjątkiem rozdziału wprowadzającego) pojawiają się problemy przekrojowe. Mogą one służyć jako „zadania domowe”, ponieważ obejmują materiał z całego rozdziału i w książce nie ma do nich odpowiedzi.

Ponadto, na końcu każdego rozdziału znajdują się pytania z kategorii „Kwestie społeczne”. Są one przeznaczone do przemyślenia i dyskusji. Wiele z nich można wykorzystać do realizacji zadań badawczych zakończonych krótkimi raportami pisemnymi lub ustnymi.

Każdy rozdział kończy się również listą o nazwie „Dodatkowe materiały”, która zawiera odniesienia do innych źródeł związanych z tematem rozdziału. Dobrymi miejscami do szukania powiązanych materiałów są również witryny wskazane w tej przedmowie, w tekście oraz w specjalnie wydzielonych wstawkach w tekście.

Dodatkowe materiały

Różne materiały uzupełniające są dostępne na stronie internetowej towarzyszącej książce: www.pearsonhighered.com/brookshear. Wszyscy czytelnicy mogą skorzystać z:

• ćwiczeń dla każdego rozdziału, które poszerzają tematy zawarte w tekście i dają możliwość poznania powiązanych tematów;

• „autotestów” dla każdego rozdziału, które pomagają czytelnikom przemyśleć materiał zawarty w tekście;

• zadań, które uczą podstaw Pythona w pedagogicznej kolejności zgodnej z tekstem.

Ponadto, w Instructor Resource Center w Pearson Education, dostępne są poniższe dodatki dla wykwalifikowanych szkoleniowców. Odwiedź stronę www.pearsonhighered.com lub skontaktuj się z przedstawicielem handlowym Pearson, aby uzyskać informacje o tym, jak zdobyć do nich dostęp:

• przewodnik instruktora z odpowiedziami do zadań powtórzeniowych do rozdziałów,

• slajdy w PowerPoint z wykładami,

• bank testów

Errata do tej książki (jeśli jakaś się pojawi) będzie dostępna pod adresem http://www.mscs.mu.edu/~brylow/errata/.

Do studentów

Glenn Brookshear jest trochę nonkonformistą (niektórzy jego przyjaciele powiedzieliby, że więcej niż trochę), kiedy zatem przystąpił do pisania tego tekstu, nie zawsze stosował się do otrzymanych rad. W szczególności wielu twierdziło, że niektóre materiały są zbyt zaawansowane dla początkujących studentów. Uważamy jednak, że jeśli temat jest istotny, to jest on istotny, nawet jeśli społeczność akademicka uważa go za „temat zaawansowany”. Zasługujesz na tekst, który przedstawia pełny obraz informatyki, a nie na rozwodnioną wersję zawierającą sztucznie uproszczone prezentacje tylko tych tematów, które zostały uznane za odpowiednie dla początkujących studentów. Nie pomijaliśmy więc tematów, lecz szukaliśmy lepszych wyjaśnień. Staraliśmy się zapewnić wystarczającą szczegółowość, aby dać uczciwy obraz tego, czym jest informatyka. Podobnie jak w przypadku przypraw w przepisie, możesz pominąć niektóre tematy na kolejnych stronach, ale jeśli chcesz, to możesz ich spróbować – i zachęcamy do tego.

Zwracamy również uwagę, że jak w każdym kursie dotyczącym technologii, szczegóły, których uczymy się dzisiaj, mogą nie być szczegółami, które będziemy musieli znać jutro. Dziedzina jest dynamiczna – to daje emocje. Ta książka daje aktualny obraz tematu, a także perspektywę historyczną. Mając takie podstawy, będziecie przygotowani do rozwijania się wraz z technologią. Zachęcamy do rozpoczęcia procesu rozwoju już teraz poprzez wyjście poza tę książkę. Uczcie się uczyć.

Dziękujemy za zaufanie, jakim nas obdarzyliście, decydując się na lekturę naszej książki. Jako autorzy mamy obowiązek stworzyć rękopis, który jest wart waszego czasu. Mamy nadzieję, że okaże się, że spełniliśmy to zobowiązanie.

Podziękowania

Przede wszystkim dziękuję Glennowi Brookshearowi, który prowadził tę książkę, „swoje dziecko”, przez 11 poprzednich wydań obejmujących ponad ćwierć wieku szybkiego rozwoju i burzliwych zmian w dziedzinie informatyki. Chociaż jest to drugie wydanie, w którym pozwolił współautorowi nadzorować wszystkie zmiany, strony tego 13. wydania pozostają w dużej mierze głosem Glenna i, mam nadzieję, że są też zgodne z jego wizją. Wszelkie nowe niedociągnięcia są moje, a eleganckie ramy są jego autorstwa.

Przyłączam się do podziękowań Glenna dla tych z Was, którzy wspierali tę książkę, czytając ją i korzystając z jej poprzednich wydań. Jesteśmy zaszczyceni. Trzynaście wydań podręcznika do informatyki? Musimy być blisko jakiegoś rekordu.

Andrew Kuemmel (Madison West) był nieocenionym doradcą, gdy pracowaliśmy nad ustaleniem części wspólnych 13. wydania i CSP. Jest jedyną znaną mi osobą, która z powodzeniem prowadziła wiele kursów CSP zarówno na poziomie szkoły średniej, jak i uniwersytetu, a jego niestrudzone wsparcie dla nauczycieli informatyki w moim rodzinnym stanie Wisconsin było naprawdę inspirujące.

David T. Smith (Indiana University of Pennsylvania) odegrał znaczącą rolę jako współautor poprawek do 11. wydania, z których wiele jest nadal widocznych w niniejszym 13. wydaniu. Jego uważna lektura poprzednich wydań i dbałość o materiały uzupełniające były niemiernie istotne. Andrew Kuemmel (Madison West), George Corliss (Marquette) i Chris Mayfield (James Madison) dostarczyli cennych uwag, pomysłów i/lub zachęty do pracy nad projektami tego lub poprzednich wydań, a James E. Ames (Virginia Commonwealth), Stephanie E. August (Loyola), Yoonsuck Choe (Texas A&M), Melanie Feinberg (UT-Austin), Eric D. Hanley (Drake), Sudharsan R. Iyengar (Winona State), Ravi Mukkamala (Old Dominion) i Edward Pryor (Wake Forest) przedstawili cenne opinie odnośnie do poprawek dotyczących Pythona w 12. wydaniu.

Inne oosby, który wniosły wkład w to lub poprzednie wydania, to: J.M. Adams, C.M. Allen, D.C.S. Allison, E. Angel, R. Ashmore, B. Auernheimer, P. Bankston, M. Barnard, P. Bender, K. Bowyer, P.W. Brashear, C.M. Brown, H.M. Brown, B. Calloni, J. Carpinelli, M. Clancy, R.T. Close, D.H. Cooley, L.D. Cornell, M.J. Crowley, F. Deek, M. Dickerson, M.J. Duncan, S. Ezekiel, C. Fox, S. Fox, N.E. Gibbs, J.D. Harris, D. Hascom, L. Heath, P.B. Henderson, L. Hunt, M. Hutchenreuther, L.A. Jehn, K.K. Kolberg, K. Korb, G. Krenz, J. Kurose, J. Liu, T.J. Long, C. May, J.J. McConnell, W. McCown, S. J. Merrill, K. Messersmith, J.C. Moyer, M. Murphy, J.P. Myers, Jr., D.S. Noonan, G. Nutt, W.W. Oblitey, S. Olariu, G. Riccardi, G. Rice, N. Rickert, C. Riedesel, J.B. Rogers, G. Saito, W. Savitch, R. Schlafly, J.C. Schlimmer, S. Sells, Z. Shen, G. Sheppard, J.C. Simms, M.C. Slattery, J. Slimick, J.A. Slomka, J. Solderitsch, R. Steigerwald, L. Steinberg, C.A. Struble, C.L. Struble, W.J. Taffe, J. Talburt, P. Tonellato, P. Tromovitch, P.H. Winston, E.D. Winter, E. Wright, M. Ziegler i jedna osoba anonimowa. Wszystkim im szczerze dziękujemy.

Diane Christie zaprojektowała podręczniki Java i C++ dla witryny towarzyszącej poprzedniemu wydaniu, z której pochodzą nasze nowe zasoby w Pythonie. Dziękuję, Diane. Kolejne podziękowania kierujemy do Rogera Eastmana, który był siłą twórczą zadań towarzyszących poprzednim wydaniom tej książki, którego DNA wciąż można znaleźć w zadaniach na stronie towarzyszącej aktualnemu wydaniu.

Dziękuję dobrym ludziom z Pearson, którzy wsparli ten projekt. Tracy Johnson, Erin Ault, Carole Snyder i Scott Disanno wnieśli do książki swoją mądrość i wiele ulepszeń w trakcie całego procesu.

Na koniec dziękuję mojej żonie, Petrze, która zajmowała naszą trójkę dzieci przez długie popołudnia i wieczory podczas mojej pracy nad tym wydaniem. Ona jest moją opoką.

D.W.B.

Uniwersytet Marquette

1 stycznia 2018

Związek 13. wydania książki Informatyka w ogólnym zarysie oraz wydania AP® z AP® Computer Science Principles Curriculum Framework

AP® jest znakiem towarowym zarejestrowanym i/lub należącym do College Board, który nie był zaangażowany w produkcję i nie promuje tego produktu.

Rozumienie kluczowych kwestii (Enduring Understandings, EU) i efekty kształcenia (Learning Outcomes, LO) z AP® CSP Curriculum Framework zostały odwzorowane na poniższe rozdziały i podrozdziały tego podręcznika. Kilka z performatywnych efektów kształcenia nie zostało wyraźnie omówionych w tej książce, ale można je znaleźć w dodatkowych zasobach i ćwiczeniach dostępnych na stronie internetowej towarzyszącej książce: www.pearsonhighered.com/brookshear. Aby uzyskać pełne informacje o programie nauczania, odwiedź stronę https://apcentral.collegeboard.org.

1.1. Kreatywny rozwój może być istotnym procesem tworzenia artefaktów obliczeniowych.

1.1.1

Zastosowanie kreatywnego procesu rozwoju podczas tworzenia artefaktów obliczeniowych.

5.3

1.2. Informatyka umożliwia ludziom wykorzystanie kreatywnych procesów rozwoju do tworzenia artefaktów obliczeniowych w celu twórczej ekspresji lub rozwiązywania problemów.

1.2.1

Utworzenie artefaktu obliczeniowego w celu twórczej ekspresji.

1.0

1.2.3

Utworzenie nowego artefaktu obliczeniowego poprzez połączenie lub modyfikację istniejących artefaktów.

10.6

1.3. Informatyka może rozszerzyć tradycyjne formy ludzkiej ekspresji i doświadczenia.

1.3.1

Użycie narzędzi i technik informatycznych do twórczej ekspresji.

10.1

2.1. Do reprezentowania wszystkich danych cyfrowych można użyć różnych abstrakcji zbudowanych na sekwencjach binarnych.

2.1.1

Opisanie różnorodnych abstrakcji używanych do reprezentowania danych.

1.1, 1.4, 2.1

2.1.2

Wyjaśnienie, w jaki sposób sekwencje binarne są używane do reprezentowania danych cyfrowych.

1.6, 2.6, 6.1, 6.4

2.2. Do pisania programów lub tworzenia innych artefaktów obliczeniowych używa się wielu poziomów abstrakcji.

2.2.1

Utworzenie abstrakcji podczas pisania programu lub tworzenia innych artefaktów obliczeniowych.

6.3

2.2.2

Użycie wielu poziomów abstrakcji do pisania programów.

6.2

2.2.3

Określenie różnych poziomów abstrakcji używanych podczas pisania programów.

1.1, 2.6, 6.1, 6.4

2.3. Modele i symulacje wykorzystują abstrakcję do generowania nowego pojmowania i wiedzy.

2.3.1

Zastosowanie modeli i symulacji do reprezentowania zjawisk.

10.3, 10.4, 10.6

2.3.2

Użycie modeli i symulacji do formułowania, udoskonalania i testowania hipotez.

10.4

3.1. Ludzie używają programów komputerowych do przetwarzania informacji w celu uzyskania wnikliwości i wiedzy.

3.1.1

Znajdowanie wzorców i testowanie hipotez dotyczących informacji przetworzonych cyfrowo w celu uzyskania wglądu i wiedzy.

9.1, 9.6

3.2. Informatyka ułatwia eksplorację i odkrywanie powiązań w informacjach.

3.2.1

Pozyskiwanie informacji z danych w celu odkrywania i wyjaśniania powiązań lub trendów.

9.1, 11.4

3.2.2

Określenie, jak duże zbiory danych wpływają na wykorzystanie procesów obliczeniowych do odkrywania informacji i wiedzy.

9.0, 9.1, 9.4

3.3. Przedstawianie informacji jako danych cyfrowych wymaga kompromisów.

3.3.1

Analizowanie, w jaki sposób reprezentowanie, przechowywanie, bezpieczeństwo i transmisja danych wiążą się z obliczeniową manipulacją informacjami.

1.3, 1.9, 4.4, 4.5, 9.7

4.1. Algorytmy to precyzyjne sekwencje instrukcji dla procesów, które mogą być wykonywane przez komputer i są implementowane przy użyciu języków programowania.

4.1.1

Opracowanie algorytmu w celu implementacji w postaci programu.

5.1, 5.2, 5.4, 6.3

4.1.2

Wyrażenie algorytmu z użyciem języka.

5.2, 6.1

4.2. Algorytmy mogą rozwiązać wiele, ale nie wszystkie problemy obliczeniowe.

4.2.1

Wyjaśnienie różnicy między algorytmami, które działają w akceptowanym czasie, a tymi, które nie działają w akceptowanym czasie.

12.5

4.2.2

Wyjaśnienie różnicy między rozwiązywalnymi i nierozwiązywalnymi problemami w informatyce.

11.3, 12.5

4.2.3

Wyjaśnienie istnienia nierozstrzygalnych problemów w informatyce.

12.1, 12.4

4.2.4

Analityczna i empiryczna ocena algorytmów pod kątem wydajności, poprawności i przejrzystości.

5.6, 12.5

5.1. Programy mogą być opracowywane w celu twórczej ekspresji, zaspokojenia osobistej ciekawości, tworzenia nowej wiedzy lub rozwiązywania problemów (aby pomóc ludziom, organizacjom lub społeczeństwu).

5.1.1

Opracowanie programu w celu kreatywnej ekspresji, zaspokojenia osobistej ciekawości lub zdobycia nowej wiedzy.

10

5.1.2

Opracowanie właściwego programu w celu rozwiązywania problemów.

6.2, 7.2, 7.3, 7.4, 7.7

5.1.3

Współpraca w celu opracowania programu.

5.1, 7.1, 7.6

5.2. Ludzie piszą programy w celu wykonywania algorytmów.

5.2.1

Wyjaśnienie, jak programy implementują algorytmy.

2.6, 6.2

5.3. Programowanie ułatwiają odpowiednie abstrakcje.

5.3.1

Użycie abstrakcji do zarządzania złożonością programów.

1.8, 2.6, 6.3, 6.5, 8.1, 8.5

5.4. Programy są tworzone, utrzymywane i używane przez ludzi do różnych celów.

5.4.1

Ocena poprawności programu.

1.8, 7.5

5.5. Programowanie wykorzystuje pojęcia matematyczne i logiczne.

5.5.1

Zastosowanie odpowiednich pojęć matematycznych i logicznych w programowaniu.

1.1, 1.6, 1.7, 1.8, 8.1

6.1. Internet to sieć systemów autonomicznych.

6.1.1

Wyjaśnienie abstrakcji w Internecie i tego, jak działa Internet.

4.1, 4.2, 4.4

6.2. Cechy Internetu wpływają na budowane w nim systemy.

6.2.1

Wyjaśnienie charakterystyki Internetu i budowanych w nim systemów.

4.2, 4.4

6.2.2

Wyjaśnienie, w jaki sposób cechy Internetu wpływają na budowane w nim systemy.

1.3, 4.1, 4.2, 4.4, 4.6

6.3. Cyberbezpieczeństwo jest ważnym problemem dla Internetu i budowanych w nim systemów.

6.3.1

Wskazanie istniejących problemów związanych z cyberbezpieczeństwem oraz możliwości rozwiązania tych problemów w Internecie i budowanych w nim systemach.

4.6

7.1. Informatyka usprawnia komunikację, interakcję i poznawanie.

7.1.1

Wyjaśnienie, w jaki sposób innowacje komputerowe wpływają na komunikację, interakcję i poznawanie.

4

7.2. Informatyka umożliwia wprowadzanie innowacji w niemal każdej dziedzinie.

7.2.1

Wyjaśnienie, w jaki sposób informatyka wpłynęła na innowacje w innych dziedzinach.

9.6, 10.6

7.3. Informatyka ma globalny wpływ – zarówno korzystny, jak i szkodliwy – na ludzi i społeczeństwo.

7.3.1

Przeanalizowanie korzystnych i szkodliwych skutków informatyki.

4.6, 9.7, 11.7

7.4. Innowacje informatyczne wpływają na konteksty gospodarcze, społeczne i kulturowe, w których są projektowane i wykorzystywane.

7.4.1

Wyjaśnienie powiązania między informatyką a kontekstami świata rzeczywistego, w tym kontekstami ekonomicznymi, społecznymi i kulturowymi.

4.2

Rozdział 0

Wprowadzenie

W tym wstępnym rozdziale przedstawimy zakres informatyki, perspektywę historyczną i określimy podstawy, od których będzie można rozpocząć nasze dalsze rozważania. ■

0.1    Rola algorytmów

0.2    Historia informatyki

0.3    Zawartość książki

0.4    Nadrzędne zagadnienia informatyki

Algorytmy

Abstrakcja

Kreatywność

Dane

Programowanie

Internet

Wpływ

Rozumienie kluczowych kwestii i efekty kształcenia

Badanie algorytmów jest podstawą informatyki.

EK. Wyjaśnienie znaczenia algorytmów w dziedzinie informatyki.

Najnowsza historia informatyki charakteryzuje się szybkim postępem w zakresie mocy obliczeniowej, miniaturyzacji i łączności.

EK. Wskazanie głównych kamieni milowych w historii informatyki, które utorowały drogę do naszego współczesnego społeczeństwa technologicznego.

Postępy w informatyce mają głęboki wpływ na kulturę i społeczeństwo.

EK. Omówienie niektórych dylematów społecznych, etycznych i prawnych, które wynikają z postępu w informatyce.

Informatyka to dyscyplina, która ma na celu tworzenie podstaw naukowych dla takich tematów, jak projektowanie komputerów, programowanie komputerów, przetwarzanie informacji, rozwiązywanie problemów za pomocą algorytmów i samego procesu tworzenia algorytmów. Daje podstawy dla dzisiejszych zastosowań komputerów, a także fundamenty przyszłej infrastruktury komputerowej.

Ta książka stanowi obszerne wprowadzenie do tej nauki. Będziemy badać szeroki zakres tematów, w tym większość z tych, które składają się na typowy uniwersytecki program nauczania informatyki. Chcemy pokazać pełen zakres i dynamikę tej dziedziny. Dlatego, oprócz samych tematów, interesować nas będzie ich historyczny rozwój, aktualny stan badań oraz perspektywy na przyszłość. Naszym celem jest przedstawienie funkcjonalnego rozumienia informatyki – takiego, które będzie wspierać tych, którzy chcą prowadzić bardziej specjalistyczne studia w tej nauce, a także takiego, które umożliwi osobom z innych dziedzin rozwijanie się w coraz bardziej zaawansowanym technicznie społeczeństwie.

0.1 Rola algorytmów

Zaczniemy od najbardziej podstawowego pojęcia w informatyce – algorytmu. Nieformalnie algorytm to zestaw kroków, które określają sposób wykonywania zadania. (Dokładniej omówimy to w dalszej części, w rozdziale 5). Istnieją na przykład algorytmy gotowania (przepisy kulinarne), znajdowania drogi w obcym mieście (trasy), obsługi pralek (zwykle znajdujące się od wewnątrz pokrywy pralki lub być może na ścianie pralni), odtwarzania muzyki (wyrażone w postaci nut) oraz do wykonywania magicznych sztuczek (rysunek 0.1).

Sztuczka: Iluzjonista kładzie na stole kilka zakrytych kart do gry i dokładnie je miesza. Następnie, gdy publiczność zażąda odkrycia czerwonej lub czarnej karty, magik odwraca kartę w żądanym kolorze.

Sekret sztuczki i sposób jej wykonania

Krok 1.    Z normalnej talii kart wybierz dziesięć czerwonych kart i dziesięć czarnych kart. Rozłóż na stole zakryte karty w dwóch stosach według koloru.

Krok 2.    Poinformuj, że wybrałeś kilka kart czerwonych i kilka czarnych.

Krok 3.    Podnieś czerwone karty. Pod pretekstem, że układasz je w małą talię, trzymaj je zakryte w lewej ręce, a kciukiem oraz pierwszym palcem prawej ręki zagnij do tyłu róg talii, tak aby każda karta była lekko zagięta do tyłu. Następnie połóż zakrytą talię czerwonych kart na stole, mówiąc: „Na tym stosie znajdują się czerwone karty”.

Krok 4.    Podnieś czarne karty. W sposób podobny do tego z kroku 3 zagnij te karty lekko do przodu. Następnie odłóż te karty na stół w zakrytej talii, mówiąc: „Na tym stosie znajdują się czarne karty”.

Krok 5.    Natychmiast po odłożeniu czarnych kart na stół, użyj obu rąk, aby wymieszać czerwone i czarne karty (nadal zakryte), rozkładając je na stole. Wyjaśnij, że karty są dokładnie wymieszane.

Krok 6.    Dopóki na stole znajdują się zakryte karty, powtarzaj następujące kroki:

6.1. Poproś publiczność o wybór, czy ma zostać odkryta czerwona czy czarna karta.

6.2. Jeśli żądany kolor jest czerwony i istnieje (zakryta) karta z odpowiednim zagięciem, odwracamy taką kartę, mówiąc: „Oto czerwona karta”.

6.3. Jeśli żądany kolor jest czarny i istnieje (zakryta) karta z odpowiednim zagięciem, odwracamy taką kartę, mówiąc: „Oto czarna karta”.

6.4. W przeciwnym razie powiedz, że nie ma już kart w żądanym kolorze i odwróć pozostałe karty, aby udowodnić swoje stwierdzenie.

Rysunek 0.1 Algorytm magicznej sztuczki

Zanim maszyna taka jak komputer będzie mogła wykonać zadanie, musi zostać opracowany algorytm wykonania tego zadania i przedstawiony w formie odpowiedniej dla maszyny. Reprezentacja algorytmu nazywana jest programem. Dla wygody ludzi programy komputerowe są zwykle drukowane na papierze lub wyświetlane na ekranach komputerów. Dla wygody maszyn programy zapisywane są w sposób zgodny z technologią maszyny. Proces tworzenia programu, zapisywania go w formie odpowiedniej dla maszyny i przekazywania go maszynie nazywa się programowaniem, a czasem kodowaniem. Programy i reprezentowane przez nie algorytmy są zbiorczo określane jako oprogramowanie, w przeciwieństwie do samej maszyny, która jest traktowana jako sprzęt.

Badanie algorytmów rozpoczęło się jako jeden z tematów matematyki. Poszukiwanie algorytmów było ważną działalnością matematyków na długo przed powstaniem współczesnych komputerów. Celem było znalezienie jednego zestawu wskazówek opisujących, jak można rozwiązać wszystkie problemy określonego typu. Jednym z najbardziej znanych przykładów tych wczesnych badań jest algorytm dzielenia do znajdowania ilorazu dwóch liczb wielocyfrowych. Innym przykładem jest algorytm odkryty przez starożytnego greckiego matematyka Euklidesa, do znajdowania największego wspólnego dzielnika dwóch dodatnich liczb całkowitych (rysunek 0.2).

Opis: Algorytm zakłada, że jego dane wejściowe składają się z dwóch dodatnich liczb całkowitych i polega na obliczeniu największego wspólnego dzielnika tych dwóch wartości.

Procedura:

Krok 1.    Przypisz M i N odpowiednio wartość większej i mniejszej z dwóch wartości wejściowych.

Krok 2.    Podziel M przez N i nazwij resztę R.

Krok 3.    Jeśli R nie jest równe 0, przypisz M wartość N, przypisz N wartość R i wróć do kroku 2; w przeciwnym razie największym wspólnym dzielnikiem jest wartość aktualnie przypisana do N.

Rysunek 0.2 Algorytm Euklidesa do znajdowania największego wspólnego dzielnika dwóch dodatnich liczb całkowitych

Po znalezieniu algorytmu wykonanie zadania nie wymaga już zrozumienia zasad, na których ten algorytm się opiera. Wystarczy jedynie postępować zgodnie ze wskazówkami. (Możemy zastosować algorytm dzielenia, aby znaleźć iloraz, lub algorytm Euklidesa, aby znaleźć największy wspólny dzielnik, nie wiedząc, dlaczego algorytm działa akurat w taki sposób). W pewnym sensie inteligencja wymagana do rozwiązania danego problemu jest zakodowana w algorytmie.

Wychwytywane i przekazywanie inteligencji (lub przynajmniej inteligentnego zachowania) za pomocą algorytmów pozwala nam budować maszyny, które wykonują użyteczne zadania. W konsekwencji poziom inteligencji prezentowany przez maszyny jest ograniczony przez inteligencję, którą można im przekazać za pomocą algorytmów. Możemy skonstruować maszynę do wykonania zadania tylko wtedy, gdy istnieje algorytm do wykonania tego zadania. Z kolei jeśli nie istnieje algorytm do rozwiązania problemu, to rozwiązanie leży poza możliwościami maszyn.

Określenie ograniczeń możliwości algorytmicznych zostało wprowadzone jako element matematyki w latach 30. XX wieku wraz z publikacją twierdzenia o niezupełności Kurta Gödla. Twierdzenie to zasadniczo mówi, że w każdej teorii matematycznej obejmującej nasz tradycyjny system arytmetyczny istnieją twierdzenia, których prawdziwości lub fałszu nie można ustalić metodami algorytmicznymi. Krótko mówiąc, jakiekolwiek pełne badanie naszego systemu arytmetycznego wykracza poza możliwości działań algorytmicznych. Ta świadomość wstrząsnęła podstawami matematyki, a badanie możliwości algorytmicznych, które po tym nastąpiło, było początkiem dziedziny znanej dziś jako informatyka. W rzeczywistości to właśnie nauka o algorytmach stanowi rdzeń informatyki.

0.2 Historia informatyki

Dzisiejsze komputery mają bogatą genealogię. Jednym z początkowych narzędzi obliczeniowych było liczydło. Historia mówi nam, że prawdopodobnie miało ono swoje korzenie w starożytnych Chinach i było używane we wczesnych cywilizacjach greckich i rzymskich. Maszyna jest dość prosta, składa się z koralików nawleczonych na pręty, które z kolei są zamontowane w prostokątnej ramie (rysunek 0.3). Gdy koraliki są przesuwane wzdłuż prętów, ich pozycje reprezentują zapisane wartości. To właśnie w pozycjach koralików tego typu „komputer” reprezentuje i przechowuje dane. Sterowanie wykonaniem algorytmu wymaga udziału człowieka. Zatem samo liczydło jest jedynie systemem przechowywania danych i musi być połączone z człowiekiem, aby stworzyć kompletną maszynę obliczeniową.

W okresie po średniowieczu, a przed epoką nowożytną zaczęto poszukiwać bardziej wyrafinowanych maszyn obliczeniowych. Kilku wynalazców zaczęło eksperymentować z technologią kół zębatych. Wśród nich byli Blaise Pascal (1623–1662) z Francji, Gottfried Wilhelm Leibniz (1646–1716) z Niemiec i Charles Babbage (1792–1871) z Anglii. Maszyny te reprezentowały dane poprzez pozycje kół zębatych, przy czym dane były wprowadzane mechanicznie poprzez ustawienie początkowych pozycji kół zębatych. Wartości wyjściowe w maszynach Pascala i Leibniza ustalano, obserwując końcowe pozycje kół zębatych. Z kolei Babbage przewidział maszyny, które będą drukować wyniki obliczeń na papierze, aby wyeliminować możliwość błędów w transkrypcji.

Rysunek 0.3 Chińskie liczydło drewniane (Ekkapon/Shutterstock)

Można było również zaobserwować postęp w elastyczności maszyn pod względem możliwości wykonywania algorytmu. Maszyna Pascala została zbudowana do wykonywania tylko dodawania. W związku z tym w strukturę samej maszyny została wbudowana odpowiednia sekwencja kroków. W podobny sposób maszyna Leibniza miała w swojej architekturze trwale wbudowane algorytmy, aczkolwiek operator mógł wybierać spośród wielu oferowanych przez nią operacji arytmetycznych. Maszyna różnicowa Babbage’a (której skonstruowano tylko model demonstracyjny) mogła być modyfikowana do wykonywania różnych obliczeń, natomiast jego maszyna analityczna (której budowy nigdy nie sfinansowano) została zaprojektowana do odczytywania instrukcji w postaci układu dziurek w papierowych kartach. Tak więc maszyna analityczna Babbage’a była programowalna. Augusta Ada Byron (Ada Lovelace), która opublikowała artykuł, w którym pokazała, jak można zaprogramować maszynę analityczną Babbage’a do wykonywania różnych obliczeń, jest dziś często uznawana za pierwszego na świecie programistę.

Przekazywanie algorytmu za pomocą otworków w papierze nie było pomysłem Babbage’a. Zaczerpnął go od Josepha Jacquarda (1752–1834), który w 1801 r. skonstruował krosno tkackie, w którym etapy procesu tkania wyznaczały wzory otworów w dużych grubych kartach wykonanych z drewna (lub tektury). W ten sposób algorytm stosowany przez krosno można łatwo zmienić, aby uzyskać różne tkane wzory. Innym beneficjentem pomysłu Jacquarda był Herman Hollerith (1860–1929), który zastosował koncepcję przedstawiania informacji jako dziurek w papierowych kartach, aby przyspieszyć proces tworzenia tabel w spisie powszechnym w USA w 1890 roku. (To właśnie ta praca Holleritha doprowadziła do powstania IBM). Takie karty ostatecznie stały się znane jako karty perforowane i przetrwały jako popularny środek komunikacji z komputerami aż do lat 70. XX wieku.

Rysunek 0.4 Trzy kobiety obsługujące główny panel sterowania ENIAC (Electronic Numerical Integrator and Computer), gdy maszyna znajdowała się w Moore School. Maszyna została później przeniesiona do Ballistics Research Laboratory U.S. Army. (Dzięki uprzejmości U.S. Army).

Dziewiętnastowieczna technologia nie była w stanie w sposób opłacalny produkować skomplikowanych, napędzanych przekładniami maszyn Pascala, Leibniza i Babbage’a. Jednak wraz z postępem w elektronice na początku XX wieku bariera ta została pokonana. Przykładami tego postępu są elektromechaniczna maszyna George’a Stibitza, zbudowana w 1940 roku w Bell Laboratories, oraz Mark I, zbudowana w 1944 roku na Uniwersytecie Harvarda przez Howarda Aikena i grupę inżynierów IBM. Maszyny te w dużym stopniu wykorzystywały sterowane elektronicznie przekaźniki mechaniczne. W tym sensie były one przestarzałe niemal natychmiast po zbudowaniu, ponieważ inni badacze do budowy całkowicie elektronicznych komputerów wykorzystywali technologię lamp próżniowych. Pierwszą z tych maszyn z lampą próżniową była maszyna Atanasoffa–Berry’ego, skonstruowana w latach 1937–1941 w Iowa State College (obecnie Iowa State University) przez Johna Atanasoffa i jego asystenta Clifforda Berry’ego. Inną była maszyna o nazwie Colossus, zbudowana pod kierunkiem Tommy’ego Flowersa w Anglii do dekodowania niemieckich wiadomości w drugiej połowie II wojny światowej. (Faktycznie zbudowano aż dziesięć takich maszyn, ale tajemnica wojskowa i kwestie bezpieczeństwa narodowego uniemożliwiły ich zaistnienie w „komputerowym drzewie genealogicznym”). Wkrótce pojawiły się inne, bardziej elastyczne maszyny, takie jak ENIAC (Electronic Numerical Integrator and Computer) opracowany przez Johna Mauchly’ego i J. Prespera Eckerta w Moore School of Electrical Engineering (rysunek 0.4) na University of Pennsylvania.

Maszyna różnicowa Babbage’a

Maszyny zaprojektowane przez Charlesa Babbage’a były prawdziwymi zwiastunami współczesnego projektowania komputerów. Gdyby technologia była w stanie wyprodukować jego maszyny w sposób ekonomicznie opłacalny i gdyby zapotrzebowanie handlu i rządu w zakresie przetwarzania danych były na taką skalę jak dziś, pomysły Babbage’a mogłyby doprowadzić do rewolucji komputerowej w XIX wieku. W rzeczywistości za jego życia skonstruowano jedynie demonstracyjny model jego maszyny różnicowej. Ta maszyna określała wartości liczbowe, obliczając „kolejne różnice”. Wgląd w tę technikę możemy uzyskać, rozważając problem obliczania kwadratów liczb całkowitych. Zaczynamy od tego, że wiemy, że kwadrat 0 to 0, kwadrat 1 to 1, kwadrat 2 to 4, a kwadrat 3 to 9. Dzięki temu możemy wyznaczyć kwadrat 4 w następujący sposób (patrz poniższy schemat). Najpierw obliczamy różnice kwadratów, które już znamy: 1^2 – 0^2 = 1, 2^2 – 1^2 = 3 i 3^2 – 2^2 = 5. Następnie obliczamy różnice tych wyników: 3 – 1 = 2 i 5 – 3 = 2. Zauważmy, że obie te różnice wynoszą 2. Zakładając, że ta spójność będzie dalej prawdziwa (matematyka może pokazać, że tak jest), wnioskujemy, że różnica między wartością (4^2 – 3^2) a wartością (3^2 – 2^2) musi również wynosić 2. Zatem (4^2 – 3^2) musi być o 2 większe niż (3^2 – 2^2), więc 4^2 – 3^2 = 7 oraz 4^2 = 3^2 + 7 = 16. Teraz, gdy znamy kwadrat 4, możemy kontynuować naszą procedurę obliczania kwadratu 5, bazując na wartościach 1^2, 2^2, 3^2 i 4^2. (Chociaż głębsze omówienie pojęcia kolejnych różnic wykracza poza zakres naszej obecnej analizy, studenci rachunku różniczkowego mogą zauważyć, że poprzedni przykład jest oparty na fakcie, że pochodna funkcji y = x^2 jest linią prostą o nachyleniu 2).

Od tego momentu historia maszyn obliczeniowych jest ściśle powiązana z postępem technologicznym, w tym z wynalezieniem tranzystorów (za które fizycy William Shockley, John Bardeen i Walter Brattain otrzymali Nagrodę Nobla) i późniejszym rozwojem kompletnych obwodów jako pojedynczych jednostek zwanych układami scalonymi (za które Jack Kilby otrzymał również Nagrodę Nobla z fizyki). Dzięki tym rozwiązaniom maszyny wielkości pomieszczenia z lat 40. XX wieku zostały przez dziesięciolecia zredukowane do rozmiarów pojedynczych szafek. Jednocześnie moc obliczeniowa maszyn obliczeniowych zaczęła podwajać się co dwa lata (tendencja, która trwa do dziś). W miarę postępu prac nad układami scalonymi wiele komponentów komputera stało się łatwo dostępnych na wolnym rynku jako układy scalone zamknięte w plastikowych blokach wielkości klocków, zwanych czipami.

Ważnym krokiem w kierunku popularyzacji informatyki był rozwój komputerów stacjonarnych. Początków tych maszyn można doszukiwać się u hobbystów komputerowych, którzy z kombinacji czipów budowali komputery domowej roboty. To właśnie w tym „podziemiu” hobbystycznej działalności Steve Jobs i Stephen Wozniak zbudowali komercyjnie opłacalny komputer domowy, a w 1976 r. założyli firmę Apple Computer, Inc. (obecnie Apple Inc.), aby produkować i sprzedawać swoje produkty. Inne firmy, które sprzedawały podobne produkty, to Commodore, Heathkit i Radio Shack. Chociaż produkty te były popularne wśród hobbystów komputerowych, nie były powszechnie akceptowane przez społeczność biznesową, która aby zaspokoić większość swoich potrzeb obliczeniowych nadal zwracała uwagę na dobrze ugruntowaną firmę IBM i jej duże komputery typu mainframe.

W 1981 roku IBM wprowadził swój pierwszy komputer stacjonarny, zwany komputerem osobistym lub PC, którego podstawowe oprogramowanie zostało opracowane przez nowo utworzoną firmę znaną jako Microsoft. Komputer PC odniósł natychmiastowy sukces i sprawił, że komputer stacjonarny stał się uznanym towarem w świadomości społeczności biznesowej. Obecnie termin PC jest powszechnie używany w odniesieniu do wszystkich maszyn (od różnych producentów), których konstrukcja wyewoluowała z początkowego komputera stacjonarnego IBM. Większość z nich jest nadal sprzedawana z oprogramowaniem firmy Microsoft. Czasami jednak termin PC jest używany zamiennie z ogólnymi terminami typu komputer stacjonarny czy laptop.

Pod koniec XX wieku możliwość łączenia poszczególnych komputerów w ogólnoświatowy system zwany Internetem zrewolucjonizowała komunikację. W tym kontekście Tim Berners-Lee (brytyjski naukowiec) zaproponował system, za pomocą którego dokumenty przechowywane na komputerach w Internecie mogłyby być łączone ze sobą, tworząc labirynt powiązanych informacji zwany World Wide Web (w skrócie Web lub WWW). Aby udostępnić informacje w sieci, stworzono oprogramowanie, zwane wyszukiwarkami, które „przesiewa” sieć, „kategoryzuje” wyniki, a następnie przedstawia je użytkownikom poszukującym określonych tematów. Głównymi graczami w tej dziedzinie są Google, Yahoo i Microsoft. Firmy te nadal rozszerzają swoją działalność związaną z Internetem, często w kierunkach, które rzucają wyzwanie naszemu tradycyjnemu sposobowi myślenia.

Augusta Ada Byron

Augusta Ada Byron, hrabina Lovelace, była przedmiotem wielu komentarzy w społeczności komputerowej. Jej nieco tragiczne życie trwało niespełna 37 lat (1815–1852) i było skomplikowane przez zły stan zdrowia i fakt, że była nonkonformistką w społeczeństwie, które ograniczało zawodową rolę kobiet. Chociaż interesowała ją szeroka gama nauk ścisłych, skoncentrowała swoje studia na matematyce. Jej zainteresowanie „informatyką” zaczęło się od fascynacji maszyną różnicową Charlesa Babbage’a podczas demonstracji prototypu w 1833 roku. Jej wkład w informatykę wynika z przetłumaczenia z francuskiego na angielski artykułu omawiającego projekt maszyny analitycznej Babbage’a. Babbage zachęcił ją, aby do tego tłumaczenia dołączyła dodatek opisujący zastosowania maszyny i zawierający przykłady, jak można ją zaprogramować do wykonywania różnych zadań. Entuzjazm Babbage’a dla pracy Ady Byron był najwyraźniej motywowany nadzieją, że jej publikacja doprowadzi do finansowego wsparcia budowy jego maszyny analitycznej. (Jako córka Lorda Byrona, Ada Byron miała status celebrytki z potencjalnie znaczącymi powiązaniami finansowymi). To wsparcie nigdy się nie zmaterializowało, ale dodatek stworzony przez Adę Byron przetrwał i uważa się, że zawiera pierwsze przykłady programów komputerowych. Historycy dyskutują o stopniu, w jakim Babbage wpłynął na pracę Ady Byron. Niektórzy twierdzą, że Babbage wniósł duży wkład, a według innych był bardziej przeszkodą niż pomocą. Niemniej jednak Augusta Ada Byron jest dziś uznawana za pierwszą na świecie programistkę, co zostało potwierdzone przez Departament Obrony USA, gdy na jej cześć nazwał czołowy język programowania (Ada).

W tym samym czasie, gdy komputery stacjonarne i laptopy zostały zaakceptowane i zaczęły być używane w domach, postępowała miniaturyzacja maszyn liczących. Obecnie małe komputery są wbudowane w szerokiej gamie urządzeń, w tym urządzeń elektronicznych. Samochody mogą teraz zawierać dziesiątki małych komputerów obsługujących globalny system pozycjonowania (GPS), monitorujących pracę silnika i zapewniających usługi poleceń głosowych do sterowania systemami audio i komunikacji telefonicznej w samochodzie.

Być może najbardziej rewolucyjnym zastosowaniem miniaturyzacji komputerów są rosnące możliwości smartfonów, podręcznych komputerów ogólnego przeznaczenia, w których telefonia jest tylko jednym z wielu zastosowań. Wydajniejsze niż superkomputery z poprzednich dekad, te kieszonkowe urządzenia są wyposażone w bogatą gamę czujników i interfejsów, w tym kamery, mikrofony, kompasy, ekrany dotykowe, akcelerometry (do wykrywania orientacji i ruchu telefonu) oraz szereg bezprzewodowych technologii do komunikacji z innymi smartfonami i komputerami. Wielu twierdzi, że smartfon ma większy wpływ na globalne społeczeństwo niż rewolucja komputerów osobistych.

Google

Założona w 1998 roku firma Google LLC (dawniej Google Inc.) stała się jedną z najbardziej rozpoznawalnych firm technologicznych na świecie. Jej podstawowa usługa, wyszukiwarka Google, jest używana przez miliony ludzi do wyszukiwania dokumentów w sieci WWW. Ponadto Google oferuje usługę poczty elektronicznej (zwaną Gmail), internetową usługę udostępniania wideo (zwaną YouTube) oraz szereg innych usług internetowych (w tym Mapy Google, Kalendarz Google, Google Earth, Książki Google i Tłumacz Google).

Jednak oprócz tego, że jest doskonałym przykładem ducha przedsiębiorczości, Google dostarcza również przykładów tego, jak rozwój technologii stanowi wyzwanie dla społeczeństwa. Na przykład wyszukiwarka Google doprowadziła do pytań dotyczących zakresu, w jakim międzynarodowa firma powinna przestrzegać oczekiwań poszczególnych rządów; YouTube wywołał pytania dotyczące zakresu, w jakim firma powinna ponosić odpowiedzialność za informacje rozpowszechniane przez inne osoby za pośrednictwem tych usług, a także stopnia, w jakim firma może rościć sobie prawo własności do tych informacji; Książki Google wzbudziły obawy dotyczące zakresu i ograniczeń praw własności intelektualnej, a Mapy Google zostały oskarżone o naruszenie praw do prywatności.

0.3 Zawartość książki

Zawartość tej książki stanowi oddolne podejście do badania informatyki, zaczynając od takich praktycznych tematów, takich jak sprzęt komputerowy, a kończąc na bardziej abstrakcyjnych tematach, takich jak złożoność algorytmów i obliczenia. W rezultacie nasze badanie podąża za wzorcem budowania coraz większych abstrakcyjnych narzędzi w miarę poszerzania się naszego rozumienia tematu.

Zaczniemy od rozważenia tematów dotyczących projektowania i budowy maszyn służących do wykonywania algorytmów. W rozdziale 1 („Przechowywanie danych”) przyjrzymy się, jak informacje są zapisywane i przechowywane we współczesnych komputerach, zaś w rozdziale 2 („Operowanie danymi”) zbadamy podstawy wewnętrznego działania prostego komputera. Chociaż część tego operowania obejmuje technologię, główny temat jest jednak od niej niezależny. Oznacza to, że takie tematy, jak projektowanie układów cyfrowych, systemy kodowania i kompresji danych oraz architektura komputerów będą dotyczyły szerokiego zakresu technologii, w związku z czym pozostaną aktualne niezależnie od kierunku jej przyszłego rozwoju.

W rozdziale 3 („Systemy operacyjne”) zbadamy oprogramowanie, które steruje ogólnym działaniem komputera. To oprogramowanie nazywa się systemem operacyjnym. System operacyjny komputera steruje interfejsem między maszyną a jej światem zewnętrznym, chroniąc maszynę i przechowywane w niej dane przed nieautoryzowanym dostępem, umożliwiając użytkownikowi komputera wykonywanie różnych programów i koordynuje wymagane działania wewnętrzne w celu spełniania żądań użytkownika.

W rozdziale 4 („Sieć i Internet”) zbadamy, w jaki sposób komputery są ze sobą łączone w celu utworzenia sieci komputerowych oraz w jaki sposób łączone są sieci w celu utworzenia internetów. Analiza poprowadzi do takich tematów, jak protokoły sieciowe, struktura i wewnętrzne działanie Internetu, sieć WWW oraz liczne kwestie bezpieczeństwa.

Rozdział 5 („Algorytmy”) wprowadza do badania algorytmów z bardziej formalnej perspektywy. Zapoznamy się ze sposobem odkrywania algorytmów, wskażemy kilka podstawowych struktur algorytmicznych, rozwiniemy elementarne techniki reprezentacji algorytmów oraz wprowadzimy tematy dotyczące wydajności i poprawności algorytmów.

W rozdziale 6 („Języki programowania”) rozważymy temat reprezentacji algorytmów i proces tworzenia programu. Przekonamy się, że poszukiwanie lepszych technik programowania doprowadziło do powstania różnych metodologii lub paradygmatów programowania, z których każdy zawiera własny zbiór języków programowania. Zbadamy te paradygmaty oraz języki, a także rozważymy problemy translacji gramatycznej i językowej.

Rozdział 7 („Inżynieria oprogramowania”) przedstawi dziedzinę informatyki znaną jako inżynieria oprogramowania, która zajmuje się problemami napotykanymi podczas tworzenia dużych systemów oprogramowania. Motywem przewodnim jest to, że ich projektowanie jest złożonym zadaniem, które obejmuje problemy wykraczające poza te związane z tradycyjną inżynierią. Tym samym tematyka inżynierii oprogramowania staje się ważnym obszarem badań w dziedzinie informatyki, czerpiąc z tak różnorodnych dziedzin, jak inżynieria, zarządzanie projektami, zarządzanie zasobami ludzkimi, projektowanie języków programowania, a nawet architektura.

W następnych dwóch rozdziałach przyjrzymy się sposobom organizowania danych w systemie komputerowym. W rozdziale 8 („Abstrakcje danych”) przedstawimy tradycyjne techniki używane do organizowania danych w pamięci głównej komputera, a następnie prześledzimy ewolucję abstrakcji danych od koncepcji prymitywów do współczesnych technik obiektowych. W rozdziale 9 („Systemy baz danych”) rozważymy tradycyjne metody stosowane do organizowania danych w pamięci masowej komputera i zbadamy, jak tworzone są niezwykle duże i złożone systemy baz danych.

W rozdziale 10 („Grafika komputerowa”) zgłębimy temat grafiki i animacji, dziedziny zajmującej się tworzeniem i fotografowaniem wirtualnych światów. Opierając się na postępach w bardziej tradycyjnych dziedzinach informatyki, takich jak architektura maszyn, projektowanie algorytmów, struktury danych i inżynieria oprogramowania, dyscyplina grafiki i animacji odnotowała znaczny postęp i obecnie rozkwitła w ekscytujący, dynamiczny obszar. Co więcej, ta dziedzina pokazuje, w jaki sposób różne elementy informatyki łączą się z innymi dyscyplinami, takimi jak fizyka, sztuka i fotografia, w celu uzyskania niesamowitych efektów.

W rozdziale 11 („Sztuczna inteligencja”) dowiemy się, że aby opracować bardziej użyteczne maszyny, informatyka w poszukiwaniu inspiracji zwróciła się ku badaniu ludzkiej inteligencji. Istnieje nadzieja, że dzięki zrozumieniu, w jaki sposób nasze własne umysły rozumują i postrzegają, naukowcy będą w stanie zaprojektować algorytmy naśladujące te procesy, a tym samym przenieść porównywalne możliwości na maszyny. Rezultatem jest dziedzina informatyki znana jako sztuczna inteligencja, która w dużym stopniu opiera się na badaniach w takich dziedzinach, jak psychologia, biologia i językoznawstwo.

Nasze rozważania zamkniemy rozdziałem 12 („Teoria obliczalności”), badając teoretyczne podstawy informatyki – jest to temat, który pozwoli nam zrozumieć ograniczenia algorytmów (a tym samym maszyn). W tym miejscu wskażemy kilka problemów, których nie można rozwiązać algorytmicznie (a zatem leżą poza możliwościami maszyn), a także dowiemy się, że rozwiązania wielu innych problemów wymagają tak ogromnego czasu lub miejsca, że z praktycznego punktu widzenia są również nierozwiązywalne. Dzięki temu będziemy w stanie uchwycić zakres i ograniczenia systemów algorytmicznych.

W każdym rozdziale naszym celem będzie dogłębne zbadanie tematu, aby umożliwić jego właściwe zrozumienie. Chcemy rozwinąć praktyczną wiedzę z zakresu informatyki – wiedzę, która pozwoli ci zrozumieć techniczne społeczeństwo, w którym żyjesz, i zapewni podstawę, na której możesz uczyć się samodzielnie w miarę postępu nauki i technologii.

0.4 Nadrzędne zagadnienia informatyki

Oprócz wymienionych powyżej głównych tematów poszczególnych rozdziałów, mamy również nadzieję poszerzyć wiedzę o informatyce poprzez włączenie kilku nadrzędnych tematów. Miniaturyzacja komputerów i ich rosnące możliwości sprawiły, że technologia komputerowa stała się istotnym elementem współczesnych społeczeństw. Jest ona tak powszechna, że znajomość jej ma fundamentalne znaczenie dla bycia członkiem współczesnego świata. Technologia komputerowa zmieniła zdolność rządów do sprawowania kontroli; miała ogromny wpływ na światową ekonomię; doprowadziła do zaskakujących postępów w badaniach naukowych; zrewolucjonizowała rolę gromadzenia, przechowywania i zastosowania danych; zapewniła ludziom nowe sposoby komunikowania się i interakcji oraz wielokrotnie podważyła status quo społeczeństwa. Rezultatem jest mnożenie się zagadnień związanych z informatyką, z których każdy jest teraz sam w sobie znaczącym kierunkiem studiów. Co więcej, podobnie jak w przypadku inżynierii mechanicznej i fizyki, często trudno jest oddzielić te dziedziny od samej informatyki. Tak więc, aby uzyskać właściwą perspektywę, nasze studium obejmie nie tylko tematy kluczowe dla rdzenia informatyki, ale także zbada różne dyscypliny zajmujące się zarówno zastosowaniami, jak i konsekwencjami nauki. W rzeczywistości wprowadzenie do informatyki jest przedsięwzięciem interdyscyplinarnym.

Rozpoczynając eksplorację informatyki, warto pamiętać o głównych pojęciach, które łączą tę dziedzinę. Mimo że kodyfikacja „Siedmiu wielkich idei informatyki” nastąpiła po pierwszych dziesięciu wydaniach tej książki, są one ściśle zbieżne z tematami kolejnych rozdziałów. „Siedem wielkich idei” to w skrócie: Algorytmy, Abstrakcja, Kreatywność, Dane, Programowanie, Internet i Wpływ. W kolejnych rozdziałach zawarliśmy różne zagadnienia, w każdym przypadku wprowadzając główne idee danego zagadnienia, przedstawiając aktualne obszary badań i niektóre techniki stosowane do pogłębiania wiedzy w tym obszarze. Zwracajcie uwagę na „Wielkie idee”, gdyż będziemy do nich wracać raz po raz.

Algorytmy

Ograniczone możliwości przechowywania danych i skomplikowane, czasochłonne procedury ograniczały złożoność algorytmów stosowanych we wczesnych maszynach obliczeniowych. Jednak gdy ograniczenia te zaczęły zanikać, maszyny zaczęły być stosowane do coraz większych i bardziej skomplikowanych zadań. Ponieważ próby wyrażania struktury takich zadań w formie algorytmicznej zaczęły przekraczać zdolności ludzkiego umysłu, coraz więcej wysiłków badawczych skierowano na badanie algorytmów i procesu programowania.

W tym kontekście teoretyczna praca matematyków zaczęła przynosić korzyści. W konsekwencji twierdzenia Gödla o niezupełności matematycy prowadzili już analizę kwestii dotyczących procesów algorytmicznych, które teraz zaczęły się pojawiać wraz z postępem technologicznym. W ten sposób przygotowano grunt pod powstanie nowej dyscypliny, zwanej informatyką.

Obecnie informatyka stała się nauką o algorytmach. Zakres tej nauki jest szeroki i czerpie z tak różnorodnych obszarów, takich jak matematyka, inżynieria, psychologia, biologia, zarządzanie biznesowe i językoznawstwo. Badacze z różnych obszarów informatyki mogą mieć bardzo różne definicje tej nauki. Na przykład badacz zajmujący się architekturą komputerową może skupić się na zadaniu miniaturyzacji układów, a tym samym postrzegać informatykę jako postęp i zastosowanie technologii. Ale badacz zajmujący się systemami baz danych może postrzegać informatykę jako poszukiwanie sposobów na zwiększenie użyteczności systemów informatycznych. A badacz zajmujący się sztuczną inteligencją może uważać informatykę za badanie inteligencji i inteligentnych zachowań.

Niemniej jednak wszyscy ci badacze są zaangażowani w aspekty nauki o algorytmach. Biorąc pod uwagę kluczową rolę, jaką algorytmy odgrywają w informatyce (patrz rysunek 0.5), warto wskazać kilku pytań, na których będziemy się skupiać w naszych badaniach nad tą wielką ideą.

• Jakie problemy można rozwiązać za pomocą procesów algorytmicznych?

• Jak można ułatwić odkrywanie algorytmów?

• W jaki sposób można ulepszyć techniki przedstawiania i opisywania algorytmów?

• W jaki sposób można analizować i porównywać charakterystyki różnych algorytmów?

• W jaki sposób można wykorzystać algorytmy do operowania informacjami?

• W jaki sposób można zastosować algorytmy do tworzenia inteligentnych zachowań?

• Jak zastosowanie algorytmów wpływa na społeczeństwo?

Abstrakcja

Termin abstrakcja, tak jak będziemy go tu używać, odnosi się do rozróżnienia między zewnętrznymi właściwościami jednostki a szczegółami jej budowy wewnętrznej. Jest to abstrakcja, która pozwala nam pominąć wewnętrzne szczegóły złożonego urządzenia, takiego jak komputer, samochód czy kuchenka mikrofalowa, i wykorzystać je jako jedną, zrozumiałą całość. Co więcej, to właśnie w pierwszej kolejności za pomocą abstrakcji projektuje się i produkuje takie złożone systemy. Komputery, samochody i kuchenki mikrofalowe są zbudowane z komponentów, z których każdy reprezentuje poziom abstrakcji, na którym użycie komponentu jest oddzielone od szczegółów jego budowy wewnętrznej.

To dzięki zastosowaniu abstrakcji jesteśmy w stanie konstruować, analizować i zarządzać dużymi, złożonymi systemami komputerowymi, które byłyby przytłaczające, gdyby spojrzeć na nie w całości na poziomie szczegółowym. Na każdym poziomie abstrakcji patrzymy na system w kategoriach komponentów, zwanych abstrakcyjnymi narzędziami, których strukturę wewnętrzną ignorujemy. To pozwala nam skoncentrować się na tym, jak każdy komponent współdziała z innymi komponentami na tym samym poziomie i jak zestaw jako całość tworzy komponent wyższego poziomu. Dzięki temu jesteśmy w stanie zrozumieć część systemu, która jest istotna dla danego zadania, a nie gubimy się w morzu szczegółów.

Podkreślmy, że abstrakcja nie ogranicza się do nauki i technologii. Jest to ważna technika upraszczania, dzięki której nasze społeczeństwo stworzyło styl życia, który w innym przypadku byłby niemożliwy. Niewielu z nas rozumie, w jaki sposób wdrażane są różne udogodnienia codziennego życia. Spożywamy żywność i nosimy ubrania, których sami nie jesteśmy w stanie wyprodukować. Używamy urządzeń elektrycznych i systemów komunikacyjnych, nie rozumiejąc technologii, na której się opierają. Korzystamy z usług innych osób, nie znając szczegółów ich zawodów. Z każdym nowym postępem niewielka część społeczeństwa postanawia specjalizować się w jego wdrażaniu, podczas gdy reszta z nas uczy się korzystać z wyniki jako abstrakcyjne narzędzia. W ten sposób rozszerza się magazyn abstrakcyjnych narzędzi społeczeństwa, a zdolność społeczeństwa do postępu wzrasta.

Rysunek 0.5 Centralna rola algorytmów w informatyce

Abstrakcja jest powracającym filarem naszej analizy. Dowiemy się, że narzędzia obliczeniowe są konstruowane z użyciem abstrakcyjnych narzędzi. Zobaczymy również, że rozwój dużych systemów oprogramowania odbywa się w sposób modułowy, gdzie każdy moduł jest używany jako abstrakcyjne narzędzie w większych modułach. Co więcej, abstrakcja odgrywa ważną rolę w zadaniu rozwoju samej informatyki, umożliwiając naukowcom skupienie uwagi na określonych obszarach w tej złożonej dziedzinie. Tę cechę nauki odzwierciedla układ tej książki. Każdy rozdział, który koncentruje się na określonym obszarze nauki, jest często zaskakująco niezależny od pozostałych, jednak razem rozdziały tworzą kompleksowy przegląd tej rozległej dziedziny nauki.

Kreatywność

Mimo że komputery są jedynie złożonymi maszynami mechanicznie wykonującymi rutynowe instrukcje algorytmiczne, zobaczymy, że dziedzina informatyki jest z natury twórcza. Odkrywanie i stosowanie nowych algorytmów to ludzkie działanie, które zależy od naszego wrodzonego pragnienia, aby stosować nasze narzędzia do rozwiązywania problemów w otaczającym nas świecie. Informatyka nie tylko rozszerza formy ekspresji obejmujące sztukę wizualną, językową i muzyczną, ale także umożliwia nowe sposoby ekspresji cyfrowej, które przenikają współczesny świat.

Tworzenie dużych systemów oprogramowania w mniejszym stopniu przypomina postępowanie według przepisu z książki kucharskiej, a bardziej wymyślanie wielkiej nowej rzeźby. Wyobrażenie sobie jego formy i funkcji wymaga starannego zaplanowania. Wykonanie jego elementów wymaga czasu, dbałości o szczegóły i wyćwiczonych umiejętności. Produkt finalny ucieleśnia estetykę projektowania i wrażliwość jego twórców.

Dane

Komputery są w stanie reprezentować wszelkie informacje, które można dyskretyzować i digitalizować. Algorytmy mogą przetwarzać lub przekształcać takie cyfrowo reprezentowane informacje na wiele różnych sposobów. Rezultatem tego jest nie tylko przenoszenie danych cyfrowych z jednej części komputera do drugiej; komputerowe algorytmy umożliwiają nam wyszukiwanie wzorców, tworzenie symulacji i korelację połączeń w sposób, który generuje nową wiedzę i wnioski. Ogromne pojemności pamięci masowej, szybkie sieci komputerowe i potężne narzędzia obliczeniowe napędzają odkrycia w wielu innych dyscyplinach nauki, inżynierii i naukach humanistycznych. Niezależnie od tego, czy przewidujemy skutki nowego leku, symulując złożone fałdowanie białek, analizując statystycznie ewolucję języka na przestrzeni wieków, korzystając ze zdigitalizowanych książek, czy też renderując trójwymiarowe obrazy narządów wewnętrznych z nieinwazyjnego skanu medycznego, dane napędzają nowoczesne odkrycia w całej gamie ludzkich dążeń.

Oto niektóre z pytań dotyczących danych, które zgłębimy w naszej analizie:

• W jaki sposób komputery przechowują dane o typowych artefaktach cyfrowych, takich jak liczby, tekst, obrazy, dźwięki i wideo?

• W jaki sposób komputery aproksymują dane o artefaktach analogowych ze świata rzeczywistego?

• W jaki sposób komputery wykrywają i zapobiegają błędom w danych?

• Jakie są konsekwencje stale rosnącego i wzajemnie połączonego cyfrowego wszechświata danych, jakimi dysponujemy?

Programowanie

Przekładanie ludzkich intencji na wykonywalne algorytmy komputerowe jest obecnie powszechnie określane jako programowanie, chociaż rozpowszechnienie dostępnych języków i narzędzi w niewielkim stopniu przypomina programowalne komputery z lat pięćdziesiątych i wczesnych sześćdziesiątych. Podczas gdy informatyka to znacznie więcej niż programowanie komputerów, umiejętność rozwiązywania problemów poprzez opracowywanie wykonywalnych algorytmów (programów) pozostaje podstawową umiejętnością wszystkich informatyków.

Sprzęt komputerowy jest w stanie wykonać tylko stosunkowo proste kroki algorytmiczne, ale abstrakcje dostarczane przez języki programowania komputerowego pozwalają ludziom formułować i zapisywać rozwiązania znacznie bardziej złożonych problemów. Naszą dyskusję na ten temat ukierunkuje kilka kluczowych pytań:

• Jak budowane są programy?

• Jakie rodzaje błędów mogą pojawić się w programach?

• Jak znajdowane i naprawiane są błędy w programach?

• Jakie są skutki błędów we współczesnych programach?

• W jaki sposób programy są dokumentowane i oceniane?

Internet

Internet łączy komputery i urządzenia elektroniczne na całym świecie i ma ogromny wpływ na sposób, w jaki nasze społeczeństwo technologiczne przechowuje, pobiera i udostępnia informacje. Handel, wiadomości, rozrywka i komunikacja w coraz większym stopniu zależą od tej połączonej sieci mniejszych sieci komputerowych. W naszej dyskusji nie tylko będziemy opisywać mechanizmy Internetu jako artefaktu, ale także poruszymy wielu aspektów społeczeństwa, które są teraz splecione z globalną siecią.

Zasięg Internetu ma również głęboki wpływ na naszą prywatność i bezpieczeństwo naszych danych osobowych. Cyberprzestrzeń kryje w sobie wiele niebezpieczeństw. W związku z tym kryptografia i cyberbezpieczeństwo mają coraz większe znaczenie w naszym połączonym świecie.

Wpływ

Informatyka ma nie tylko głęboki wpływ na technologie, których używamy do komunikacji, pracy i zabawy. Ma też ogromne reperkusje społeczne. Postęp w informatyce zaciera wiele różnic, na których nasze społeczeństwo opierało decyzje w przeszłości, i kwestionuje wiele od dawna utrzymywanych zasad społecznych. W świetle prawa rodzi pytania dotyczące stopnia, w jakim można posiadać własność intelektualną, oraz praw i zobowiązań, które tej własności towarzyszą. W etyce generuje wiele okazji podważających tradycyjne zasady, na których opierają się zachowania społeczne. Dla rządzących wywołuje debaty dotyczące zakresu, w jakim technologia komputerowa i jej zastosowania powinny być regulowane. W filozofii generuje spór między obecnością inteligentnego zachowania a obecnością samej inteligencji. A w całym społeczeństwie generuje spory dotyczące tego, czy nowe zastosowania tworzą nowe wolności czy nowe mechanizmy kontroli.

Takie tematy są ważne dla osób rozważających karierę w informatyce lub dziedzinach związanych z informatyką. Odkrycia naukowe czasami znajdowały kontrowersyjne zastosowania, wywołując poważne niezadowolenie zaangażowanych w nie badaczy. Co więcej, udana kariera może szybko zostać przerwana przez błąd etyczny.

Umiejętność radzenia sobie z dylematami wynikającymi z postępu technologii komputerowej jest również ważna dla osób spoza jej najbliższego otoczenia. W rzeczywistości technologia infiltruje społeczeństwo tak szybko, że niewielu, jeśli w ogóle tacy są, jest niezależnych od jej skutków.

Ta książka oferuje podstawy techniczne potrzebne do racjonalnego podejścia do dylematów generowanych przez informatykę. Jednak sama wiedza techniczna o nauce nie zapewnia rozwiązania wszystkich związanych z nią pytań. Mając to na uwadze, niniejsza książka zawiera wiele podrozdziałów poświęconych społecznym, etycznym i prawnym skutkom informatyki. Dotyczą one kwestii bezpieczeństwa, własności oprogramowania i odpowiedzialności, społecznego wpływu technologii baz danych oraz konsekwencji postępu w sztucznej inteligencji.

Co więcej, często nie ma ostatecznej, poprawnej odpowiedzi na problem, a wiele rozwiązań to kompromisy między przeciwstawnymi (i być może równie ważnymi) poglądami. Znalezienie rozwiązań w takich przypadkach często wymaga umiejętności słuchania, rozpoznawania innych punktów widzenia, prowadzenia racjonalnej debaty i zmieniania własnej opinii w miarę zdobywania nowej wiedzy. Dlatego każdy rozdział tej książki, pod nagłówkiem „Kwestie społeczne”, kończy się zbiorem pytań, które badają relacje między informatyką a społeczeństwem. Niekoniecznie są to pytania, na które należy odpowiedzieć. Są to raczej pytania do rozważenia. W wielu przypadkach odpowiedź, która na pierwszy rzut oka może wydawać się oczywista, przestanie nas zadowalać, gdy będziemy badać alternatywy. Krótko mówiąc, celem tych pytań nie jest poprowadzenie nas do „poprawnej” odpowiedzi, ale raczej zwiększenie świadomości, w tym świadomości różnych interesariuszy w danej kwestii, świadomości alternatyw i krótko-, jak i długoterminowych konsekwencji tych alternatyw.

Filozofowie wprowadzili wiele podejść do etyki, poszukując fundamentalnych teorii, które prowadzą do zasad kierowania decyzjami i zachowaniem.

Etyka charakteru (czasami nazywana etyką cnót) była promowana przez Platona i Arystotelesa, którzy twierdzili, że „dobre zachowanie” nie jest wynikiem stosowania możliwych do określenia reguł, ale jest naturalną konsekwencją „dobrego charakteru”. Podczas gdy inne podstawy etyczne, takie jak etyka oparta na konsekwencjach, etyka oparta na obowiązkach i etyka oparta na umowach, proponują, aby osoba rozwiązała dylemat etyczny, stawiając odpowiednie pytania: „Jakie są konsekwencje?”, „Jakie są moje obowiązki?” lub „Jakie mam zobowiązania?”, etyka charakteru proponuje, aby dylematy rozwiązywać, pytając: „Kim chcę być?”. Dobre zachowanie uzyskuje się zatem poprzez budowanie dobrego charakteru, co jest zazwyczaj wynikiem zdrowego wychowania i wyrobienia cnotliwych nawyków.

To etyka charakteru leży u podstaw podejścia zwykle przyjmowanego podczas „uczenia” etyki profesjonalistów z różnych dziedzin. Zamiast przedstawiać konkretne teorie etyczne, podejście polega na wprowadzeniu studiów przypadku, które ujawniają różnorodne pytania etyczne w obszarze wiedzy fachowej profesjonalistów. Następnie, omawiając plusy i minusy w tych przypadkach, profesjonaliści stają się bardziej świadomi, wnikliwi i wrażliwi na niebezpieczeństwa czyhające w ich życiu zawodowym, a tym samym zyskują na charakterze. W takim duchu prezentowane są pytania dotyczące kwestii społecznych na końcu każdego rozdziału.

Kwestie społeczne

Poniższe pytania mają służyć jako przewodnik po kwestiach etycznych/społecznych/prawnych związanych z informatyką. Celem nie jest tylko udzielenie odpowiedzi na te pytania. Należy także zastanowić się, dlaczego twoja odpowiedź jest taka, a nie inna, i czy twoje uzasadnienia są spójne w kolejnych pytaniach.

1. Powszechnie przyjmuje się założenie, że nasze społeczeństwo różni się od tego, jakie byłoby bez rewolucji komputerowej. Czy nasze społeczeństwo jest lepsze, niż byłoby bez rewolucji? Czy nasze społeczeństwo jest gorsze? Czy twoja odpowiedź byłaby inna, gdyby twoja pozycja w społeczeństwie była inna?

2. Czy można uczestniczyć w dzisiejszym społeczeństwie technologicznym, nie podejmując wysiłku zrozumienia podstaw tej technologii? Na przykład, czy członkowie społeczności, których głosy często decydują o tym, jak technologia będzie wspierana i wykorzystywana, mają obowiązek starać się ją zrozumieć? Czy twoja odpowiedź zależy od rozważanej technologii? Na przykład, czy twoja odpowiedź jest będzie taka sama, przy rozważaniu technologii jądrowej, jak w przypadku technologii komputerowej?

3. Używając gotówki w transakcjach finansowych, osoby fizyczne miały tradycyjnie możliwość zarządzania swoimi sprawami finansowymi bez opłat za usługi. Jednak w miarę jak coraz większa część naszej gospodarki staje się zautomatyzowana, instytucje finansowe wprowadzają opłaty za dostęp do tych zautomatyzowanych systemów. Czy istnieje moment, w którym opłaty te niesprawiedliwie ograniczają dostęp jednostki do gospodarki? Załóżmy na przykład, że pracodawca płaci pracownikom tylko czekiem, a wszystkie instytucje finansowe pobierają opłatę za obsługę i deponowanie czeków. Czy pracownicy byliby niesprawiedliwie traktowani? Co się stanie, jeśli pracodawca będzie wymagał płacenia za pomocą bezpośrednich przelewów na konto?

4. W jakim stopniu firma powinna mieć możliwość pozyskiwania informacji od dzieci (być może za pomocą interaktywnego formatu gry) w kontekście telewizji interaktywnej? Na przykład, czy firma powinna mieć możliwość uzyskania od dziecka raportu na temat wzorców zakupowych jego rodziców? A co z informacjami o dziecku?

5. W jakim stopniu władze powinny regulować technologię komputerową i jej zastosowania? Rozważ, na przykład, kwestie wskazane w pytaniach 3 i 4. Co uzasadnia regulacje rządowe?

6. W jakim stopniu nasze decyzje dotyczące technologii w ogóle, a technologii komputerowej w szczególności, wpłyną na przyszłe pokolenia?

7. Wraz z postępem technologicznym nasz system edukacji nieustannie musi ponownie rozważać poziomy abstrakcji, na których prezentowane są pewne tematy. Wiele pytań dotyczy tego, czy umiejętność jest nadal potrzebna, czy też uczniowie powinni mieć możliwość polegania na abstrakcyjnym narzędziu. Studenci trygonometrii nie są już uczeni znajdowania wartości funkcji trygonometrycznych za pomocą tabel. Zamiast tego do znajdowania tych wartości używają kalkulatorów jako abstrakcyjnych narzędzi. Niektórzy twierdzą, że dzielenie nad kreską powinno również ustąpić miejsca abstrakcji. Jakich innych tematów dotyczą podobne kontrowersje? Czy współczesne edytory tekstu eliminują potrzebę rozwijania umiejętności ortograficznych? Czy zastosowanie technologii wideo wyeliminuje kiedyś potrzebę czytania?

8. Koncepcja bibliotek publicznych opiera się w dużej mierze na założeniu, że wszyscy obywatele powinni mieć dostęp do informacji. Ponieważ coraz więcej informacji jest przechowywanych i rozpowszechnianych za pomocą technologii komputerowej, czy dostęp do tej technologii staje się prawem każdej osoby? Jeśli tak, to czy biblioteki publiczne powinny być kanałem, przez który ten dostęp jest oferowany?

9. Jakie problemy etyczne pojawiają się w społeczeństwie, które opiera się na wykorzystywaniu abstrakcyjnych narzędzi? Czy są przypadki, w których nieetyczne jest korzystanie z produktu lub usługi bez zrozumienia, jak ono działa? Bez wiedzy, jak jest produkowane? Lub bez zrozumienia efektów ubocznych jego użycia?

10. W miarę jak społeczeństwa coraz więcej korzystają z automatyki, władzom łatwiej jest monitorować działania swoich obywateli. Czy to dobrze czy źle?

11. Jakie technologie, które wymyślił George Orwell (Eric Blair) w jego powieści Rok 1984, stały się rzeczywistością? Czy są używane w sposób, w jaki przewidział Orwell?

12. Gdybyś miał wehikuł czasu, to w jakim okresie historii chciałbyś żyć? Czy są obecne technologie, które chciałbyś ze sobą zabrać? Czy wybrana przez ciebie technologia mogłaby zostać zabrana bez zabierania innych? W jakim stopniu można oddzielić jedną technologię od innej? Czy konsekwentne jest protestowanie przeciwko globalnemu ociepleniu, a jednocześnie akceptowanie nowoczesnego leczenia?

13. Załóżmy, że twoja praca wymaga zamieszkania w innej kulturze. Czy masz nadal praktykować etykę swojej rodzimej kultury, czy przyjąć etykę kultury przyjmującej? Czy twoja odpowiedź zależy od tego, czy problem dotyczy ubioru, czy praw człowieka? Jakie standardy etyczne powinny panować, jeśli nadal żyjemy w swojej rodzimej kulturze, ale prowadzimy biznes z obcą kulturą w Internecie?

14. Czy społeczeństwo stało się zbyt zależne od aplikacji komputerowych służących do handlu, komunikacji lub interakcji społecznych? Na przykład, jakie byłyby konsekwencje długotrwałej przerwy w dostępie do Internetu i/lub telefonii komórkowej?

15. Większość smartfonów jest w stanie ustalić swoją lokalizację za pomocą GPS. Umożliwia to aplikacjom dostarczanie informacji związanych z otoczeniem (takich jak lokalne wiadomości, lokalna pogoda lub obecność firm w najbliższej okolicy) na podstawie bieżącej lokalizacji telefonu. Jednak takie funkcje GPS mogą również umożliwiać innym aplikacjom przekazywanie lokalizacji telefonu innym osobom. Czy to dobrze? Jak można nadużyć wiedzy o lokalizacji telefonu (a więc naszej lokalizacji)?

Dodatkowe materiały

Goldstine H.H., The Computer from Pascal to von Neumann. Princeton, NJ: Princeton University Press, 1972.

Haigh T., Priestley M., Rope C., ENIAC in Action: Making and Remaking the Modern Computer. Cambridge, MA: The MIT Press, 2016.

Kizza J.M., Ethical and Social Issues in the Information Age, 5th ed. London: Springer-Verlag, 2013.

Mollenhoff C.R., Atanasoff: Forgotten Father of the Computer. Ames, IA: Iowa State University Press, 1988.

Neumann P.G., Computer Related Risks. Boston, MA: Addison-Wesley, 1995.

Quinn M.J., Ethics for the Information Age, 7th ed. Essex, England: Pearson, 2016.

Randell B., The Origins of Digital Computers, 3rd ed. New York: Springer-Verlag, 1982.

Spinello R.A., Tavani H.T., Readings in CyberEthics, 2nd ed. Sudbury, MA: Jones and Bartlett, 2004.

Swade D., The Difference Engine, New York: Viking, 2000.

Tavani H.T., Ethics and Technology: Controversies, Questions, and Strategies for Ethical Computing, 5th ed. New York: Wiley, 2016.

Woolley B., The Bride of Science: Romance, Reason, and Byron’s Daughter, New York: McGraw-Hill, 1999.

Rozdział 1

Przechowywanie danych

W tym rozdziale rozważymy tematy związane z reprezentacją danych i ich przechowywaniem w komputerze. Rodzaje danych, które będziemy brać pod uwagę, obejmują tekst, wartości liczbowe, obrazy, dźwięk i wideo. Wiele informacji znajdujących się w tym rozdziale będzie dotyczyć również dziedzin innych niż tradycyjna informatyka, takich jak fotografia cyfrowa, nagrywanie i odtwarzanie audio/wideo oraz komunikacja na duże odległości. ■

1.1    Bity i ich przechowywanie

Operacje logiczne

Bramki i przerzutniki

Notacja szesnastkowa

1.2    Pamięć główna

Organizacja pamięci

Mierzenie pojemności pamięci

1.3    Pamięć masowa

Systemy magnetyczne

Systemy optyczne

Pamięci flash

1.4    Przedstawianie informacji w postaci bitów

Przedstawianie tekstu

Przedstawianie wartości liczbowych

Przedstawianie obrazów

Przedstawianie dźwięków

* 1.5    System binarny

Notacja binarna

Dodawanie binarne

Ułamki w notacji binarnej

* 1.6    Przechowywanie liczb całkowitych

Notacja uzupełnień do dwóch

Dodawanie w notacji uzupełnień do dwóch

Problem przepełnienia

Notacja nadmiarowa

* 1.7    Przechowywanie ułamków

Notacja zmiennoprzecinkowa

Błędy obcięcia

* 1.8    Dane i programowanie

Pierwsze kroki w Pythonie

Hello, Python

Zmienne

Operatory i wyrażenia

Konwersja walut

Debugowanie

* 1.9    Kompresja danych

Ogólne techniki kompresji danych

Kompresowanie obrazów

Kompresowanie audio i wideo

* 1.10    Błędy komunikacji

Bity parzystości

Kody korekcji błędów

* Gwiazdki oznaczają sugestie podrozdziałów opcjonalnych

Rozumienie kluczowych kwestii i efekty kształcenia

Informatyka umożliwia ludziom korzystanie z kreatywnych procesów rozwoju do tworzenia artefaktów obliczeniowych dla twórczej ekspresji lub rozwiązywania problemów. AP® CSP

EK. Utworzenie artefaktu obliczeniowego dla twórczej ekspresji.

Do przedstawiania wszystkich danych cyfrowych można użyć różnych abstrakcji zbudowanych na ciągach binarnych. AP® CSP

EK. Opisanie różnorodnych abstrakcji używanych do przedstawiania danych.

EK. Wyjaśnienie, w jaki sposób ciągi binarne są używane do przedstawiania danych cyfrowych.

Do pisania programów lub tworzenia innych artefaktów obliczeniowych używa się wielu poziomów abstrakcji. AP® CSP

EK. Określenie różnych poziomów abstrakcji używanych podczas pisania programów.

Przedstawianie informacji jako danych cyfrowych wymaga kompromisów. AP® CSP

EK. Analizowanie, w jaki sposób przedstawiania, przechowywanie, bezpieczeństwo i transmisja danych wiążą się z obróbką informacji.

Programowanie ułatwiają odpowiednie abstrakcje. AP® CSP

EK. Użycie abstrakcji do zarządzania złożonością programów.

Programy są tworzone, utrzymywane i używane przez ludzi do różnych celów. AP® CSP

EK. Ocena poprawności programu.

Programowanie wykorzystuje pojęcia matematyczne i logiczne. AP® CSP

EK. Zastosowanie odpowiednich pojęć matematycznych i logicznych w programowaniu.

Ludzie używają komputerów do tworzenia. Programy, media cyfrowe, treści internetowe, zbiory danych, modele i symulacje – wszystko to są przykłady artefaktów obliczeniowych, które ludzie tworzą za pomocą narzędzi obliczeniowych i abstrakcji. Nasze badanie informatyki rozpoczniemy od analizy, w jaki sposób te artefakty obliczeniowe są zapisywane i przechowywane w komputerach. Naszym pierwszym krokiem będzie omówienie podstaw komputerowych urządzeń do przechowywania danych, a następnie przeanalizowanie sposobów zapisu informacji w celu ich przechowywania w tych systemach. Złożoność tych systemów wymaga potężnych abstrakcji na wielu poziomach, począwszy od najprostszych bramek sprzętowych zbudowanych z przełączników aż po wysokopoziomowe języki programowania, których używamy do zapisu naszych poleceń jako programu dla komputera.

Najważniejsze informacje

• Artefakt obliczeniowy to wszystko, co zostało stworzone przez człowieka przy użyciu komputera i może być między innymi programem, obrazem, dźwiękiem, wideo, prezentacją lub stroną internetową.

1.1 Bity i ich przechowywanie

Abstrakcje pozwalają nam reprezentować wiele rodzajów danych, ale we współczesnych komputerach na najniższym poziomie wszystkie informacje są zakodowane jako układy zer i jedynek. Cyfry te nazywane są bitami (ang. bits, skrót od binary digits). Chociaż możemy mieć skłonność do kojarzenia bitów z wartościami liczbowymi, w rzeczywistości są to tylko symbole, których znaczenie zależy od użycia. Postacie bitowe czasami są używane do przedstawiania wartości liczbowych; czasami reprezentują znaki alfabetu i znaki interpunkcyjne, czasami kolor i obrazy, a czasem dźwięki.

Najważniejsze informacje

• Dane cyfrowe są reprezentowane przez abstrakcje na różnych poziomach.

• Na najniższym poziomie wszystkie dane cyfrowe są reprezentowane przez bity.

• Na wyższych poziomach bity są grupowane w celu przedstawiania abstrakcji, w tym m.in. liczb, znaków i kolorów.

• Na jednym z najniższych poziomów abstrakcji dane cyfrowe są przedstawiane binarnie (podstawa 2) przy użyciu wyłącznie kombinacji cyfr zero i jeden.

Operacje logiczne

Aby zrozumieć, w jaki sposób poszczególne bity są przechowywane i przetwarzane wewnątrz komputera, wygodnie jest wyobrazić sobie, że bit 0 reprezentuje wartość fałsz, a bit 1 reprezentuje wartość prawda. Na cześć matematyka George’a Boole’a (1815–1864), który był pionierem w dziedzinie matematyki zwanej logiką, operacje na wartościach prawda/fałsz nazywane są operacjami boolowskimi (logicznymi). Trzy podstawowe operacje logiczne to AND, OR i XOR (alternatywa rozłączna). Pokazano je na rysunku 1.1. (Nazwy operacji logicznych zapisujemy wielkimi literami, aby odróżnić je od odpowiadających im słów w języku angielskim). Te operacje są podobne do operacji arytmetycznych RAZY i PLUS, ponieważ łączą parę wartości (wejście operacji) w celu uzyskania trzeciej wartości (wyjście). Jednak w przeciwieństwie do operacji arytmetycznych operacje logiczne łączą wartości prawda/fałsz, a nie wartości liczbowe.

Operacja logiczna AND służy do przedstawiania prawdziwości lub fałszu zdania utworzonego przez połączenie dwóch mniejszych lub prostszych stwierdzeń spójnikiem i. Takie stwierdzenia mają formę rodzajową

P AND Q

gdzie P reprezentuje jedno stwierdzenie, a Q reprezentuje inne – na przykład:

Kermit jest żabą AND Miss Piggy jest aktorką.

Dane dwuargumentowej operacji AND reprezentują prawdziwość lub fałszywość jej składowych, a wynik reprezentuje prawdziwość lub fałszywość całego złożonego wyrażenia. Ponieważ zdanie w postaci P AND Q jest prawdziwe tylko wtedy, gdy oba jego składniki są prawdziwe, wnioskujemy, że 1 AND 1 powinno wynosić 1, podczas gdy wszystkie inne przypadki powinny dać wynik równy 0, zgodnie z rysunkiem 1.1.

W podobny sposób operacja OR jest dwuargumentowym wyrażeniem w postaci

P OR Q

gdzie P reprezentuje jedno stwierdzenie, a Q inne. Takie stwierdzenia są prawdziwe, gdy przynajmniej jeden ze składników jest prawdziwy, co jest zgodne z operacją OR przedstawioną na rysunku 1.1.

W języku angielskim nie ma jednego spójnika, który przedstawiłby znaczenie operacji XOR. XOR daje wynik 1 (prawda), gdy jedno z jego danych wejściowych ma wartość 1 (prawda), a drugie 0 (fałsz). Na przykład stwierdzenie w formie P XOR Q oznacza „albo P albo Q, ale nie oba naraz”. (W skrócie, operacja XOR daje wynik 1, gdy jej dane wejściowe są różne).

Rysunek 1.1 Możliwe wartości wejściowe i wyniki operacji logicznych AND, OR i XOR (alternatywa rozłączna)

Kolejną operacją logiczną jest operacja NOT. Różni się od AND, OR i XOR, ponieważ ma tylko jedno wejście. Jej wyjście jest przeciwieństwem tego wejścia; jeśli wejście operacji NOT jest prawdą, to wyjście jest fałszem i na odwrót. Tak więc, jeśli wejście operacji NOT byłoby prawdą lub fałszem stwierdzenia,

Fozzie jest niedźwiedziem.

to wtedy wynik reprezentowałby prawdziwość lub fałszywość stwierdzenia

Fozzie nie jest niedźwiedziem.

Bramki i przerzutniki

Układ, który generuje dane wyjściowe operacji logicznej, gdy podane są wartości wejściowe operacji, jest nazywany bramką, a czasem bramką logiczną. Bramki mogą być zbudowane z użyciem różnych technologii, takich jak przekładnie, przekaźniki czy elementy optyczne. Bramki w dzisiejszych komputerach zwykle składają się z małych elektronicznych układów przełączających zwanych tranzystorami. Cyfry 0 i 1 są reprezentowane jako odpowiednie poziomy napięcia. Nie musimy jednak zajmować się takimi szczegółami. Dla naszych potrzeb wystarczy przedstawić bramki w ich symbolicznej formie, tak jak pokazano na rysunku 1.2. Zauważmy, że bramki AND, OR, XOR i NOT są reprezentowane przez symbole o różnych kształtach, z wartościami wejściowymi zaznaczonymi z jednej strony i wyjściem z drugiej.

Najważniejsze informacje

• Bramka logiczna to abstrakcja sprzętowa modelowana przez jedną z funkcji logicznych.

Rysunek 1.2 Graficzna reprezentacja bramek AND, OR, XOR i NOT oraz ich wartości wejściowych i wyjściowych

Bramki stanowią cegiełki, z których są zbudowane komputery. W rezultacie logika i operatory logiczne są podstawowymi operacjami w naszych językach programowania. Jeden ważny krok w tym kierunku został przedstawiony na schemacie na rysunku 1.3. Jest to szczególny przykład komponentu znanego jako przerzutnik (ang. flip-flop). Przerzutnik to podstawowa jednostka pamięci komputera. Jest to układ wytwarzający wartość wyjściową 0 lub 1, która pozostaje stała, dopóki impuls (chwilowa zmiana na 1, po którym następuje powrót do 0) z innego układu, nie spowoduje przejścia na inną wartość. Innymi słowy, wyjście można ustawić tak, aby „pamiętało” zero lub jedynkę w zależności od bodźców zewnętrznych. Dopóki oba wejścia w obwodzie na rysunku 1.3 będą 0, wyjście (niezależnie czy 0, czy 1) nie zmieni się. Tymczasowe umieszczenie 1 na górnym wejściu spowoduje, że wyjście będzie równe 1, podczas gdy tymczasowe umieszczenie 1 na dolnym wejściu spowoduje, że wyjście będzie ponownie równe 0.

Najważniejsze informacje

• Pojęcia logiczne i algebra boolowska są podstawą programowania.

Rysunek 1.3 Prosty układ przerzutnika

Przeanalizujmy to działanie bardziej szczegółowo. Nie znając bieżącego wyjścia układu z rysunku 1.3, załóżmy, że górne wejście zmienia się na 1, podczas gdy dolne wejście pozostaje 0 (rysunek 1.4a). Spowoduje to, że wyjście bramki OR będzie równe 1, niezależnie od drugiego wejścia tej bramki. Oba wejścia bramki AND będą z kolei miały teraz wartość 1, ponieważ drugie wejście do tej bramki ma już wartość 1 (wyjście wytwarzane przez bramkę NOT, gdy dolne wejście przerzutnika ma wartość 0). Wyjście bramki AND będzie wtedy równe 1, co oznacza, że drugie wejście bramki OR będzie teraz miało wartość 1 (rysunek 1.4b). Gwarantuje to, że wyjście bramki OR pozostanie 1, nawet gdy górne wejście przerzutnika zostanie zmienione z powrotem na 0 (rysunek 1.4c). Podsumowując, wyjście przerzutnika będzie wynosić 1 i pozostanie niezmienione po powrocie górnego wejścia na 0.

W podobny sposób chwilowe podanie wartości 1 na dolne wejście spowoduje wymuszenie na wyjściu przerzutnika wartości 0, które będzie trwało po powrocie wartości wejściowej do 0.

Wprowadzenie układu przerzutnika przedstawionego na rysunkach 1.3 i 1.4 ma potrójny cel. Po pierwsze, pokazuje, w jaki sposób można budować urządzenia z bramek, co jest procesem znanym jako projektowanie układów cyfrowych, który jest ważnym tematem w inżynierii komputerowej. W rzeczywistości przerzutnik jest tylko jednym z wielu układów, które są podstawowymi narzędziami w inżynierii komputerowej.

Po drugie, pojęcie przerzutnika dostarcza przykładu abstrakcji i użycia abstrakcyjnych narzędzi. Obecnie istnieją inne sposoby na zbudowanie przerzutnika. Jedną z alternatyw pokazano na rysunku 1.5. Eksperymentując z tym układem, można przekonać się, że chociaż ma on inną strukturę wewnętrzną, jego właściwości zewnętrzne są takie same jak tego na rysunku 1.3. Inżynier komputerowy nie musi wiedzieć, który układ jest faktycznie używany w przerzutniku. Zamiast tego, aby użyć go jako abstrakcyjnego narzędzia, musi tylko zrozumieć zewnętrzne właściwości przerzutnika. Przerzutnik, wraz z innymi tego typu układami, tworzy zestaw elementów składowych, z których inżynier może zbudować bardziej złożone układy. Projektowanie układów komputerowych przybiera strukturę hierarchiczną, w której każdy poziom jako abstrakcyjne narzędzia wykorzystuje komponenty niższego poziomu.

Rysunek 1.4 Ustawienie wyjścia przerzutnika na 1

Rysunek 1.5 Inny sposób zbudowania przerzutnika

Trzecim celem wprowadzenia przerzutnika jest to, że jest to jeden ze sposobów przechowywania bitów we współczesnych komputerach. Dokładniej rzecz biorąc, przerzutnik można ustawić tak, aby na wyjściu miał wartość 0 lub 1. Inne układy mogą zmieniać tę wartość, wysyłając impulsy na wejścia przerzutnika, a jeszcze inne układy mogą reagować na zapamiętaną wartość, korzystając z wyjścia przerzutnika jako swojego wejścia. W ten sposób wiele przerzutników, zbudowanych w postaci bardzo małych obwodów elektrycznych, może zostać użytych wewnątrz komputera jako narzędzie do zapisywania informacji zakodowanych jako kombinacje zer i jedynek. W praktyce technologia znana jako VLSI (bardzo duży stopień scalenia), która umożliwia umieszczanie milionów komponentów elektrycznych na płytce półprzewodnikowej (zwanej układem scalonym lub czipem), jest wykorzystywana do tworzenia miniaturowych układów zawierających miliony przerzutników wraz z ich obwodami sterującymi. W rezultacie czipy te w systemach komputerowych są wykorzystywane jako abstrakcyjne narzędzia do budowy komponentów wyższego poziomu. W niektórych przypadkach VLSI służy do tworzenia całego systemu komputerowego opartego na jednym czipie.

Najważniejsze informacje

• Dane binarne są przetwarzane przez fizyczne warstwy sprzętu komputerowego, w tym bramki, układy scalone i komponenty.

• Sprzęt jest zbudowany przy użyciu wielu poziomów abstrakcji, takich jak tranzystory, bramki logiczne, układy scalone, pamięć, płyty główne, karty specjalnego przeznaczenia i urządzenia pamięci masowej.

Notacja szesnastkowa

Rozważając wewnętrzne działania komputera, będziemy mieli do czynienia z wzorcami bitów, które będziemy nazywać łańcuchami bitów. Niektóre z nich mogą być dość długie. Długi łańcuch bitów jest często nazywany strumieniem. Niestety strumienie są trudne do zrozumienia dla ludzkiego umysłu. Samo zapisanie wzorca 101101010011 jest żmudne i podatne na błędy. Aby uprościć reprezentację takich wzorców bitowych, zwykle używamy notacji skróconej zwanej notacją szesnastkową, która wykorzystuje fakt, że wzorce bitowe w maszynie mają zwykle długość będącą wielokrotnością czterech. W szczególności notacja szesnastkowa wykorzystuje pojedynczy symbol do reprezentowania wzorca czterech bitów. Na przykład łańcuch dwunastu bitów może być reprezentowany przez trzy symbole szesnastkowe. Do wskazania podstawy liczby niedziesiętnej matematycy używają zwykle indeksów dolnych, zatem wartość 15_10 mogą zapisać szesnastkowo jako F_16. Informatycy, przyzwyczajeni do programowania w językach tekstowych, które nie obsługują indeksów dolnych, do wskazania podstawy liczby niedziesiętnej często używają przedrostków. Dlatego, dla jasności, w tej książce przed naszymi liczbami szesnastkowymi będziemy również używać typowego dla tego przypadku prefiksu „0x”.

Najważniejsze informacje

• System szesnastkowy (o podstawie 16) jest wykorzystywany do reprezentowania danych cyfrowych, ponieważ reprezentacja szesnastkowa używa mniej cyfr niż binarna.

Rysunek 1.6 przedstawia system szesnastkowy. Lewa kolumna zawiera wszystkie możliwe wzorce bitowe o długości cztery, a prawa kolumna wskazuje symbol używany do reprezentowania wzorca bitowego w notacji szesnastkowej. Używając tego systemu, postać bitową 10110101 można zapisać jako 0xB5. Uzyskuje się to poprzez podzielenie postaci bitowej na podciągi o długości czterech, a następnie zamianę każdego podciągu na jego szesnastkowy odpowiednik – 1011 jest reprezentowane przez 0xB, a odpowiednikiem 0101 jest 0x5. W ten sposób 16-bitowy wzorzec 1010010011001000 może zostać zredukowany do przyjemniejszej postaci 0xA4C8. W następnym rozdziale będziemy szeroko używać notacji szesnastkowej. Tam docenimy jej skuteczność.

Rysunek 1.6 Szesnastkowy system zapisu

1.1 Pytania i ćwiczenia

1. Jaki wzorzec bitowy na wejściu spowoduje, że poniższy układ wygeneruje wartość 1?

2. W tekście stwierdziliśmy, że podanie 1 na dolne wejście przerzutnika na rysunku 1.3 (przy utrzymaniu 0 na górnym wejściu) spowoduje, że wyjście przerzutnika będzie równe 0. Opisz sekwencję zdarzeń, które w tym przypadku wystąpią w przerzutniku.

3. Zakładając, że na obu wejściach przerzutnika z rysunku 1.5 na początku jest podane 0, opisz sekwencję zdarzeń, która następuje, gdy górne wejście zostanie tymczasowo ustawione na 1.

4. a. Jeśli wyjście bramki AND przechodzi przez bramkę NOT, kombinacja stanowi operację logiczną o nazwie NAND, która na wyjściu daje 0 tylko wtedy, gdy oba wejścia mają wartość 1. Symbol bramki NAND jest taki sam jak bramki AND, z wyjątkiem tego, że przy jej wyjściu jest narysowane małe kółko. Poniżej znajduje się układ zawierający bramkę NAND. Jaką operację logiczną realizuje ten układ?

b. Jeśli wyjście bramki OR przechodzi przez bramkę NOT, kombinacja stanowi operację logiczną zwaną NOR, która na wyjściu daje 1 tylko wtedy, gdy oba jej wejścia mają wartość 0. Symbol bramki NOR jest taki sam jak bramki OR, z wyjątkiem tego, że przy jej wyjściu jest narysowane małe kółko. Poniżej znajduje się obwód zawierający bramkę AND i dwie bramki NOR. Jaką operację logiczną realizuje ten układ?

5. Użyj notacji szesnastkowej, aby przedstawić następujące wzorce bitowe:

a. 0110101011110010 b. 111010000101010100010111

c. 01001000

6. Jakie wzorce bitowe są reprezentowane przez następujące wzorce szesnastkowe?

a. 0x5FD97 b. 0x610A c. 0xABCD d. 0x0100

1.2 Pamięć główna

W celu przechowywania danych komputer zawiera duży zbiór układów (takich jak przerzutniki), z których każdy może przechowywać pojedynczy bit. Ten zbiór bitów jest określany jako pamięć główna urządzenia.

Organizacja pamięci

Pamięć główna komputera jest podzielona na zarządzalne jednostki zwane komórkami. Typowy rozmiar komórki wynosi osiem bitów. (Ciąg ośmiu bitów nazywany jest bajtem. Typowa komórka pamięci ma zatem pojemność jednego bajta.) Małe komputery wbudowane w takie urządzenia domowe jak termostaty i kuchenki mikrofalowe mogą mieć pamięć główną składającą się tylko z kilkuset komórek, podczas gdy komputery stacjonarne i smartfony mogą mieć w pamięci głównej miliardy komórek.

Chociaż w komputerze nie ma lewej ani prawej strony, zwykle wyobrażamy sobie, że bity w komórce pamięci są ułożone w rzędzie. Lewy strona tego rzędu wskazuje starsze bity, a prawa strona – młodsze bity. Najbardziej skrajny bit po lewej stronie jest nazywany najstarszym bitem lub najbardziej znaczącym bitem w związku z tym, że gdyby zawartość komórki była interpretowana jako wartość liczbowa, bit ten byłby najbardziej znaczącą cyfrą w liczbie. Podobnie, najbardziej skrajny bit po prawej jest określany jako najmłodszy bit lub najmniej znaczący bit. W ten sposób zawartość komórki pamięci o rozmiarze bajta możemy przedstawiać tak, jak pokazano na rysunku 1.7.

Rysunek 1.7 Organizacja komórki pamięci o rozmiarze bajta

Aby rozpoznać poszczególne komórki w pamięci głównej komputera, każdej komórce przypisywana jest niepowtarzalna „nazwa”, zwana jej adresem. System jest analogiczny do techniki identyfikacji domów w mieście po adresach. Jednak w przypadku komórek pamięci używane adresy są całkowicie numeryczne. Mówiąc dokładniej, powinniśmy wyobrazić sobie, że wszystkie komórki są umieszczone w jednym rzędzie i ponumerowane w tej kolejności, zaczynając od wartości zero. Taki system adresowania nie tylko daje nam sposób na jednoznaczną identyfikację każdej komórki, ale także kojarzy kolejność z komórkami (rysunek 1.8), dając nam wyrażenia takie jak „następna komórka” lub „poprzednia komórka”.

Ważną konsekwencją przypisywania kolejności zarówno komórkom w pamięci głównej, jak i bitom w każdej komórce, jest to, że cały zbiór bitów w pamięci głównej komputera jest zasadniczo uporządkowany w jednym długim rzędzie. Fragmenty tego długiego rzędu mogą zatem być używane do przechowywania wzorców bitowych, które mogą być dłuższe niż długość pojedynczej komórki. W takiej sytuacji łańcuch 16 bitów możemy zapisać przy użyciu po prostu dwóch kolejnych komórek pamięci.

Rysunek 1.8 Komórki pamięci uporządkowane według adresu

Uzupełnieniem układów, które faktycznie przechowują bity w pamięci głównej komputera, są układy niezbędne do umożliwienia innym układom zapisywanie i pobieranie danych z komórek pamięci. W ten sposób inne układy mogą pobierać dane z pamięci, prosząc elektronicznie o zawartość określonego adresu (co jest nazywane operacją odczytu), lub mogą zapisywać informacje w pamięci, żądając umieszczenia w komórce o konkretnym adresie określonego wzorca bitowego (co jest nazywane operacją zapisu).

Ponieważ pamięć główna komputera jest zorganizowana jako indywidualne, adresowalne komórki, dostęp do nich można uzyskać w razie potrzeby niezależnie. Aby odzwierciedlić możliwość dostępu do komórek w dowolnej kolejności, pamięć główna komputera jest często nazywana pamięcią o dostępie swobodnym (ang. random access memory, RAM). Ta własność swobodnego dostępu do pamięci głównej jest wyraźnie sprzeczna z systemami pamięci masowej (omówionymi w następnym podrozdziale), w których długie ciągi bitów są przetwarzane w postaci połączonych bloków.

Chociaż wprowadziliśmy przerzutniki jako sposób na przechowywanie bitów, pamięć RAM w większości współczesnych komputerów jest konstruowana przy użyciu analogicznych, ale bardziej złożonych technologii, które oferują większą miniaturyzację i krótszy czas reakcji. Wiele z tych technologii przechowuje bity jako maleńkie ładunki elektryczne, które szybko się rozładowują. W związku z tym układy te wymagają dodatkowego elementu, określanego jako układ odświeżający, który wiele razy na sekundę odświeża zawartość komórek. Ze względu na tę niestabilność pamięć komputerowa skonstruowana na bazie takiej technologii jest często nazywana pamięcią dynamiczną, co prowadzi do określenia DRAM oznaczającego „dynamic RAM”. W odniesieniu do pamięci DRAM, która stosuje dodatkowe techniki w celu skrócenia czasu potrzebnego na pobranie zawartości z komórek pamięci jest czasami używany termin SDRAM (wymawiany „es-de-ram”), oznaczający synchroniczną pamięć DRAM (Synchronous DRAM).

Mierzenie pojemności pamięci

Jak dowiemy się w następnym rozdziale, praktycznie jest projektować systemy pamięci głównej, w których łączna liczba komórek jest potęgą dwójki. Wielkość pamięci we wczesnych komputerach była często mierzona w 1024 (czyli 2^10) jednostkach komórek. Ponieważ 1024 jest bliskie wartości 1000, społeczność komputerowa przyjęła przedrostek kilo w odniesieniu do tej jednostki. Oznacza to, że termin kilobajt (w skrócie KB) został użyty w odniesieniu do 1024 bajtów. Tak więc maszyna z 4096 komórkami pamięci będzie posiadać 4 KB pamięci (4096 = 4 X 1024). W miarę powiększania się pamięci terminologia ta rozszerzyła się o MB (megabajt), GB (gigabajt) i TB (terabajt). Niestety stosowanie przedrostków kilo-, mega- itd. stanowi nadużycie terminologii, ponieważ są już one używane w innych dziedzinach w odniesieniu do jednostek będących potęgami tysiąca. Na przykład podczas pomiaru odległości kilometr odnosi się do 1000 metrów, a podczas pomiaru częstotliwości radiowych megaherc odnosi się do 1 000 000 herców. Pod koniec lat 90. międzynarodowe organizacje normalizacyjne opracowały specjalistyczną terminologię dla potęg dwójki: kibi-, mebi-, gibi- i tebi-bajty oznaczające potęgi 1024, a nie potęgi tysiąca. Jednak chociaż to rozróżnienie w wielu częściach świata jest prawem danego kraju, zarówno opinia publiczna, jak i wielu informatyków niechętnie porzuciło bardziej znany, ale niejednoznaczny „megabajt”. Dlatego przy posługiwaniu się tą terminologią konieczne jest słowo przestrogi. Z reguły terminy takie jak kilo-, mega- itp., gdy są używane w kontekście miar komputerowych, odnoszą się do potęg dwójki, natomiast w innych kontekstach odnoszą się do potęg tysiąca.

1.2 Pytania i ćwiczenia

1. Jeżeli komórka pamięci o adresie 5 zawiera wartość 8, to jaka jest różnica między zapisaniem wartości 5 do komórki nr 6 a przeniesieniem zawartości komórki nr 5 do komórki nr 6?

2. Załóżmy, że chcemy zamienić wartości przechowywane w komórkach pamięci 2 i 3. Jaki jest błąd w następującej sekwencji kroków:

Krok 1. Przenosimy zawartość komórki nr 2 do komórki nr 3.

Krok 2. Przenosimy zawartość komórki nr 3 do komórki nr 2.

3. Zaprojektuj sekwencję kroków, która poprawnie zamienia zawartość tych komórek. W razie potrzeby możesz użyć dodatkowych komórek.

4. Ile bitów byłoby w pamięci komputera z pamięcią 4 KB?

1.3 Pamięć masowa

Ze względu na niestabilność i ograniczony rozmiar pamięci głównej komputera większość komputerów ma dodatkowe urządzenia pamięci zwane systemami pamięci masowej (lub pamięci pomocniczej), do których należą dyski magnetyczne, płyty CD, DVD, taśmy magnetyczne, dyski flash i dyski półprzewodnikowe (wszystkie z nich omówimy pokrótce). Przewaga systemów pamięci masowej nad pamięcią główną to mniejsza niestabilność, duże pojemności pamięci, niski koszt, a w wielu przypadkach możliwość wyjęcia nośnika pamięci z maszyny w celu archiwizacji.

Główną wadą magnetycznych i optycznych systemów pamięci masowej jest to, że zazwyczaj korzystają one z elementów ruchomych, a zatem potrzebują znacznie więcej czasu na zapis i pobranie danych niż pamięć główna maszyny, w której wszystkie czynności są wykonywane elektronicznie. Co więcej, systemy przechowywania z ruchomymi częściami są bardziej podatne na awarie mechaniczne niż systemy półprzewodnikowe. Chociaż dyski flash i dyski półprzewodnikowe nie wymagają ruchomych części, inne czynniki elektroniczne mogą ograniczać ich szybkość lub trwałość w porównaniu z pamięcią główną.

Najważniejsze informacje

• Wybór nośników pamięci ma wpływ zarówno na metody, jak i koszty operowania danymi na nich zawartymi.

Systemy magnetyczne

Na arenie pamięci masowych od lat dominuje technologia magnetyczna. Najpopularniejszym obecnie przykładem jest dysk magnetyczny lub dysk twardy (HDD), w którym do przechowywania danych używa się cienkiego, wirującego talerza z powłoką magnetyczną (rysunek 1.9). Nad i/lub pod talerzem są umieszczone głowice odczytu/zapisu, dzięki czemu podczas jego obrotu każda głowica porusza się po okręgu zwanym ścieżką. Poprzez zmianę położenia głowic odczytu/zapisu można uzyskać dostęp do różnych koncentrycznych ścieżek. W wielu przypadkach system przechowywania dysków składa się z kilku talerzy zamontowanych na wspólnym wrzecionie, jeden nad drugim, z wystarczającą ilością miejsca, aby głowice odczytu/zapisu mogły wsunąć się między talerze. W takich przypadkach głowice odczytu/zapisu poruszają się zgodnie. Za każdym razem, gdy przesuwane są głowice odczytu/zapisu, dostępny staje się nowy zbiór ścieżek zwany cylindrem.

Ponieważ ścieżka może zawierać więcej informacji, niż chcielibyśmy przetwarzać za jednym razem, każda ścieżka jest podzielona na małe łuki zwane sektorami, w których informacje są zapisywane jako ciągły łańcuch bitów. Każdy sektor na dysku zawiera tę samą liczbę bitów (typowe pojemności mieszczą się w zakresie od 512 bajtów do kilku KB), a w najprostszych dyskowych systemach pamięci masowej każda ścieżka zawiera taką samą liczbę sektorów. Tak więc bity w obrębie sektora na ścieżce w pobliżu zewnętrznej krawędzi talerza są przechowywane w mniej zwarty sposób niż te na ścieżkach w pobliżu środka, ponieważ zewnętrzne ścieżki są dłuższe niż wewnętrzne. W przeciwieństwie do tego, w dyskowych systemach pamięci masowej o dużej pojemności, ścieżki w pobliżu zewnętrznej krawędzi mogą zawierać znacznie więcej sektorów niż te w pobliżu środka, a możliwość ta jest często wykorzystywana przez zastosowanie techniki zwanej nagrywaniem strefowym. W nagrywaniu strefowym kilka sąsiednich ścieżek jest wspólnie określanych jako strefa, przy czym typowy dysk zawiera około dziesięciu stref. Wszystkie ścieżki w strefie mają taką samą liczbę sektorów. Dana strefa ma więcej sektorów na ścieżkę niż strefa bliżej środka talerza. W ten sposób uzyskuje się efektywne wykorzystanie całej powierzchni dysku. Niezależnie od szczegółów, system pamięci dyskowej składa się z wielu indywidualnych sektorów, z których każdy może być dostępny jako niezależny ciąg bitów.

Pojemność pamięci dyskowej zależy od liczby użytych talerzy i gęstości, z jaką umieszczone są ścieżki i sektory. Systemy o mniejszej pojemności mogą składać się z jednego talerza, zwłaszcza gdy fizyczny rozmiar dysku twardego musi pozostać kompaktowy. Systemy dyskowe o dużej pojemności, które mogą pomieścić wiele terabajtów, składają się z trzech do sześciu talerzy zamontowanych na wspólnym wrzecionie. Ponadto dane mogą być przechowywane zarówno na górnej, jak i dolnej powierzchni każdego talerza.

Rysunek 1.9 System przechowywania danych na dysku

Do oceny wydajności systemu dyskowego wykorzystuje się kilka parametrów: (1) czas odszukiwania (czas wymagany do przeniesienia głowic odczytu/zapisu z jednej ścieżki nad drugą); (2) opóźnienie rotacyjne (połowa czasu potrzebnego na wykonanie pełnego obrotu talerza, czyli średni czas wymagany na obrót żądanych danych wokół głowicy odczytu/zapisu po umieszczeniu głowicy nad żądaną ścieżką); (3) czas dostępu (suma czasu odszukiwania i opóźnienia rotacyjnego) oraz (4) szybkość przesyłania (szybkość, z jaką dane mogą być przesyłane na dysk lub z dysku). (Należy zauważyć, że w przypadku nagrywania strefowego ilość danych przechodzących przez głowicę odczytu/zapisu podczas jednego obrotu talerza jest większa w przypadku ścieżek w strefie zewnętrznej niż w strefie wewnętrznej, a zatem szybkość przesyłania danych różni się w zależności od używanej części dysku). Inne ważne wskaźniki wydajności służące do oceny zarówno pamięci masowej, jak i bardziej ogólnych systemów komunikacyjnych obejmują: (1) przepustowość (całkowita liczba bitów, które można przesłać w jednostce czasu, np. 3 megabity na sekundę) oraz (2) opóźnienie (całkowity czas między żądaniem transferu danych a ich otrzymaniem).

Czynnikiem ograniczającym czas dostępu i szybkość transferu jest szybkość, z jaką obracają się talerze. Aby ułatwić szybkie obroty, głowice odczytu/zapisu nie dotykają dysku, ale „unoszą się” tuż nad jego powierzchnią. Odstęp jest tak niewielki, że nawet pojedyncza cząsteczka kurzu może utknąć między głowicą a powierzchnią dysku, niszcząc obydwa elementy (zjawisko znane jako uszkodzenie dysku twardego). Dlatego systemy dyskowe są zwykle umieszczane w obudowach, które są fabrycznie zaplombowane. Dzięki takiej konstrukcji są one w stanie obracać się z prędkością kilkuset razy na sekundę, osiągając szybkość transferu mierzoną w MB na sekundę.

Ponieważ do swojego działania systemy dyskowe wymagają fizycznego ruchu, prędkości w tych systemach są gorsze w porównaniu do prędkości w układach elektronicznych. Czasy opóźnienia w obwodzie elektronicznym są mierzone w nanosekundach (miliardowe części sekundy) lub mniejszych, podczas gdy czasy odszukiwania, czasy opóźnień i czasy dostępu w systemach dyskowych są mierzone w milisekundach (tysięczne części sekundy). Tak więc czas potrzebny na pobranie informacji z systemu dyskowego może wydawać się wiecznością dla układu elektronicznego.

Technologiami zapisu magnetycznego, które są obecnie mniej powszechnie stosowane, są taśmy magnetyczne, w których informacje są zapisywane na powłoce magnetycznej cienkiej plastikowej taśmy nawiniętej na szpule, oraz napędy dyskietek, w których pojedyncze talerze z powłoką magnetyczną są umieszczone w przenośnej kasetce zaprojektowanej tak, aby można ją było łatwo wyjąć z napędu. Napędy taśm magnetycznych mają wyjątkowo długie czasy wyszukiwania (a więc duże opóźnienia), podobnie jak ich kuzyni, kasety audio i wideo, które mają problemy z powodu długich czasów przewijania do tyłu i do przodu. Niski koszt i duża pojemność danych sprawiają, że taśma magnetyczna nadaje się do zastosowań, w których dane są głównie odczytywane lub zapisywane liniowo, takich jak kopie zapasowe z danymi archiwalnymi. Wymienny charakter talerzy dyskietek wiązał się ze znacznie mniejszą gęstością danych i prędkością dostępu niż w przypadku talerzy dysków twardych, ale we wcześniejszych dekadach ich przenośność była niezwykle cenna, zanim pojawiły się dyski flash o większej pojemności i większej trwałości.

Najważniejsze informacje

• Przepustowość systemu jest miarą przepływności – ilości danych (mierzonej w bitach), które można przesłać w ustalonym czasie.

• Opóźnienie systemu to czas, jaki upłynął między otrzymaniem żądania a przesłaniem danych.

Systemy optyczne

Inna klasa systemów pamięci masowych wykorzystuje technologię optyczną. Przykładem jest płyta kompaktowa (CD). Płyty te mają średnicę 12 centymetrów i składają się z materiału odblaskowego pokrytego przezroczystą powłoką ochronną. Informacje są na nich zapisywane poprzez tworzenie na ich powierzchniach mikrorowków odbijających światło. Informacje te można następnie odczytać za pomocą lasera, który wykrywa nieregularności na powierzchni odbijającej dysku CD podczas jego wirowania.

Technologia CD była pierwotnie stosowana do nagrań audio przy użyciu formatu nagrywania znanego jako CD-DA (Compact Disk Digital Audio), a płyty CD używane obecnie do przechowywania danych komputerowych używają zasadniczo tego samego formatu. Informacje na płytach CD są umieszczane na pojedynczej ścieżce, która ma kształt spirali na płycie jak rowek na staromodnej płycie winylowej, jednak w przeciwieństwie do płyt winylowych, ścieżka na płycie CD biegnie od środka na zewnątrz (rysunek 1.10). Ścieżka ta jest podzielona na jednostki zwane sektorami, z których każdy ma własne oznaczenie identyfikacyjne i pojemność 2 KB, co w przypadku nagrań audio odpowiada 1/75 sekundy muzyki.

Zauważmy, że długość spiralnej ścieżki jest większa bliżej zewnętrznej krawędzi dysku niż w części wewnętrznej. Aby zmaksymalizować pojemność płyty CD, informacje są przechowywane z jednolitą gęstością liniową na całej spiralnej ścieżce, co oznacza, że więcej informacji może zostać zapisanych w pętli na zewnętrznej części spirali niż w pętli w części wewnętrznej. Tym samym więcej sektorów zostanie odczytanych podczas jednego obrotu dysku, gdy laser będzie skanował zewnętrzną część spiralnej ścieżki, niż w sytuacji gdy laser będzie skanował wewnętrzną część ścieżki. Zatem, aby uzyskać jednolitą szybkość przesyłania danych, odtwarzacze CD-DA są zaprojektowane tak, aby zmieniać prędkość obrotową w zależności od lokalizacji lasera. Jednak większość systemów CD wykorzystywanych do przechowywania danych komputerowych obraca się z większą, stałą prędkością i dlatego musi uwzględniać zmiany w szybkości przesyłania danych.

W wyniku takich decyzji projektowych systemy zapisu wykorzystujące płyty CD najlepiej sprawdzają się w przypadku długich, ciągłych łańcuchów danych, na przykład podczas odtwarzania muzyki. Natomiast gdy aplikacja wymaga dostępu do danych w sposób losowy, metoda stosowana na dyskach magnetycznych (pojedyncze, koncentryczne ścieżki podzielone na osobne sektory) przewyższa metodę spiralną stosowaną na płytach CD.

Rysunek 1.10 Format zapisu na płytach CD

Tradycyjne płyty CD mają pojemność w zakresie od 600 do 700 MB. Jednak dyski DVD (Digital Versatile Disk), zbudowane z wielu półprzezroczystych warstw, które podczas odczytu przez precyzyjnie skupiony laser stanowią odrębne powierzchnie, oferują pojemność kilku GB. Takie dyski są w stanie przechowywać długie prezentacje multimedialne, w tym całe filmy. Wreszcie technologia Blu ray, która wykorzystuje laser w niebiesko-fioletowym spektrum światła (zamiast czerwonego), jest w stanie skupić wiązkę lasera z bardzo dużą precyzją. W rezultacie jednowarstwowe dyski BD (dyski Blu ray) oferują ponad pięć razy większą pojemność niż dyski DVD. Nowsze wielowarstwowe formaty BD mogą osiągać pojemności nawet 100 GB. Ta pozornie ogromna ilość pamięci jest potrzebna, aby sprostać wymaganiom wideo w ultrawysokiej rozdzielczości.

Pamięci flash

Powszechną cechą systemów pamięci masowych opartych na technologii magnetycznej lub optycznej jest to, że do zapisu i pobierania danych wymagany jest fizyczny ruch w postaci na przykład obracających się dysków, poruszających się głowic odczytu/zapisu, czy ogniskowania wiązki laserowej. Oznacza to, że zapisywanie i pobieranie danych jest powolne w porównaniu z szybkością układów elektronicznych. Technologia pamięci flash ma potencjał, aby zredukować te wady. W systemie pamięci flash bity są zapisywane poprzez wysyłanie sygnałów elektronicznych bezpośrednio do nośnika pamięci, gdzie powodują uwięzienie elektronów w maleńkich komorach dwutlenku krzemu, zmieniając w ten sposób charakterystykę małych elementów elektronicznych. Ponieważ komory te są w stanie utrzymywać uwięzione elektrony przez wiele lat bez zewnętrznego zasilania, technologia ta doskonale nadaje się do przenośnego, nieulotnego przechowywania danych.

Chociaż dostęp do danych przechowywanych w systemach pamięci flash można uzyskiwać na poziomie małych jednostek wielkości bajtów, tak jak w przypadku pamięci RAM, obecna technologia wymaga, aby zapisywane dane były usuwane w dużych blokach. Co więcej, wielokrotne kasowanie powoli uszkadza komory z dwutlenkiem krzemu, co oznacza, że obecna technologia pamięci flash nie nadaje się do ogólnych zastosowań tak jak w przypadku pamięci głównej, gdzie jej zawartość może być zmieniana wiele razy na sekundę. Jednak w tych zastosowaniach, w których zmiany można kontrolować na rozsądnym poziomie, takich jak aparaty cyfrowe i smartfony, pamięć flash stała się preferowaną technologią pamięci masowej. Ponieważ pamięć flash nie jest wrażliwa na fizyczne wstrząsy (w przeciwieństwie do systemów magnetycznych i optycznych), w praktyce zastępuje inne technologie pamięci masowej w zastosowaniach przenośnych, takich jak laptopy.

Urządzenia z pamięcią flash zwane dyskami flash, o pojemności setek GB, są dostępne w większości zastosowań związanych z pamięcią masową. Napędy te są pakowane w małe plastikowe obudowy ze zdejmowaną nasadką na jednym końcu, chroniącą złącze napędu, gdy jest on odłączony. Duża pojemność tych przenośnych urządzeń, a także fakt, że można je łatwo podłączyć i odłączyć od komputera, czyni je idealnymi do przenośnego gromadzenia danych. Jednak wspomniana ułomność ich maleńkich komór pamięci związana krótszym czasem przechowywania danych wskazuje, że w naprawdę długotrwałych zastosowaniach nie są one tak niezawodne jak dyski optyczne.

Większe urządzenia z pamięcią flash zwane dyskami SSD (solid-state drives), czyli napędy półprzewodnikowe są specjalnie projektowane tak, aby zastąpić magnetyczne dyski twarde. Dyski SSD są lepsze w porównaniu z dyskami twardymi pod względem odporności na wibracje i fizyczne wstrząsy, cichszej pracy (ze względu na brak ruchomych części) i krótszych czasów dostępu. Dyski SSD pozostają droższe niż dyski twarde o porównywalnej wielkości, a zatem podczas zakupu komputera stacjonarnego nadal są traktowane jako rozwiązanie wyższej klasy. W przypadku zastosowań mobilnych, takich jak laptopy i smartfony, dyski SSD mają wyraźną przewagę. Sektory SSD mają bardziej ograniczoną trwałość, co jest cechą wszystkich technologii pamięci flash, natomiast zastosowanie technik równoważenia zużycia poprzez przenoszenie często zmienianych bloków danych do nowych lokalizacji na dysku może zmniejszyć tę niekorzystną właściwość.

Kolejne zastosowanie technologii flash znajduje się w kartach pamięci SD (Secure Digital) (lub po prostu kartach SD). Oferują one do dwóch GB miejsca i są pakowane w postaci plastikowego wafelka wielkości znaczka pocztowego. (Karty SD są również dostępne w mniejszych rozmiarach mini i mikro). Karty pamięci SDHC (High Capacity) oferują do 32 GB miejsca, zaś pojemność kart pamięci nowej generacji SDXC (Extended Capacity) może przekraczać TB. Biorąc pod uwagę ich kompaktowy rozmiar, karty te dobrze pasują do gniazd w małych urządzeniach elektronicznych. Dzięki temu idealnie nadają się do aparatów cyfrowych, odtwarzaczy muzycznych, systemów nawigacji samochodowej i wielu innych urządzeń elektronicznych.

1.3 Pytania i ćwiczenia

1. Co można zyskać, zwiększając prędkość obrotową dysku lub płyty CD?

2. Czy podczas zapisu danych na dysku składającym się z wielu talerzy najpierw powinniśmy wypełnić całą powierzchnię talerza przed rozpoczęciem zapisu na innym, czy też najpierw powinniśmy zapełnić cały cylinder przed rozpoczęciem zapisu na innym talerzu?

3. Dlaczego dane w stale aktualizowanym systemie rezerwacji powinny być zapisywane na dysku magnetycznym zamiast na płycie CD lub DVD?

4. Jakie czynniki pozwalają na odczytywanie wszystkich rodzajów dysków CD, DVD i Blu-ray przez ten sam napęd?

5. Jaką przewagę mają dyski flash nad innymi systemami pamięci masowej przedstawionymi w tym podrozdziale?

6. Jakie zalety magnetycznych dysków twardych sprawiają, że są one nadal są konkurencyjne?

1.4 Przedstawianie informacji w postaci bitów

Po przeanalizowaniu technik przechowywania bitów zajmiemy się teraz tym, w jaki sposób można zapisywać informacje w postaci wzorców bitów. Nasza analiza będzie koncentrować się na popularnych metodach kodowania tekstu, danych liczbowych, obrazów i dźwięku. Każdy z tych systemów ma konsekwencje, które są często widoczne dla typowego użytkownika komputera. Naszym celem jest przedstawienie tych technik na tyle, aby można było dostrzec ich konsekwencje.

Przedstawianie tekstu

Informacja w postaci tekstu jest zwykle przedstawiana za pomocą kodów, w których każdemu z różnych symboli w tekście (takim jak litery alfabetu i znaki interpunkcyjne) przypisywany jest niepowtarzalny wzorzec bitowy. Tekst jest wówczas przedstawiany jako długi łańcuch bitów, w którym kolejne wzorce reprezentują kolejne symbole w oryginalnym tekście.

W latach czterdziestych i pięćdziesiątych zaprojektowano wiele takich kodów i stosowano je w połączeniu z różnym dodatkowym wyposażeniem, co spowodowało proliferację problemów komunikacyjnych. Aby złagodzić ten problem, American National Standards Institute (ANSI) przyjął American Standard Code for Information Interchange (ASCII, wymawiane „aski”). Ten kod wykorzystuje wzorce bitowe o długości siedem do reprezentowania wielkich i małych liter alfabetu angielskiego, symboli interpunkcyjnych, cyfr od 0 do 9 oraz pewnych informacji kontrolnych, takich jak znaki nowego wiersza, powrót karetki i tabulatory. ASCII jest rozszerzany do formatu ośmiu bitów na symbol przez dodanie 0 na najbardziej znaczącym końcu każdego z siedmiobitowych wzorców. Ta technika nie tylko tworzy kod, w którym każdy wzorzec pasuje do typowej komórki pamięci o rozmiarze bajta, ale także dostarcza 128 dodatkowych wzorców bitowych (uzyskanych przez przypisanie dodatkowemu bitowi wartości 1), które mogą być użyte do reprezentowania symboli spoza alfabetu języka angielskiego oraz związanej z nim interpunkcji.

Fragment kodu ASCII w formacie osiem bitów na symbol jest przedstawiony w dodatku A. Korzystając z tego dodatku, możemy zdekodować postać bitową

01001000  01100101  01101100  01101100  01101111  00101110

jako wiadomość „Hello”, co pokazano na rysunku 1.11.

Rysunek 1.11 Komunikat „Hello” w kodowaniu ASCII lub UTF-8

Międzynarodowa Organizacja Normalizacyjna (International Organization for Standardization, znana również jako ISO, w odniesieniu do greckiego słowa isos, oznaczającego równy) opracowała szereg rozszerzeń ASCII, z których każde zostało zaprojektowane tak, aby objąć pewną grupę językową. Na przykład jeden ze standardów zawiera symbole potrzebne do zapisywania tekstów w większości języków zachodnioeuropejskich. Znajdujące się w nim 128 dodatkowe wzorce zawierają symbole funta brytyjskiego i niemieckie samogłoski ä, ö i ü.

Rozszerzone przez ISO standardy ASCII przyczyniły się do ogromnego postępu w kierunku obsługi całej światowej komunikacji wielojęzykowej. Pojawiły się jednak dwie główne przeszkody. Po pierwsze, liczba dodatkowych wzorców bitowych dostępnych w rozszerzonym ASCII jest po prostu niewystarczająca, aby pomieścić alfabet wielu języków azjatyckich i niektórych języków wschodnioeuropejskich. Po drugie, ponieważ dany dokument był ograniczony do używania symboli tylko w jednym wybranym standardzie, nie można było obsługiwać dokumentów zawierających tekst w językach z różnych grup językowych. Obydwie okazały się istotnym utrudnieniem dla międzynarodowego użycia. Aby rozwiązać ten problem, dzięki współpracy kilku wiodących producentów sprzętu i oprogramowania został opracowany Unicode, który szybko zyskał poparcie społeczności komputerowej. Ten kod do reprezentowania dowolnego symbolu wykorzystuje niepowtarzalny wzorzec, który może składać się aż z 21 bitów. Gdy zestaw znaków Unicode zostanie połączony z 8-bitowym standardem kodowania Unicode Transformation Format (UTF-8), oryginalne znaki ASCII będą mogły być nadal reprezentowane za pomocą 8 bitów, natomiast tysiące dodatkowych znaków z takich języków, jak chiński, japoński i hebrajski będą mogły być reprezentowane przez 16 bitów. Oprócz znaków występujących we wszystkich powszechnie używanych językach na świecie, UTF-8 wykorzystuje 24- lub 32-bitowe wzorce do reprezentowania bardziej nietypowych symboli Unicode, pozostawiając wystarczająco dużo miejsca na przyszłą rozbudowę.

Plik składający się z długiej sekwencji symboli zakodowanych za pomocą ASCII lub Unicode jest często nazywany plikiem tekstowym. Ważne jest, aby odróżnić proste pliki tekstowe, które są obsługiwane przez programy narzędziowe zwane edytorami tekstu (lub często po prostu edytorami), od bardziej skomplikowanych plików tworzonych przez procesory tekstu takie jak Microsoft Word. Obydwa zawierają materiał tekstowy. Jednak plik tekstowy zawiera sam tekst zakodowany znak po znaku tekst, podczas gdy plik utworzony przez procesor tekstu zawiera dodatkowe struktury reprezentujące zmiany czcionek, informacje o wyrównaniu itp.

Przedstawianie wartości liczbowych

Przechowywanie informacji w postaci zakodowanych znaków jest nieefektywne, gdy zapisywane informacje są czysto numeryczne. Aby zobaczyć dlaczego, rozważmy problem przechowywania wartości 25. Jeśli będziemy chcieli zapisać ją jako zakodowane symbole w ASCII przy użyciu jednego bajta na symbol, potrzebujemy w sumie 16 bitów. Co więcej, największa liczba, jaką możemy zapisać przy użyciu 16 bitów, to 99. Jednak, jak wkrótce zobaczymy, używając notacji binarnej, w tych 16 bitach możemy przechować dowolną liczbę całkowitą z zakresu od 0 do 65535. Tak więc notacja binarna (lub jej odmiany) jest szeroko stosowana do kodowania danych numerycznych przechowywanych w komputerze.

Notacja binarna to sposób przedstawiania wartości liczbowych za pomocą tylko cyfr 0 i 1, a nie cyfr 0, 1, 2, 3, 4, 5, 6, 7, 8 i 9, jak w tradycyjnym systemie decymalnym, czyli dziesiętnym. System binarny dokładniej przestudiujemy w podrozdziale 1.5. Na razie potrzebujemy tylko jego elementarnego zrozumienia. W tym celu rozważmy działanie staromodnego drogomierza w samochodzie, którego pozycje wyświetlacza zawierają tylko cyfry 0 i 1, a nie zaś tradycyjnie cyfry od 0 do 9. Drogomierz rozpoczyna wyświetlanie od samych zer, a gdy samochód przejedzie kilka pierwszych mil, skrajny prawy element obróci się z 0 na 1. Następnie, gdy nastąpi zmiana z 1 z powrotem do 0, to spowoduje to, że cyfra 1 pojawi się po jego lewej stronie, tworząc wzór 10. Zmiana 0 na 1 w prawym elemencie spowoduje powstanie 11. Gdy skrajny prawy element obróci się z 1 z powrotem do 0, spowoduje to obrócenie elementu po jego lewej stronie z 1 na 0. To z kolei spowoduje, że w trzeciej kolumnie pojawi się kolejna 1, tworząc wzór 100. Krótko mówiąc, podczas jazdy samochodem zobaczymy następującą sekwencję odczytów drogomierza:

0000

0001

0010

0011

0100

0101

0110

0111

1000

American National Standards Institute

American National Standards Institute (ANSI) został założony w 1918 roku przez niewielkie konsorcjum stowarzyszeń inżynierów i agencji rządowych jako federacja non-profit w celu koordynacji opracowywania dobrowolnych standardów dla sektora prywatnego. Obecnie ANSI obejmuje ponad 1,3 tys. firm, organizacji zawodowych, stowarzyszeń handlowych i agencji rządowych. ANSI ma siedzibę w Nowym Jorku i reprezentuje Stany Zjednoczone jako organ członkowski w ISO. Witryna internetowa American National Standards Institute znajduje się pod adresem http://www.ansi.org.

Podobnymi organizacjami w innych krajach są: Standards Australia (Australia), Standards Council of Canada (Kanada), China State Bureau of Quality and Technical Supervision (Chiny), Deutsches Institut für Normung (Niemcy), Japanese Industrial Standards Committee (Japonia), Dirección General de Normas (Meksyk), State Committee of the Russian Federation for Standardization and Metrology (Rosja), Swiss Association for Standardization (Szwajcaria) oraz British Standards Institution (Wielka Brytania).

Ta sekwencja stanowi binarną reprezentację liczb całkowitych od zera do ósemki. Chociaż byłoby to żmudne, moglibyśmy rozszerzyć tę technikę liczenia, aby odkryć, że postać bitowa składająca się z szesnastu jedynek reprezentuje wartość 65535, co potwierdza nasze twierdzenie, że przy użyciu 16 bitów można zakodować każdą liczbę całkowitą z zakresu od 0 do 65535.

Ze względu na tę wydajność powszechne jest przechowywanie informacji liczbowych w formie notacji binarnej, a nie w postaci zakodowanych symboli. Mówimy „forma notacji binarnej”, ponieważ właśnie opisany prosty system binarny jest tylko podstawą kilku technik zapisu numerycznego używanych w maszynach. Niektóre z tych odmian systemu binarnego zostaną omówione w dalszej części tego rozdziału. Na razie powiemy tylko, że system zwany notacją uzupełnień do dwóch (patrz podrozdział 1.6) jest powszechnie stosowany do przechowywania liczb całkowitych, ponieważ zapewnia wygodną metodę przedstawiania liczb ujemnych i dodatnich. Do przedstawiania liczb z częściami ułamkowymi, takimi jak 4½ czy ¾, używana jest inna technika, zwana notacją zmiennoprzecinkową (patrz podrozdział 1.7).

Wreszcie, niezależnie od tego, czy zapiszemy liczbę za pomocą notacji binarnej (podstawa 2), bardziej znanej notacji dziesiętnej (podstawa 10), czy skróconej notacji szesnastkowej (podstawa 16), wyjściowa wartość liczbowa będzie taka sama. Oznacza to, że dwa plus dwa równa się cztery i jest prawda niezależnie od tego, czy zapiszemy to w notacji binarnej (010 + 010 = 100), dziesiętnej (2 + 2 = 4), szesnastkowej (0 × 2 + 0 × 2 = 0 × 4), czy z jakąkolwiek inną podstawą liczbową. Dla komputerów to tylko binarne jedynki i zera.

Najważniejsze informacje

• Systemy liczbowe, w tym binarne, dziesiętne i szesnastkowe, są używane do reprezentowania i przetwarzania danych cyfrowych.

• Liczby można konwertować z dowolnego systemu do dowolnego innego systemu.

Przedstawianie obrazów

Jednym ze sposobów przedstawienia obrazu jest interpretacja obrazu jako zbioru punktów, z których każdy nazywany jest pikselem (pixel), czyli skrótem od „picture element” (element obrazu). Wygląd każdego piksela jest zapisywany, a cały obraz jest zbiorem takich zakodowanych pikseli. Taki zbiór nazywany jest mapą bitową. To podejście jest popularne, ponieważ wiele urządzeń wyświetlających, takich jak drukarki i wyświetlacze, działa na koncepcji pikseli. Dzięki temu obrazy w postaci mapy bitowej można łatwo formatować w celu ich wyświetlenia.

Metoda kodowania pikseli w mapie bitowej różni się w zależności od zastosowania. W przypadku prostego czarno-białego obrazu każdy piksel może być reprezentowany przez pojedynczy bit, którego wartość zależy od tego, czy odpowiadający mu piksel jest czarny czy biały. Jest to podejście stosowane w większości faksów. W przypadku bardziej skomplikowanych zdjęć czarno-białych każdy piksel można przedstawić za pomocą zbioru bitów (zwykle ośmiu), co pozwala na przedstawienie różnych odcieni szarości. W przypadku obrazów kolorowych każdy piksel jest zapisywany za pomocą bardziej złożonego systemu. Powszechne są dwa podejścia. W pierwszym, który nazwiemy kodowaniem RGB, każdy piksel jest przedstawiany za pomocą trzech składowych koloru – czerwonej, zielonej oraz niebieskiej – odpowiadających trzem podstawowym kolorom światła. Zwykle do reprezentowania intensywności każdego składnika koloru jest używany jeden bajt. To powoduje, że do przedstawienia pojedynczego piksela w oryginalnym obrazie są wymagane trzy bajty pamięci.

Alternatywą dla prostego kodowania RGB jest użycie składowej „jasność” oraz dwóch składowych koloru. W tym przypadku składowa „jasność”, nazywana luminancją piksela, jest zasadniczo sumą składowych: czerwonej, zielonej i niebieskiej. (W rzeczywistości uważa się, że jest to ilość białego światła w pikselu, natomiast te szczegóły nie muszą nas tutaj interesować). Pozostałe dwie składowe, zwane chrominancją niebieską i chrominancją czerwoną, są określane przez obliczenie różnicy między luminancją piksela i ilością odpowiednio niebieskiego lub czerwonego światła w pikselu. Łącznie te trzy składowe zawierają informacje wymagane do odtworzenia piksela.

Popularność kodowania obrazów przy użyciu składowych luminancji i chrominancji wywodzi się ze sposobu nadawania telewizji kolorowej, gdyż takie podejście zapewniło sposób kodowania obrazów kolorowych, który był również kompatybilny ze starszymi czarno-białymi odbiornikami telewizyjnymi. W rzeczywistości wersja obrazu w skali szarości może zostać utworzona przy użyciu tylko składowej luminancji zakodowanego kolorowego obrazu.

Wadą przedstawiania obrazów jako map bitowych jest to, że obrazu nie można łatwo przeskalować do dowolnego rozmiaru. Zasadniczo jedynym sposobem na powiększenie obrazu jest powiększanie pikseli, co prowadzi do ziarnistego wyglądu. (Jest to technika stosowana w aparatach cyfrowych zwana „zoomem cyfrowym” w przeciwieństwie do „zoomu optycznego”, który uzyskuje się poprzez regulację obiektywu aparatu).

ISO – Międzynarodowa Organizacja Normalizacyjna

Międzynarodowa Organizacja Normalizacyjna (International Organization for Standardization, powszechnie nazywana ISO) powstała w 1947 roku jako światowa federacja organów normalizacyjnych, po jednym z każdego kraju. Obecnie ma swoją siedzibę w Genewie w Szwajcarii i składa się z ponad 100 członków rzeczywistych oraz licznych członków korespondentów. (Członkiem korespondentem jest zwykle organ normalizacyjny z kraju, w którym nie ma jednostki normalizacyjnej uznanej na poziomie krajowym. Tacy członkowie nie mogą bezpośrednio uczestniczyć w opracowywaniu norm, ale są informowani o działaniach ISO). ISO prowadzi witrynę internetową pod adresem http://www.iso.org.

Alternatywnym sposobem reprezentowania obrazów, który pozwala uniknąć problemu związanego ze skalowaniem, jest opisanie obrazu za pomocą zbioru figur geometrycznych, takich jak linie i krzywe, które można zapisać za pomocą technik geometrii analitycznej. Taki opis pozwala urządzeniu, które docelowo wyświetla obraz, decydować o sposobie wyświetlania figur geometrycznych, zamiast wymagać, aby urządzenie odtwarzało określony wzór pikseli. Jest to podejście stosowane do tworzenia skalowalnych czcionek, które są dostępne w dzisiejszych systemach przetwarzania tekstu. Na przykład TrueType (opracowany przez Microsoft i Apple) to system do geometrycznego opisu symboli tekstowych. Analogicznie PostScript (opracowany przez firmę Adobe Systems) umożliwia opisywanie znaków, a także bardziej ogólnych danych graficznych. Ten geometryczny sposób przedstawiania obrazów jest również popularny w systemach komputerowego wspomagania projektowania (CAD), w których wyświetlane i przetwarzane na ekranach komputerów są rysunki trójwymiarowych obiektów.

Różnica między przedstawianiem obrazu w postaci figur geometrycznych w przeciwieństwie do mapy bitowej jest oczywista dla użytkowników wielu programów do rysowania (takich jak narzędzie Microsoft Paint), które pozwalają użytkownikowi tworzyć obrazy składające się z wcześniej zdefiniowanych kształtów, takich jak prostokąty, owale i podstawowe krzywe. Użytkownik po prostu wybiera żądany kształt geometryczny z menu, a następnie kieruje rysowaniem tego kształtu za pomocą myszy. Podczas procesu rysowania oprogramowanie zachowuje geometryczny opis rysowanego kształtu. W miarę wskazywania kierunków przez mysz, wewnętrzna reprezentacja geometryczna jest modyfikowana, przekształcana do postaci mapy bitowej i wyświetlana. Pozwala to na łatwe skalowanie i modelowanie obrazu. Jednak po zakończeniu procesu rysowania wyjściowy opis geometryczny jest porzucany i zachowywana jest tylko mapa bitowa, co oznacza, że dodatkowe zmiany będą wymagać żmudnego procesu modyfikacji piksel po pikselu. Z drugiej strony, niektóre programy do rysowania zachowują elementy w postaci kształtów geometrycznych, które można później zmodyfikować. Dzięki takim narzędziom można łatwo zmieniać rozmiar kształtów, zachowując wyraźny obraz w dowolnym wymiarze.

Przedstawianie dźwięków

Najbardziej ogólną metodą kodowania informacji dźwiękowych do ich przechowywania i przetwarzania w komputerze jest próbkowanie amplitudy fali dźwiękowej w regularnych odstępach czasu i rejestrowanie ciągu uzyskanych wartości. Na przykład ciąg 0; 1,5; 2,0; 1,5; 2,0; 3,0; 4,0; 3,0; 0 reprezentowałaby falę dźwiękową, której amplituda rośnie, na krótko spada, potem wznosi się na wyższy poziom, a następnie znów spada do 0 (rysunek 1.12). Technika ta, wykorzystująca częstotliwość próbkowania 8 tys. próbek na sekundę, była stosowana od lat w telefonicznej komunikacji głosowej na duże odległości. Głos na jednym końcu kanału komunikacyjnego jest kodowany jako wartości liczbowe reprezentujące amplitudę głosu co osiem tysięcznych sekundy. Te wartości liczbowe są następnie przesyłane linią komunikacyjną do odbiorcy, gdzie są wykorzystywane do odtwarzania dźwięku głosu.

Chociaż 8 tys. próbek na sekundę może wydawać się szybkim tempem, nie jest to wystarczające do nagrań muzycznych o wysokiej jakości. Aby uzyskać jakość odtwarzania dźwięku uzyskiwaną z płyt CD, stosuje się częstotliwość 44 100 próbek na sekundę. Dane uzyskiwane z każdej próbki są przedstawiane za pomocą 16 bitów (32 bitów w przypadku nagrań stereo). W rezultacie każda sekunda muzyki nagranej w stereo wymaga ponad miliona bitów.

Rysunek 1.12. Fala dźwiękowa reprezentowana przez ciąg 0; 1,5; 2,0; 1,5; 2,0; 3,0; 4,0; 3,0; 0

Alternatywny system kodowania, znany jako Musical Instrument Digital Interface (MIDI), jest szeroko stosowany w syntezatorach muzycznych znajdujących się w elektronicznych instrumentach klawiszowych, w dźwięku w grach wideo oraz w efektach dźwiękowych towarzyszących stronom internetowym. Dzięki zapisaniu sposobu wytwarzania muzyki na syntezatorze zamiast kodowania samego dźwięku MIDI pozwala uniknąć wysokich wymagań dotyczących pamięci, jakie stawia technika próbkowania. Ściślej rzecz biorąc, MIDI zapisuje to, który instrument ma zagrać określoną nutę i przez jaki czas, co oznacza, że klarnet grający nutę D przez dwie sekundy może być zakodowany w trzech bajtach, a nie w ponad dwóch milionach bitów, gdy jest próbkowany z częstotliwością 44 100 próbek na sekundę.

Krótko mówiąc, MIDI może być traktowane jako sposób kodowania zapisów nutowych czytanych przez wykonawcę, a nie zaś jako same wykonanie muzyki. W rezultacie „nagranie” MIDI może brzmieć zupełnie inaczej, gdy jest wykonywane na różnych syntezatorach.

1.4 Pytania i ćwiczenia

1. Oto wiadomość zakodowana w ASCII przy użyciu 8 bitów na symbol. Co ona zawiera? (Patrz dodatek A).

01000011  01101111  01101101  01110000  01110101  01110100

01100101  01110010  00100000  01010011  01100011  01101001

01100101  01101110  01100011  01100101

2. Jaka jest zależność w ASCII między kodem wielkiej litery a kodem tej samej, ale małej litery? (Patrz Dodatek A).

3. Zapisz poniższe zdania w ASCII:

a. “Stop!” Cheryl shouted.

b. Does 2 + 3 = 5?

4. Opisz urządzenie z życia codziennego, które może znajdować się w jednym z dwóch stanów, na przykład flaga na maszcie znajdująca się na górze albo na dole. Przypisz do jednego ze stanów symbol 1, a do drugiego 0, i pokaż, jak by wyglądała reprezentacja ASCII dla litery b, zapisana za pomocą takich bitów.

5. Przekształć każdą z następujących reprezentacji binarnych na równoważną postać dziesiętną:

a. 0101    b. 1001    c. 1011

d. 0110    e. 10000    f. 10010

6. Przekształć każdą z następujących reprezentacji dziesiętnych na równoważną postać binarną:

a. 6    b. 13    c. 11

d. 18    e. 27    f. 4

7. Jaka jest największa wartość liczbowa, którą można przedstawić za pomocą trzech bajtów, gdyby każda cyfra została zakodowana przy użyciu jednobajtowego symbolu ASCII? A co by było, gdyby użyto notacji binarnej?

8. Alternatywą dla notacji szesnastkowej do reprezentowania postaci bitowych jest notacja kropkowo-dziesiętna, w której każdy bajt we wzorcu jest reprezentowany przez swój odpowiednik dziesiętny, a te reprezentacje bajtów są oddzielone kropkami. Na przykład 0000110000000101 reprezentuje 12.5 (bajt 00001100 odpowiada wartości 12, a 00000101 odpowiada wartości 5), zaś postać 100010000001000000000111 reprezentuje 136.16.7. Przedstaw każdą z następujących postaci bitowych w notacji kropkowo-dziesiętnej.

a. 0000111100001111    b. 001100110000000010000000

c. 0000101010100000

9. Jaka jest zaleta przedstawiania obrazów za pomocą struktur geometrycznych w porównaniu do map bitowych? Jaka jest zaleta map bitowych w porównaniu do struktur geometrycznych?

10. Załóżmy, że nagranie stereofoniczne jednej godziny muzyki jest zakodowane przy użyciu częstotliwości 44 100 próbek na sekundę, jak omówiono wcześniej w tekście. Jaki będzie rozmiar zakodowanej wersji w porównaniu z pojemnością dysku CD?

1.5. System binarny

W podrozdziale 1.4 widzieliśmy, że notacja binarna jest sposobem przedstawiania wartości liczbowych za pomocą tylko cyfr 0 i 1, a nie dziesięciu cyfr od 0 do 9, które są używane w bardziej powszechnym systemie notacji o podstawie dziesięć. Nadszedł czas, aby dokładniej przyjrzeć się notacji binarnej.

Notacja binarna

Przypomnij sobie, że w systemie dziesiętnym każda pozycja w liczbie jest powiązana z rzędem wielkości. W reprezentacji liczby 375 cyfra 5 znajduje się na pozycji związanej z jednościami, 7 jest na pozycji związanej z dziesiątkami, a 3 jest na pozycji związanej z setkami (rysunek 1.13a). Dana jednostka jest dziesięciokrotnie większa od jednostki po jej prawej stronie. Wartość reprezentowaną przez całe wyrażenie uzyskuje się przez pomnożenie wartości każdej cyfry przez wartość związaną z pozycją tej cyfry, a następnie dodanie tych produktów. Na przykład zapis 375 reprezentuje (3 × sto) + (7 × dziesięć) + (5 × jeden), co w bardziej technicznym zapisie to (3 × 10^2) + (7 × 10^1) + (5 × 10^0).

Pozycja każdej cyfry w zapisie binarnym jest również powiązana z wartością, z tym że wartość przypisana do danej pozycji jest dwa razy większa od wartości przypisanej do pozycji po jej prawej stronie. Mówiąc dokładniej, skrajna prawa cyfra w reprezentacji binarnej jest związana z jedynką (2^0), następnej pozycji po lewej jest przypisana dwójka (2^1), kolejnej czwórka (2^2), następnej ósemka (2^3) i tak dalej. Na przykład w reprezentacji binarnej 1011 pierwsza 1 z prawej znajduje się na pozycji związanej z wartością 1, 1 obok niej jest na pozycji związanej z liczbą dwa, 0 jest na pozycji związanej z czwórką, a 1 najbardziej na lewo na pozycji związanej z ósemką (rysunek 1.13b).

Rysunek 1.13. Systemy o podstawie 10 oraz 2

Aby uzyskać wartość w postaci binarnej, postępujemy zgodnie z tą samą procedurą, co w przypadku podstawy dziesięć – mnożymy wartość każdej cyfry przez wartość związaną z jej pozycją i dodajemy wyniki. Na przykład wartość reprezentowana przez 100101 to 37, jak pokazano na rysunku 1.14. Zauważmy, że ponieważ zapis binarny wykorzystuje tylko cyfry 0 i 1, to proces mnożenia i dodawania ogranicza się do dodawania wartości związanych z pozycjami zajętymi przez jedynki. Zatem postać binarna 1011 reprezentuje wartość jedenaście, ponieważ jedynki znajdują się na pozycjach związanych z wartościami jeden, dwa i osiem.

Rysunek 1.14 Dekodowanie reprezentacji binarnej 100101

W podrozdziale 1.4 nauczyliśmy się liczyć w notacji binarnej, co pozwoliło nam zapisać w niej małe liczby całkowite. Do znajdowania binarnych reprezentacji większych wartości możemy preferować podejście opisane przez algorytm na rysunku 1.15. Zastosujmy ten algorytm do wartości trzynaście (rysunek 1.16). Najpierw dzielimy trzynaście przez dwa, otrzymując iloraz sześć i resztę jeden. Ponieważ iloraz nie był zerowy, krok 2 każe nam podzielić iloraz (sześć) przez dwa, uzyskując nowy iloraz trzy i resztę zero. Najnowszy iloraz nadal nie wynosi zero, zatem dzielimy go przez dwa, uzyskując iloraz jeden i resztę jeden. Ponownie dzielimy najnowszy iloraz (jeden) przez dwa, tym razem otrzymując iloraz zero i resztę jeden. Ponieważ uzyskaliśmy teraz iloraz zerowy, przechodzimy do kroku 3, gdzie dowiadujemy się, że binarna reprezentacja pierwotnej wartości (trzynaście) to 1101, otrzymana na podstawie wartości reszty.

Krok 1.    Podziel wartość przez dwa i zapisz otrzymaną resztę.

Krok 2.    Dopóki uzyskany iloraz nie jest zerem, dziel najnowszy iloraz przez dwa i zapisuj otrzymaną resztę.

Krok 3.    Gdy uzyskany iloraz wynosi zero, liczba binarna reprezentująca pierwotną wartość składa się z reszt ustawionych od prawej do lewej w kolejności, w jakiej zostały obliczone.

Rysunek 1.15 Algorytm znajdowania binarnej reprezentacji dodatniej liczby całkowitej

Rysunek 1.16 Zastosowanie algorytmu z rysunku 1.15 do uzyskania binarnej reprezentacji trzynastki

Dodawanie binarne

Aby zrozumieć proces dodawania dwóch liczb całkowitych, które są przedstawione w systemie binarnym, przypomnijmy najpierw proces dodawania wartości w tradycyjnym zapisie dziesiętnym. Rozważmy następujący przykład:

58

+ 27

Zaczynamy od dodania 8 i 7 w skrajnej prawej kolumnie, aby otrzymać sumę 15. Zapisujemy 5 na dole tej kolumny i przenosimy 1 do następnej kolumny, uzyskując

1

58

+ 27

5

Teraz w następnej kolumnie dodajemy 5 oraz 2 wraz z 1, która została przeniesiona, i otrzymujemy sumę 8, którą zapisujemy na dole kolumny. Wynik jest następujący:

58

+ 27

85

Krótko mówiąc, proces postępuje od prawej do lewej. Dodajemy w nim cyfry w każdej kolumnie, wpisujemy najmniej znaczącą cyfrę tej sumy pod kolumną i przenosimy bardziej znaczącą cyfrę sumy (jeśli istnieje) do następnej kolumny.

Aby dodać dwie liczby całkowite przedstawione w notacji binarnej, postępujemy zgodnie z tą samą procedurą, z tym że wszystkie sumy są obliczane przy użyciu reguł dodawania pokazanych na rysunku 1.17, a nie tradycyjnych reguł dziesiętnych, których nauczyliśmy się w szkole podstawowej. Na przykład, aby obliczyć

111010

+ 11011

zaczynamy od dodania 0 i 1 w skrajnej prawej kolumnie. Otrzymujemy 1, którą wpisujemy poniżej kolumny. Teraz dodajemy 1 i 1 z następnej kolumny, uzyskując 10.

Rysunek 1.17. Reguły dotyczące dodawania binarnego

Cyfrę 0 z 10 zapisujemy pod kolumną, 1 przenosimy na początek następnej kolumny. Teraz nasze rozwiązanie wygląda następująco:

1

111010

+ 11011

01

W następnej kolumnie dodajemy 1, 0 i 0, otrzymujemy 1, którą wpisujemy pod tą kolumną. 1 i 1 z następnej kolumny daje łącznie 10: zapisujemy 0 pod kolumną i przenosimy 1 do następnej kolumny. Teraz nasze rozwiązanie wygląda następująco:

1

111010

+ 11011

0101

W kolejnej kolumnie 1, 1 i 1 dają łącznie 11 (zapis binarny wartości trzy); zapisujemy ostatnią 1 pod kolumną oraz przenosimy 1 na początek następnej kolumny. Dodajemy w niej 1 do 1 i uzyskujemy 10. Ponownie zapisujemy ostatnie 0 oraz przenosimy 1 do następnej kolumny. Teraz otrzymujemy

1

111010

+ 11011

010101

Jedyny wpis w następnej kolumnie to 1, którą przenieśliśmy z poprzedniej kolumny. Zapisujemy ją zatem w odpowiedzi. Nasze ostateczne rozwiązanie jest następujące:

111010

+ 11011

1010101

Ułamki w notacji binarnej

Aby rozszerzyć notację binarną w celu uwzględnienia wartości ułamkowych, używamy kropki pozycyjnej pełniącej tę samą rolę co kropka dziesiętna w notacji dziesiętnej. Oznacza to, że cyfry po lewej stronie kropki reprezentują część całkowitą wartości i są interpretowane tak jak w omawianym wcześniej systemie binarnym. Cyfry po jej prawej stronie reprezentują ułamkową część wartości i są interpretowane w sposób podobny do innych bitów, z tym że ich pozycjom przypisuje się wartości ułamkowe. Oznacza to, że pierwsza pozycja po prawej stronie podstawy ma przypisaną wartość ½ (czyli 2-1), następna pozycja to wartość ¼ (czyli 2-2), kolejna ⅛ (czyli 2-3) i tak dalej. Należy zwrócić uwagę, że jest to po prostu kontynuacja zasady opisanej wcześniej: każdej pozycji jest przypisana wielkość dwukrotnie większa od wartości po jej prawej stronie. Przy wartościach przypisanych do pozycji bitów dekodowanie reprezentacji binarnej zawierającej kropkę pozycyjną wymaga wykonania tej samej procedury jak w przypadku zapisu bez kropki pozycyjnej. Dokładniej, mnożymy każdą wartość bitu przez wartość przypisaną do pozycji tego bitu w reprezentacji. Na przykład binarną reprezentację 101.101 można zdekodować do liczby 5/8, jak pokazano na rysunku 1.18.

Analogowo kontra cyfrowo

Przed nastaniem XXI wieku wielu badaczy zastanawiało się nad zaletami i wadami technologii cyfrowej w porównaniu do analogowej. W systemie cyfrowym wartość jest kodowana jako ciąg cyfr, a następnie przechowywana w postaci kilku obiektów, z których każdy reprezentuje jedną z cyfr. W systemie analogowym każda wartość jest przechowywana jako jeden obiekt, który może reprezentować dowolną wartość z ciągłego zakresu.

Porównajmy te dwa podejścia, wykorzystując wiadra z wodą jako obiekty magazynujące. Aby zasymulować system cyfrowy, możemy umówić się, że puste wiadro reprezentuje cyfrę 0, a pełne cyfrę 1. Następnie moglibyśmy zapisać wartość liczbową w rzędzie wiader za pomocą notacji zmiennoprzecinkowej (patrz podrozdział 1.7). Natomiast system analogowy moglibyśmy zasymulować, częściowo wypełniając jedno wiadro do punktu, w którym poziom wody oddawałby reprezentowaną wartość liczbową. Na pierwszy rzut oka system analogowy może wydawać się dokładniejszy, ponieważ nie byłby narażony na błędy obcięcia właściwe dla systemu cyfrowego (ponownie patrz podrozdział 1.7). Jednak jakikolwiek ruch wiadra w systemie analogowym mógłby spowodować błędy w ustaleniu poziomu wody, podczas gdy w systemie cyfrowym musiałaby rozlać się znaczna ilość wody, zanim rozróżnienie między pełnym i pustym wiadrem by się rozmyło. Zatem system cyfrowy byłby mniej wrażliwy na błędy niż system analogowy. Ta solidność i pewność jest głównym powodem, dla którego wiele zastosowań, które pierwotnie opierały się na technologii analogowej (takich jak komunikacja telefoniczna, nagrania audio i telewizja) przestawiło się na technologię cyfrową.

Ponadto techniki zastosowane w systemie dziesiętnym mają również zastosowanie w systemie binarnym. Oznacza to, że aby dodać dwie reprezentacje binarne z kropkami pozycyjnymi, po prostu wyrównujemy kropki pozycyjne i stosujemy ten sam proces dodawania jak poprzednio. Na przykład 10.011 dodane do 100.11 daje 111.001, jak pokazano tutaj:

Rysunek 1.18 Dekodowanie reprezentacji binarnej 101.101

1.5 Pytania i ćwiczenia

1. Przekształć każdą z poniższych reprezentacji binarnych na równoważną postać dziesiętną

a. 101010    b. 100001    c. 10111    d. 0110    e. 11111

2. Przekształć każdą z następujących reprezentacji dziesiętnych na równoważną postać binarną:

a. 32    b. 64    c. 96    d. 15    e. 27

3. Przekształć każdą z następujących reprezentacji binarnych na równoważną postać dziesiętną:

a. 11.01    b. 101.111    c. 10.1    d. 110.011    e. 0.101

4. Wyraź następujące wartości w notacji binarnej:

a. 4½    b. 2¾    c. 1⅛    d. 5/16    e. 5⅝

5. Wykonaj następujące dodawania w notacji binarnej:

a. 11011    b. 1010.001    c. 11111    d. 111.11

+ 1100 + 1.101 + 0001 + 00.01