Элементы теории множеств

Вероятностный подход

Подход к информации как мере уменьшения неопределенности знаний позволяет количественно измерять информацию, что чрезвычайно важно для информатики.

Объемный подход

В двоичной системе счисления знаки 0 и 1 будем называть битами (от английского выражения BinarydigiTs – двоичные цифры).

Группа из 8 битов информации называется байтом. Если бит — минимальная единица информации, то байт ее основная единица. Существуют производные единицы информации: килобайт (кбайт, кб), мегабайт (Мбайт, Мб) и гигабайт (Гбайт, Гб).

1 кб = 1024 байта. 1 Мб = 1024 кбайта.

1 Гб = 1024 Мбайта =

 

2. Информационные процессы. Информация в жизни человечества. Предмет и структура информатики. Классификация программного обеспечения.

Процессы, связанные с поиском, хранением, передачей, обработкой и использованием информации, называются информационными процессами.

Информация в жизни человека:

- появление письменности;

- изобретение печатных машин;

- изобретение радио, телефона;

- изобретение компьютера;

Предметом изучения является:

- процессы сбора, преобразования, хранения, защиты, поиска и передачи всех видов информации

Структура информатики:

Классификация ПО

Программное обеспечение принято по назначению подразделять на:

-системное (программное обеспечение, включающее в себя операционные системы, сетевое ПО, сервисные программы, а также средства разработки программ (трансляторы, редакторы связей, отладчики и пр.);

-прикладное (ПО, предназначенное для решения определенной целевой задачи из проблемной области. Часто такие программы называют приложениями);

-инструментальное (облегчает процесс создания новых программ для компьютера).

По способу распространения и использования на:

- несвободное (закрытое);

- открытое;

- свободное.

 

 

3. Представление чисел в двоичном коде. Системы счисления (позиционные и непозиционные). Действительное числа. Типы данных. 8-ая, 16-ая системы счислений.

Система счисления(далее СС) - совокупность приемов и правил для записи чисел цифровыми знаками.

 

В зависимости от способов изображения чисел цифрами, системы счисления делятся на непозиционные и позиционные. Непозиционной системой называется такая, в которой количественное значение каждой цифры не зависит от занимаемой ей позиции в изображении числа (римская система счисления). Позиционной системой счисления называется такая, в которой количественное значение каждой цифры зависит от её позиции в числе (арабская система счисления).

 

Действительные числа - объединение рациональных и иррациональных чисел называют действительными числами. Множество действительных чисел обозначают символом R.

 

Восьмери́чнаясисте́масчисле́ния — позиционная целочисленная система счисления с основанием 8. Для представления чисел в ней используются цифры от 0 до 7.

Восьмеричная система часто используется в областях, связанных с цифровыми устройствами. Характеризуется лёгким переводом восьмеричных чисел в двоичные и обратно, путём замены восьмеричных чисел на триплеты двоичных. Ранее широко использовалась в программировании и вообще компьютерной документации, однако в настоящее время почти полностью вытеснена шестнадцатеричной.

 

Шестнадцатеричная система счисления — позиционная система счисления по целочисленному основанию 16.

Обычно в качестве шестнадцатеричных цифр используются десятичные цифры от 0 до 9 и латинские буквы от A до F для обозначения цифр от 1010 до 1510, то есть (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F).

 

Традиционно выделяют два типа данных — двоичные (бинарные) и текстовые.

Двоичные данные обрабатываются только специализированным программным обеспечением, знающим их структуру, все остальные программы передают данные без изменений.

Текстовые данные воспринимаются передающими системами как текст, записанный на каком-либо языке. Для них может осуществляться перекодировка (из кодировки отправляющей системы в кодировку принимающей), заменяться символы переноса строки, изменяться максимальная длина строки, изменяться количество пробелов в тексте.

 

4. Представление символьных и текстовых данных в двоичном коде. Таблица ASCII.

 

Для передачи информации между собой люди используют знаки и символы. Начав с простейших условных жестов, человек создал целый мир знаков, где главным средством общения стал язык (т.е. речь и письменность). Слово есть минимальная первичная единица языка, представляющая собой специальный набор символов и служащая для наименования понятий, предметов, действий и т.п. Следующим по сложности элементом языка является предложение — конструкция, выражающая законченную мысль. На основе предложений строится текст.

 

С появлением вычислительных машин стала задача представления в цифровой форме нечисловых величин, и в первую очередь - символов, слов, предложений и текста.

 

Символы. Для представления символов в числовой форме был предложен метод кодирования, получивший в дальнейшем широкое распространение и для других видов представления нечисловых данных (звуков, изображений и др.). Кодом называется уникальное беззнаковое целое двоичное число, поставленное в соответствие некоторому символу. Под алфавитом компьютерной системы понимают совокупность вводимых и отображаемых символов. Алфавит компьютерной системы включает в себя арабские цифры, буквы латинского алфавита, знаки препинания, специальные символы и знаки, буквы национального алфавита, символы псевдографики — растры,

прямоугольники, одинарные и двойные рамки, стрелки.

 

В 1981 г. Институтстандартизации США принял стандарт кодовой таблицы, получившей название ASCII.В таблице ASCII содержится 256 символов и их кодов. Таблица состоит из двух частей: основной и расширенной. Основная часть (символы с кодами от 0 до 127 включительно) является базовой, она

в соответствии с принятым стандартом не может быть изменена. В нее вошли: управляющие символы арабские цифры, буквы латинского алфавита, знаки препинания,

специальные символы. Расширенная часть отдана национальным алфавитам, символам псевдографики и некоторым специальным символам.

 

 

5. Представление звуковых данных в двоичном коде.

Можно выделить два основных направления.

- Метод FM (FrequencyModulation) основан та том, что теоретически любой сложный звук можно разложить на последовательность простейших гармонических сигналов разных частот, каждый из которых представляет собой правильную синусоиду, а, следовательно, может быть описан числовыми параметрами, т.е. кодом. В природе звуковые сигналы имеют непрерывный спектр, т.е. являются аналоговыми. Их разложение в гармонические ряды и представление в виде дискретных цифровых сигналов выполняют специальный устройства - аналогово-цифровые преобразователи (АЦП). Обратное преобразование для воспроизведения звука, закодированного числовым кодом, выполняют цифро-аналоговые преобразователи (ЦАП). При таких преобразованиях неизбежны потери информации, связанные с методом кодирования, поэтому качество звукозаписи обычно получается не вполне удовлетворительным и соответствует качеству звучания простейших электромузыкальных инструментов с окрасом характерным для электронной музыки. В то же время данный метод копирования обеспечивает весьма компактный код, поэтому он нашёл применение ещё в те годы, когда ресурсы средств вычислительной техники были явно недостаточны.

 

- Метод таблично волнового (Wave-Table) синтеза лучше соответствует современному уровню развития техники. В заранее подготовленных таблицах хранятся образцы звуков для множества различных музыкальных инструментах. В технике такие образцы называют сэмплами. Числовые коды выражают тип инструмента, номер его модели, высоту тона, продолжительность и интенсивность звука, динамику его изменения, некоторые параметры среды, в которой происходит звучание, а также прочие параметры, характеризующие особенности звучания. Поскольку в качестве образцов исполняются реальные звуки, то его качество получается очень высоким и приближается к качеству звучания реальных музыкальных инструментов.

 

Существуют два способа звукозаписи:

- цифровая запись, когда реальные звуковые волны преобразуются в цифровую информацию путем измерения звука тысячи раз в секунду;

- MIDI-запись, которая, вообще говоря, является не реальным звуком, а записью определенных команд-указаний (какие клавиши надо нажимать, например, на синтезаторе). MIDI-запись является электронным эквивалентом записи игры на фортепиано.

 

 

6. Представление графических данных в двоичном коде.

Есть два основных способа представления изображений.

Первый — графические объекты создаются как совокупности линий, векторов, точек — называется векторной графикой.

Второй — графические объекты формируются в виде множества точек (пикселей) разных цветов и разных яркостей, распределенных по строкам и столбцам, — называется растровой графикой.

 

Модель RGB. Чтобы оцифровать цвет, его необходимо измерить. Немецкий ученый Грасман сформулировал три закона смешения цветов:

 

1) закон трехмерности — любой цвет может быть представлен комбинацией трех основных цветов;

