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 ....

1. Słowo wstępne

2. Tak więc - sformułowania i najważniejsze stwierdzenia.

3. Wprowadzenie

4. Rozdział 1. TEORIA INFORMACJI

5. Początkowe definicje

6. Formy informacji

7. Konwersja wiadomości

8. Testuj pytania i zadania

9. Entropia jako miara niepewności

10. Przykład 2.1

11. Właściwości Entropy

12. Entropia złożonego eksperymentu złożonego z kilku niezależnych jest równa sumie entropii poszczególnych eksperymentów.

13. Wszystkie inne rzeczy są równe, doświadczenie z równorzędnymi wynikami ma największą entropię.

14. Warunkowa entropia

15. Przykład 2.2

16. Przykład 2.3

17. Entropia i informacje

18. Entropia doświadczenia jest równa informacjom, które otrzymujemy w wyniku jego realizacji.

19. Przykład 2.5

20. Przykład 2.7

21. Przykład 2.8

22. Informacje i alfabet

23. Testuj pytania i zadania

24. Rozdział 3. Kodowanie informacji symbolicznych

25. Oświadczenie o problemie kodowania, pierwsze twierdzenie Shannona

26. W przypadku braku zakłóceń zawsze możliwy jest wariant kodowania komunikatu, w którym redundancja kodu będzie arbitralnie bliska zeru.

27. W przypadku braku zakłóceń średnia długość kodu binarnego może być dowolnie zbliżona do średniej informacji na znak alfabetu pierwotnego.

28. Alfabetyczne niejednolite kodowanie binarne z sygnałami o równym czasie trwania. Kody prefiksów

29. Przykład 3.1.

30. Jednolite alfabetyczne kodowanie binarne. Kod bajtowy

31. Kodowanie alfabetyczne z nierównym podstawowym czasem trwania sygnału. Kod Morse'a

32. Zablokuj kodowanie binarne

33. Przykład 3.2.

34. Testuj pytania i zadania

35. Rozdział 4. Reprezentacja i przetwarzanie liczb w komputerze

36. Systemy liczbowe

37. Tłumaczenie liczb całkowitych z jednego systemu liczbowego na inny

38. Przykład 4.1

39. Przykład 4.2

40. Przykład 4.3

41. Przeniesienie ułamkowych liczb z jednego systemu liczbowego na inny

42. Przykład 4.4.

43. Przykład 4.5

44. Pojęcie sprawności systemu liczbowego

45. Przykład 4.6

46. Konwertowanie znormalizowanych liczb

47. Przykład 4.8

48. Przykład 4.9

49. Kodowanie liczb w komputerze i działania na nich

50. Kodowanie komputerowe i przetwarzanie liczb całkowitych bez znaku

51. Przykład 4.11

52. Przykład 4.12

53. Kodowanie komputerowe i przetwarzanie liczb całkowitych ze znakiem

54. Przykład 4.13

55. Przykład 4.14

56. Przykład 4.15

57. Kodowanie komputerowe i przetwarzanie liczb rzeczywistych

58. Przykład 4.16

59. Przykład 4.17

60. Testuj pytania i zadania

61. Ogólny schemat przekazywania informacji w linii komunikacyjnej

62. Charakterystyka kanału komunikacyjnego

63. Przykład 5.1

64. Wpływ szumu na szerokość pasma kanału

65. Przykład 5.2

66. Stwierdzenie problemu

67. Kody wykrywania błędów

68. Kody korekcji pojedynczego błędu

69. Przykład 5.3

70. Przykład 5.4

71. Równoległy kanał transmisji

72. Szeregowa transmisja danych

73. Komputerowa komunikacja za pośrednictwem linii telefonicznych

74. Testuj pytania i zadania

75. Klasyfikacja danych. Problemy z prezentacją danych

76. Prezentacja elementarnych danych w pamięci RAM

77. Struktury danych i ich reprezentacja w pamięci RAM

