Wstęp do informatyki

Jacek Lembas, Rafał Kawa

Uzyskaj dostęp

Zakup książkę

ISBN/ISSN:

978-83-01-19604-2

DOI:

Wydawnictwo:

Wydawnictwo Naukowe PWN

Rok wydania:

2017

Liczba stron:

304

XML:ISBN/ISSN:

ONIX MARC21

Bibliografia:

Lembas, Jacek; Kawa, Rafał. Wstęp do informatyki. Red. . Warszawa: Wydawnictwo Naukowe PWN, 2017, 304 s. ISBN 978-83-01-19604-2

Bibliografia refWorks:

RT Book, Whole

SR Electronic(1)

A1 Lembas, J.

A1 Kawa, R.

T1 Wstęp do informatyki

PB Wydawnictwo Naukowe PWN

PP Warszawa

YR 2017

SN 978-83-01-19604-2

Bibliografia BibTex:

@Book{ 182259, author = "Lembas, Jacek and Kawa, Rafał", editor = "", title = "Wstęp do informatyki", publisher = "Wydawnictwo Naukowe PWN", year = "2017", address = "Warszawa", isbn = "978-83-01-19604-2" }

Bibliografia endNote:

TY - BOOK

AU - Lembas, Jacek

AU - Kawa, Rafał

ED -

TI - Wstęp do informatyki

PB - Wydawnictwo Naukowe PWN

CY - Warszawa

PY - 2017

SN - 978-83-01-19604-2

ER -

Netografia (standard APA):

Lembas, Jacek; Kawa, Rafał. Wstęp do informatyki [baza danych online] Warszawa: Wydawnictwo Naukowe PWN, 2017 [dostęp: 03 07 2024]. Dostęp w Ibuk Libra: https://libra.ibuk.pl/reader/wstep-do-informatyki-jacek-lembas-rafal-kawa-182259.

algorytmy, komputer, informacja, algorytmika, języki programowania, podstawy informatyki

Publikacja przeznaczona jest głównie dla studentów pierwszego roku kierunków informatycznych, ale może zainteresować również słuchaczy wszystkich innych kierunków studiów, mających podstawy informatyki w programach oraz uczniów klas informatycznyc...

Więcej

ISBN/ISSN:

978-83-01-19604-2

DOI:

Wydawnictwo:

Wydawnictwo Naukowe PWN

Rok wydania:

2017

Liczba stron:

304

XML:ISBN/ISSN:

ONIX MARC21

1. Wprowadzenie10
1.1. Informacja10
1.2. Podstawowe cechy informacji12
1.3. Informatyka14
1.3.1. Istota informatyki14
1.3.2. Informatyka a komputery15
1.4. Komputer16
1.5. Działy informatyki17
2. Teoria informacji20
2.1. Miara informacji20
2.2. Entropia źródła informacji24
2.3. Kodowanie komunikatów25
2.4. Algorytmy kodowania optymalnego30
2.4.1. Algorytmy Shannona-Fano31
2.4.2. Algorytm Huffmana33
2.4.3. Uzupełnienia37
3. Systemy liczbowe40
3.1. Wprowadzenie40
3.2. Analogowość, cyfrowość, binarność43
3.3. Działania na liczbach naturalnych w systemach pozycyjnych45
3.3.1. Dodawanie i odejmowanie45
3.3.2. Mnożenie i dzielenie46
3.3.3. Zapis liczb rzeczywistych47
3.4. Konwersje między systemami liczbowymi48
3.4.1. Konwersja do systemu dziesiętnego49
3.4.2. Konwersja do systemów niedziesiętnych50
3.4.3. Zależność podstaw systemów liczbowych54
4. Arytmetyka komputerowa58
4.1. Kodowania stałopozycyjne59
4.1.1. Kodowanie znak-moduł prosty60
4.1.2. Kodowanie odwrotnościowe64
4.1.3. Kodowanie uzupełnieniowe71
4.1.4. Kodowanie nadmiarowe78
4.2. Kodowania zmiennopozycyjne88
4.2.1. Wprowadzenie88
4.2.2. Normalizacja i jednoznaczność89
4.2.3. Algorytmy kodowania i dekodowania90
4.2.4. Reprezentatywność98
4.2.5. Efektywność i optymalizacja102
4.2.6. Działania na kodach zmiennopozycyjnych104
4.2.7. Praktyczne implementacje109
5. Maszyna Turinga110
5.1. Wprowadzenie110
5.2. Definicja111
5.3. Przykłady114
5.3.1. Pracowity bóbr stopnia trzeciego114
5.3.2. Inkrementacja liczby binarnej116
5.3.3. Inkrementacja liczby dziesiętnej119
5.3.4. Dekrementacja liczby binarnej121
5.3.5. Sumowanie przez inkrementację i dekrementację123
5.3.6. Dodawanie pisemne liczb binarnych125
6. Przykładowa Maszyna Cyfrowa (PMC)130
6.1. Architektura von Neumanna130
6.2. Budowa PMC132
6.3. Działanie PMC133
6.3.1. Interpretacja słowa maszynowego133
6.3.2. Rozkazy134
6.3.3. Tryby adresowania136
6.4. Realizacja przykładowych algorytmów137
6.3.4. Cykl pracy137
7. Podstawy algorytmiki148
7.1. Wprowadzenie148
7.2. Podstawowe pojęcia149
7.2.1. Pojęcie algorytmu149
7.2.2. Wstępne przykłady150
7.2.3. Zmienna152
7.2.4. Podstawienie153
7.2.5. Tablica155
7.3. Zapis algorytmów157
7.3.1. Zapis krokowy157
7.3.2. Schemat blokowy157
7.3.3. Strukturalne schematy blokowe166
7.3.4. Zapis liniowy, pseudokod178
7.4. Strukturalność187
7.4.1. Generalia187
7.4.2. Strukturalny zapis niestrukturalności189
7.5. Tworzenie algorytmów195
7.6. Złożoność algorytmów206
7.7. Poprawność algorytmów216
7.7.1. Wprowadzenie216
7.7.2. Podstawy217
7.7.3. Częściowa poprawność, niezmienniki pętli219
7.7.4. Częściowa poprawność wybranych algorytmów227
8. Notacje wyrażeń algebraicznych238
8.1. Generalia238
8.1.1. Podstawowe pojęcia238
8.1.2. Rodzaje notacji algebraicznych240
8.2. Notacje algebraiczne w informatyce243
8.3. Konwersje notacji244
8.3.1. Stos244
8.3.2. Sprowadzenie do zapisu liniowego244
8.3.3. Zamiana na odwrotną notację polską246
8.3.4. Wartościowanie wyrażeń w ONP249
8.4. Zapis algorytmów w ONP251
8.4.1. Konwersja zapisu algorytmów do ONP251
8.4.2. Odtworzenie algorytmów z zapisu w ONP259
9. Języki formalne264
9.1. Podstawowe pojęcia i oznaczenia266
9.1.1. Przykładowe alfabety268
9.1.2. Przykładowe języki270
9.2. Gramatyka formalna276
9.2.1. Intuicja276
9.2.2. Formalne definicje279
9.2.3. Hierarchia Chomsky’ego283
9.2.4. Jeszcze o gramatykach287
9.2.5. Gramatyki języków programowania295
9.3. Gramatyki regularne a maszyna Turinga297
9.3.1. Akceptacja słów języka regularnego297
9.3.2. Rozpoznawanie palindromów299
Indeks301