2) закон непрерывности — к любому цвету можно подобрать бесконечно близкий;

3) закон аддитивности — цвет смеси зависит только от цвета составляющих.

 

За основные три цвета приняты красный (Red), зеленый (Green), синий (Blue). В модели RGB любой цвет получается в результате сложения основных цветов. Каждый составляющий цвет при этом характеризуется своей яркостью, поэтому модель называется аддитивной. Эта схема применяется для создания графических образов в устройствах, излучающих свет, — мониторах, телевизорах.

 

Модель CMYK. В полиграфических системах напечатанный на бумаге графический объект сам не излучает световых волн. Изображение формируется на основе отраженной волны от окрашенных

поверхностей. Окрашенные поверхности, на которые падает белый свет (т.е. сумма всех цветов), должны поглотить все составляющие цвета, кроме того, цвет которой мы видим. Цвет поверхности можно получить красителями, которые поглощают, а не излучают. Цвета красителей должны быть дополняющими:

 

голубой (Cyan = В + G), дополняющий красного;

пурпурный (Magenta= R + В), дополняющий зеленого;

желтый (Yellow = R + G), дополняющий синего.

 

Но так как цветные красители по отражающим свойствам не одинаковы, то для повышения контрастности применяется еще черный (black). Так как цвета вычитаются, модель называется субстрактивной.

 

