Teoretyczne podstawy informatyki Rozważamy zagadnienia teorii informacji Shannona, teorii kodowania, elementy teorii algorytmów i teorii automatów skończonych, a także ogólne problemy modelowania i opisywania systemów. Wybór materiału wyprodukowanego zgodnie z programem kształcenia studentów uczelni pedagogicznych w specjalności "030100-Informatyki". Każdy rozdział zawiera liczne przykłady rozwiązywania problemów, a także pytania i zadania dotyczące samokontroli. Dla studentów uniwersytetów pedagogicznych, studiujących informatykę jako podstawową dyscyplinę, a także szkolnych nauczycieli informatyki. Autor: Starichenko B.E ....
Słowo wstępne
Tak więc - sformułowania i najważniejsze stwierdzenia.
Wprowadzenie
Rozdział 1. TEORIA INFORMACJI
Początkowe definicje
Formy informacji
Konwersja wiadomości
Testuj pytania i zadania
Entropia jako miara niepewności
Przykład 2.1
Właściwości Entropy
Entropia złożonego eksperymentu złożonego z kilku niezależnych jest równa sumie entropii poszczególnych eksperymentów.
Wszystkie inne rzeczy są równe, doświadczenie z równorzędnymi wynikami ma największą entropię.
Warunkowa entropia
Przykład 2.2
Przykład 2.3
Entropia i informacje
Entropia doświadczenia jest równa informacjom, które otrzymujemy w wyniku jego realizacji.
Przykład 2.5
Przykład 2.7
Przykład 2.8
Informacje i alfabet
Testuj pytania i zadania
Rozdział 3. Kodowanie informacji symbolicznych
Oświadczenie o problemie kodowania, pierwsze twierdzenie Shannona
W przypadku braku zakłóceń zawsze możliwy jest wariant kodowania komunikatu, w którym redundancja kodu będzie arbitralnie bliska zeru.
W przypadku braku zakłóceń średnia długość kodu binarnego może być dowolnie zbliżona do średniej informacji na znak alfabetu pierwotnego.
Alfabetyczne niejednolite kodowanie binarne z sygnałami o równym czasie trwania. Kody prefiksów
Przykład 3.1.
Jednolite alfabetyczne kodowanie binarne. Kod bajtowy
Kodowanie alfabetyczne z nierównym podstawowym czasem trwania sygnału. Kod Morse'a
Zablokuj kodowanie binarne
Przykład 3.2.
Testuj pytania i zadania
Rozdział 4. Reprezentacja i przetwarzanie liczb w komputerze
Systemy liczbowe
Tłumaczenie liczb całkowitych z jednego systemu liczbowego na inny
Przykład 4.1
Przykład 4.2
Przykład 4.3
Przeniesienie ułamkowych liczb z jednego systemu liczbowego na inny
Przykład 4.4.
Przykład 4.5
Pojęcie sprawności systemu liczbowego
Przykład 4.6
Konwertowanie znormalizowanych liczb
Przykład 4.8
Przykład 4.9
Kodowanie liczb w komputerze i działania na nich
Kodowanie komputerowe i przetwarzanie liczb całkowitych bez znaku
Przykład 4.11
Przykład 4.12
Kodowanie komputerowe i przetwarzanie liczb całkowitych ze znakiem
Przykład 4.13
Przykład 4.14
Przykład 4.15
Kodowanie komputerowe i przetwarzanie liczb rzeczywistych
Przykład 4.16
Przykład 4.17
Testuj pytania i zadania
Ogólny schemat przekazywania informacji w linii komunikacyjnej
Charakterystyka kanału komunikacyjnego
Przykład 5.1
Wpływ szumu na szerokość pasma kanału
Przykład 5.2
Stwierdzenie problemu
Kody wykrywania błędów
Kody korekcji pojedynczego błędu
Przykład 5.3
Przykład 5.4
Równoległy kanał transmisji
Szeregowa transmisja danych
Komputerowa komunikacja za pośrednictwem linii telefonicznych
Testuj pytania i zadania
Klasyfikacja danych. Problemy z prezentacją danych
Prezentacja elementarnych danych w pamięci RAM
Struktury danych i ich reprezentacja w pamięci RAM
Klasyfikacja i przykłady struktury danych
Pojęcie rekordu logicznego
Organizacja struktur danych w pamięci RAM
Hierarchia struktur danych na zewnętrznych nośnikach
Funkcje urządzeń pamięci masowej
Testuj pytania i zadania
Rozdział 2. ALGORYTMY. MODELE. SYSTEMY
Lax definicja algorytmu
Funkcje rekurencyjne
Przykład 7.2
Przykład 7.4
Przykład 7.5
Klasa algorytmicznych (lub obliczalnych maszynowo) funkcji liczby częściowej pokrywa się z klasą wszystkich częściowo rekurencyjnych funkcji.
Ogólne podejścia
Algorithmic Post Machine
Przykład 7.6
Przykład 7.7
Algorytmiczna maszyna Turinga
Przykład 7.8
Przykład 7.9
Każdy algorytm można zdefiniować za pomocą diagramu funkcjonalnego i zaimplementować w odpowiedniej maszynie Turinga.
Normalne algorytmy Markowa
Przykład 7.11
Przykład 7.12
Porównanie modeli algorytmicznych
Problem algorytmicznej rozpuszczalności
Złożoność algorytmów
Testuj pytania i zadania
Rozdział 8. Formalizacja prezentacji algorytmów
Formalna gramatyka
Przykład 8.1
Przykład 8.2
Sposoby opisywania języków formalnych
Metody prezentacji algorytmów
Wykonawca algorytmu
Ciąg słowny algorytm
Forma graficzna nagrania
Klasyfikacja metod prezentacji algorytmów
Twierdzenie strukturalne
Dowolny algorytm niestrukturalny może być skonstruowany jako równoważny algorytm strukturalny.
Testuj pytania i zadania
Rozdział 9. Zrozumienie maszyny stanu
Ogólne podejścia do opisu urządzeń do przetwarzania dyskretnych informacji
Dyskretne urządzenia bez pamięci
Przykład 9.1
Sposoby ustawiania automatu stanów
Przykład 9.2.
Przykład 9.3
Obwody elementów logicznych i opóźnień
Przykład 9.4
Równoważne automaty
Przykład 9.5
Testuj pytania i zadania
Rozdział 10. Modele i systemy
Koncepcja modelu
Ogólna koncepcja modelowania
Klasyfikacja modeli
Modele strukturalne i funkcjonalne
Modele na pełną skalę i informacyjne
Modele sprawdzone i niemożliwe do zweryfikowania
Zaprojektowane modele
Pojęcie modelu matematycznego
Definicja obiektu
Definicja systemu
Systemy statyczne i dynamiczne
Systemy zamknięte i otwarte
Systemy naturalne i sztuczne
Formalny system
Przykład 10.1
Przykład 10.4
Formalizacja wartości
Etapy rozwiązywania problemu za pomocą komputera
Podejście obiektowe w informatyce stosowanej
Testuj pytania i zadania
Wniosek
A.1. Pojęcie prawdopodobieństwa
Przykład A.1
A.2. Dodawanie i mnożenie prawdopodobieństw
Prawdopodobieństwo wystąpienia któregokolwiek z dwóch wyników zdarzeń niezależnych i niezgodnych jest równe sumie ich prawdopodobieństw.
Przykład A.3
Przykład A.4
A.3. Prawdopodobieństwo warunkowe
Przykład A.5
Przykład A.7
Testuj pytania i zadania
Glosariusz
Referencje