78. Klasyfikacja i przykłady struktury danych

79. Pojęcie rekordu logicznego

80. Organizacja struktur danych w pamięci RAM

81. Hierarchia struktur danych na zewnętrznych nośnikach

82. Funkcje urządzeń pamięci masowej

83. Testuj pytania i zadania

84. Rozdział 2. ALGORYTMY. MODELE. SYSTEMY

85. Lax definicja algorytmu

86. Funkcje rekurencyjne

87. Przykład 7.2

88. Przykład 7.4

89. Przykład 7.5

90. Klasa algorytmicznych (lub obliczalnych maszynowo) funkcji liczby częściowej pokrywa się z klasą wszystkich częściowo rekurencyjnych funkcji.

91. Ogólne podejścia

92. Algorithmic Post Machine

93. Przykład 7.6

94. Przykład 7.7

95. Algorytmiczna maszyna Turinga

96. Przykład 7.8

97. Przykład 7.9

98. Każdy algorytm można zdefiniować za pomocą diagramu funkcjonalnego i zaimplementować w odpowiedniej maszynie Turinga.

99. Normalne algorytmy Markowa

100. Przykład 7.11

101. Przykład 7.12

102. Porównanie modeli algorytmicznych

103. Problem algorytmicznej rozpuszczalności

104. Złożoność algorytmów

105. Testuj pytania i zadania

106. Rozdział 8. Formalizacja prezentacji algorytmów

107. Formalna gramatyka

108. Przykład 8.1

109. Przykład 8.2

110. Sposoby opisywania języków formalnych

111. Metody prezentacji algorytmów

112. Wykonawca algorytmu

113. Ciąg słowny algorytm

114. Forma graficzna nagrania

115. Klasyfikacja metod prezentacji algorytmów

116. Twierdzenie strukturalne

117. Dowolny algorytm niestrukturalny może być skonstruowany jako równoważny algorytm strukturalny.

118. Testuj pytania i zadania

119. Rozdział 9. Zrozumienie maszyny stanu

120. Ogólne podejścia do opisu urządzeń do przetwarzania dyskretnych informacji

121. Dyskretne urządzenia bez pamięci

122. Przykład 9.1

123. Sposoby ustawiania automatu stanów

124. Przykład 9.2.

125. Przykład 9.3

126. Obwody elementów logicznych i opóźnień

127. Przykład 9.4

128. Równoważne automaty

129. Przykład 9.5

130. Testuj pytania i zadania

131. Rozdział 10. Modele i systemy

132. Koncepcja modelu

133. Ogólna koncepcja modelowania

134. Klasyfikacja modeli

135. Modele strukturalne i funkcjonalne

136. Modele na pełną skalę i informacyjne

137. Modele sprawdzone i niemożliwe do zweryfikowania

138. Zaprojektowane modele

139. Pojęcie modelu matematycznego

140. Definicja obiektu

141. Definicja systemu

142. Systemy statyczne i dynamiczne

143. Systemy zamknięte i otwarte

144. Systemy naturalne i sztuczne

145. Formalny system

146. Przykład 10.1

147. Przykład 10.4

148. Formalizacja wartości

149. Etapy rozwiązywania problemu za pomocą komputera

150. Podejście obiektowe w informatyce stosowanej

151. Testuj pytania i zadania

152. Wniosek

153. A.1. Pojęcie prawdopodobieństwa

154. Przykład A.1

155. A.2. Dodawanie i mnożenie prawdopodobieństw

156. Prawdopodobieństwo wystąpienia któregokolwiek z dwóch wyników zdarzeń niezależnych i niezgodnych jest równe sumie ich prawdopodobieństw.

157. Przykład A.3

158. Przykład A.4

159. A.3. Prawdopodobieństwo warunkowe

160. Przykład A.5

161. Przykład A.7

162. Testuj pytania i zadania

163. Glosariusz

164. Referencje