7. Понятие сжатия информации. Структуры данных. Хранение данных.

Сжатие информации:

Разработаны и применяются два типа алгоритмов сжатия:

- сжатие с изменением структуры данных (оно происходит без потери данных);

- сжатие с частичной потерей данных.

 

Алгоритмы первого типа предусматривают две операции: сжатие информации для хранения, передачи и восстановление данных точно в исходном виде, когда их требуется использовать. Такой тип сжатия применяется, например, для хранения текстов.

 

Алгоритмы второго типа не позволяют полностью восстановить оригинал и применяются для хранения графики или звука.

 

Структуры данных.

Работа с большим количеством данных автоматизируется проще, когда данные упорядочены. Для упорядочивания данных применяют следующие структуры: линейные (списки), табличные, иерархические (дерево).

 

Линейная структура. Линейная структура данных (или список) — это упорядоченная структура, в которой адрес данного однозначно определяется его номером (индексом). Примером линейной структуры может быть список учебной группы или дома, стоящие на одной улице.

 

Табличная структура данных. Табличная структура данных — это упорядоченная структура, в которой адрес данного однозначно определяется двумя числами — номером строки и номером столбца, на пересечении которых находится ячейка с искомым элементом.

Иерархическая структура. Нерегулярные данные, которые трудно представляются в виде списка или таблицы, могут быть представлены в иерархической структуре, в которой адрес каждого элемента определяется путем (маршрутом доступа), идущим от вершины структуры к данному элементу.

 

Хранение данных.

Для устройств обработки данных, к которым относится и компьютер, большое значение имеет организация метода хранения информации на внешних носителях, позволяющих сохранять данныеэнергонезависимо. Способ хранения данных на таких носителях должен обеспечивать их целостность, доступность и защищенность. В настоящее время наиболее популярными внешними носителями являются flash-накопители. Разработчики программного обеспечения предложили оригинальный способ организации хранения информации: в виде файлов.

Под файлом понимается именованная область носителя, содержащая данные произвольной длины и воспринимаемая компьютерной системой как единое целое. Имя файла имеет особое значение, оно сопоставлено адресу размещения файла на носителе. Носитель имеет служебную таблицу, в каждой строке которой записано имя файла и адрес его местонахождения на носителе. Эта таблица используется специальной программой, которая называется файловой системой. Для доступа к данным она получает имя файла, находит по таблице его местоположение на носителе и возвращает содержимое файла. Как правило, процесс обработки информации сопровождается ее последующим сохранением. Для этого компьютерная программа объединяет какой-либо блок обрабатываемых данных в единое целое, снабжает его именем и передает файловой системе для записи на внешний носитель.

 

Имя файла состоит из некоторого набора символов и для большинства файловых систем может содержать до 256 знаков. Имя файла может быть дополнено расширением, которое определяет тип информации, хранящейся в файле. Расширение содержит от одного до четырёх символов и отделяется от имени точкой. Большинство программ при создании файла автоматически добавляют к имени свое уникальное расширение, которое помогает им в дальнейшем опознавать «свои» файлы.