2.3.KODOWANIEKOMUNIKATÓW

wielesposobów-gorzej,lepiejlubnajlepiej,aponadtowedługróżnychkryteriówjakoś-

ciowych.Podobnezagadnienia,leżąceupodstawprzesyłaniainformacji,rozpatrywanesą

wniniejszympodrozdziale.

Dlauściśleniaijednoznacznościprzedstawimyniżejkilkaważnychpojęćwykorzy-

stywanychwdalszejczęścipodrozdziału.

•

Komunikatem

nazywaćbędziemykażdyprzekaz/wiadomośćniosącyinformację.Zauważmy,że

definicja,oczywistadlaprzekazywaniainformacjizużyciemśrodkówtechnicz-

nych,przestajebyćoczywistąwprzypadkuprzekazywaniainformacjizużyciem

ludzkiejmowy.Komunikacjaprzezmowęczygestysłużynietylkodoinformo-

wania,więcdefinicjakomunikatuzawężaszerokizakresmiędzyludzkiejkomuni-

kacjidoprzekazówczystoinformacyjnych,wykluczającwzasadzietrybpytający,

trybrozkazującyikilkainnychformgramatycznych.

•

Kodowaniem

będziemynazywaćfunkcjęprzypisującąkomunikatomciągiznakówzeskończo-

negozbioruznakówmożliwychdoodebrania.

•

Kodowaniembinarnym

nazywaćbędziemykodowaniewykorzystującedwuelementowyzbiórznaków.

Wyróżniamyjespośródinnychkodowańzwielupowodówopisanychwjednym

zkolejnychrozdziałów.Jednymzpowodówwynikającychzdotychczasowejwie-

dzyjestużyciapodstawy2wlogarytmiefunkcjiliczącejilośćinformacji.Dzie-

dzinakodowaniadopuszczadowolnelicznościużytychzbiorówznaków,jednak

istotapozostajeniezmienna,dlategowdalszejczęściużywaćbędziemywyłącznie

•

kodowańbinarnych.

Kodem

wzależnościodkontekstubędziemyokreślaćkodowanie(funkcję)lubkonkretną

wartośćfunkcjikodującejdlaargumentukomunikatu.

Średniadługośćkodowania

Rozpatrzmykilkaprzykładowychkodowańbinarnychzezbioremznakówkodowaniaobej-

mującymznaki0oraz1,źródłeminformacjiobejmującympięćkomunikatówoprawdo-

podobieństwachp

,…,p

wynoszącychodpowiednio1/2,1/4,1/8,1/16oraz1/16.Pod

uwagębierzemyczterykodowaniazamieszczonewponiższejtabeli:

1/2

1/4

1/8

1/16

kodowanie

pierwsze

drugie

trzecie

czwarte

000

001

010

011

100

001

110

111

110

1110

1111

Brak wyników

Wstęp do informatyki

Treść książki

Znajdź bibliotekę blisko siebie, i uzyskaj dostęp do ebooka w systemie IBUK Libra