Файл в числовом виде хранит информацию разных типов, например, текстовую, звуковую, графическую и т.д. Программа, создающая файл, размещает информацию в нем таким образом, чтобы при дальнейшей работе с файлом записанные данные можно было распознать и правильно извлечь. Способ представления данных в файле называется форматом файла. Формат определяет внутреннюю организацию информации, хранимой в файле. Открывая файл, прикладная программа проверяет его формат. Если он соответствует распознаваемым ею форматам, информация, хранящаяся в файле, извлекается в удобном для работы виде. Современные операционные системы автоматически распознают формат файла и самостоятельно запускают работающую с ним прикладную программу. Имеется возможность определять формат файла, не исследуя его структуры. Для этого используется его расширение. Анализируя расширение, операционная система определяет тип и структуру файла. Многие форматы файлов стандартизированы и используются соответствующими программными приложениями, работающими под управлением различных операционных систем.

Для удобства работы файлы объединяют в группы, их имена располагают в файле специального вида, называемом каталогом или папкой. Каталоги образуют иерархическую (древовидную) структуру. Каталоги, размещенные на вершине иерархии, называются каталогами первого уровня. Каталоги первого уровня могут содержать каталоги второго уровня и т.д. Каждый каталог содержит описание файлов или каталогов следующего уровня иерархии. Так же как и файлу, каталогу задается имя и атрибуты, позволяющие файловой системе манипулировать им: создавать, удалять, перемещать, добавлять в него файлы, каталоги и т.д.

 

 

8. Математические основы информатики. Алгебра высказываний (булева алгебра). Логические операции. Таблицы истинности.

Основное понятие булевой алгебры — выказывание. Под простым высказыванием понимается повествовательное предложение, о котором можно сказать, истинно оно или ложно (третьего не дано). Высказывания обозначаются латинскими буквами и могут принимать одно из двух значений: ЛОЖЬ (обозначим 0) или ИСТИНА (обозначим 1). В дальнейшем нас не будет интересовать содержательная часть высказываний, а только их истинность. Два высказывания А и В называются равносильными, если они имеют одинаковые значения истинности, записывается А = В.

Логические операции

Сложное высказывание можно построить из простых с помощью логических операций: отрицания, конъюнкции, дизъюнкции, импликации и логических выражений, представляющих собой комбинации логических операций. Рассмотрим их подробней.

Операцией отрицания А называют высказывание А (или -А, говорят не А), которое истинно тогда, когда А ложно, и ложно тогда, когда А истинно.

А	- А

 

Конъюнкцией (логическим умножением) двух высказываний А и В является новое высказывание С, которое истинно только тогда, когда истинны оба высказывания, записывается С = А & В

Таблица истинности этой операции, как следует из определения, имеет вид

А	В	А&В

 

Дизъюнкцией (логическим сложением) двух высказываний А и В является новое высказывание С, которое истинно, если истинно хотя бы одно высказывание. Записывается С = A v В

Таблица истинности такой операции следующая:

А	В	А V В

 

Импликацией двух высказываний А и В является новое высказывание С, которое ложно только тогда, когда А истинно, а В ложно, записывается С = А —> В.

Таблица истинности такой операции следующая:

А	В	А -->В

 

Эквиваленцией двух высказываний А и В является новое высказывание С, которое истинно только тогда, когда оба высказывания имеют одинаковые значения истинности, записывается С = А <--> В

Таблица истинности такой операции следующая:

А	В	А<-->В

 

9. Элементы теории множеств. Элементы теории графов.

Элементы теории множеств.

Множеством называется любое объединение определенных вполне различимых объектов; их может и не быть вообще. Можно говорить о множестве точек на отрезке [0,1], множестве студентов в группе, множестве снежных дней в июле на экваторе, т.е. множество образуют любые объекты, объединенные по любому признаку. Объекты, составляющие множество, называются элементами множества. Множество, не имеющее ни одного элемента, называется пустым, оно обозначается 0. Множество, состоящее из конечного числа элементов, называется конечным, в противном случае — бесконечным.

Задать множество можно перечислением его элементов.

Задать множество можно также, указав общее свойство для всех его и только его элементов.

Два множества считаются равными, если состоят из одних и тех же элементов.

Для множеств определены следующие операции: объединение, пересечение.

Объединением множеств А и В (записывается A ᴜ B) называется множество, состоящее из элементов как одного, так и второго множества.

Пересечением множеств А и В (записывается А ∩В) называется множество, состоящее из элементов, принадлежащих как одному, так и второму множеству одновременно.