Структуры и алгоритмы обработки данных, часть 4

9.  Какие характеристики стека вам известны?

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

push

Добавить (положить) в конец стека новый элемент

pop

Извлечь из стека последний элемент

back

Узнать значение последнего элемента (не удаляя его)

size

Узнать количество элементов в стеке

clear

Очистить стек (удалить из него все элементы)

10.  Какие характеристики дека вам известны?

Деком (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь. Система команд дека:

push_front

Добавить (положить) в начало дека новый элемент

push_back

Добавить (положить) в конец дека новый элемент

pop_front

Извлечь из дека первый элемент

pop_back

Извлечь из дека последний элемент

front

Узнать значение первого элемента (не удаляя его)

back

Узнать значение последнего элемента (не удаляя его)

size

Узнать количество элементов в деке

clear

Очистить дек (удалить из него все элементы)

11.  Какие характеристики очереди вам известны?

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

Элементы очереди будем также хранить в массиве. При этом из очереди удаляется первый элемент, и, чтобы не сдвигать все элементы очереди, будем в отдельном поле m_start хранить индекс элемента массива, с которого начинается очередь. При удалении элементов, очередь будет "ползти" дальше от начала массива. Чтобы при этом не происходил выход за границы массива, замкнем массив в кольцо: будем считать, что за последним элементом массива следует первый.

Структуры и алгоритмы обработки данных, часть 3

7.  Расскажите о представлении линейных структур данных в ЭВМ

   Наиболее простой формой хранения данных в памяти ЭВМ является одномерный линейный список. Линейный список-это множество n>=0 объектов (узлов) Х(1), Х(2), Х(3)... Х(n) структурные свойства которого связаны только с линейным (одномерным) относительным расположением узлов. Если n>0, то X(1) является первым узлом; для 1<i<n узел X(i-1) предшествует узлу X(i), а узел X(i+1) следует за ним, X(n) является последним узлом, т. е. линейный список реализует структуру, которую можно определить как линейное упорядочение элементов данных.

  Линейный список X рассматривают как последовательность Х(1), Х(2), Х(3)... Х(n) компоненты которой идентифициро­ваны порядковым номером, указывающим их относительное расположение в X.

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

   Проблема представления логических структур данных в памяти ЭВМ заключается в нахождении эффективных методов отображения логической структуры данных на физическую структуру хранения. Такое отображение называют адресной функцией.

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

8. Расскажите о представлении нелинейных структур данных в ЭВМ

    Отношения между объектами реального мира часто носят нелинейный характер. Это могут быть отношения, определяемые логическими условиями, отношениями типа "один-ко-многим" или отношениями типа "многие-ко-многим". Отношения "один-ко-многим" носят иерархический характер и отображаются древовидными структурами. В виде иерархии может быть представлена например, структура учебных подразделений ВУЗа.

  Отношения "многие-ко-многим" носят более универсальный характер и отображается структурами графов. Пример такого отношения. Каждый ВУЗ распределяет своих выпускников на различные предприятия. В то же время предприятие поучает специалистов из различных ВУЗов.

     Граф общего вида состоит из ряда вершин (узлов) и ребер, связывающих пары вершин. Если в понятия "ребро" и "вершина" вложить определенную смысловую нагрузку, то графы можно использовать для представления данных. Так вершинам графа можно сопоставить определенные объекты, тогда ребра будут соответствовать отношениям между объектами. В литературе по структурам баз данных модель данных, имеющую вид ориентированного графа, называют сетью.

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

Структуры и алгоритмы обработки данных, часть 2

5. Охарактеризуйте линейные структуры данных

Линейные структуры данных – это структуры данных, в которых переход от одного элемента данных к другому не зависит от каких-либо логических условий, т.е. в линейных структурах используются лишь безусловные связи элементов.

 К линейным структурам относятся стеки, очереди и деки.

Очереди и стеки — это динамически изменяемые упорядоченные наборы элементов. Новые элементы в очередях и стеках всегда добавляются к одному и тому же концу набора — «входному концу».

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

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

6. Охарактеризуйте нелинейные структуры данных

Линейные - алгоритм в пошаговом исполнении от начала до конца.

Нелинейные - алгоритм с переходами по условию.

Структуры и алгоритмы обработки данных, часть 1

1.   Какие сигналы несут новую информацию?

Цифровые.

2. Укажите причины появления искажений при взаимном преобразовании цифрового и аналогового сигнала

Непрерывную информацию мы всегда воспринимаем в дискретном виде. Но любая непрерывная информация может быть аппроксимирована дискретной информацией с любой степенью точности, поэтому дискретная форма представления информации – универсальна.

3.  Кратко охарактеризуйте известные вам типы данных

Типы float, double и long double предназначены для чисел с плавающей точкой и различаются точностью представления (количеством значащих разрядов) и диапазоном. Обычно float (одинарная точность) занимает одно машинное слово, double (двойная точность) – два, а long double (расширенная точность) – три.

Символьная переменная — это переменная типа char, занимающая в памяти 1 байт;

short, int и long вместе составляют целые типы, которые, в свою очередь, могут быть знаковыми (signed) и беззнаковыми (unsigned). В знаковых типах самый левый бит служит для хранения знака (0 – плюс, 1 – минус), а оставшиеся биты содержат значение. В беззнаковых типах все биты используются для значения. 8-битовый тип signed char может представлять значения от -128 до 127, а unsigned char – от 0 до 255.

4.  Кратко охарактеризуйте известные вам структуры данных

Строка – конечная линейная упорядоченная последовательность простых данных символьного типа, которое рассматривается как единое целое. Логическая структура строки представляет собой вектор или одномерный массив. Максимальная длина 255.

Линейный список – упорядоченная последовательность элементов данных.

Стеком (англ. stack) называется хранилище данных, в котором можно работать только с одним элементом: тем, который был добавлен в стек последним.

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

Структура – иерархически упорядоченная коллекция данных.

Деком (англ. deque – аббревиатура от double-ended queue, двухсторонняя очередь) называется структура данных, в которую можно удалять и добавлять элементы как в начало, так и в конец. Дек хранится в памяти так же, как и очередь.

Множество – произвольный набор однотипных элементов, понимаемое как единое целое.

Компания Microsoft выпустила предварительную версию Windows 8

      Компания Майкрософт выпустила предварительную версию Windows 8  Release Preview. 

В не таком далеком прошлом программисты старались уменьшить использование ресурсов компьютера, потому что у оперативной памяти и жесткого диска было очень маленькие объёмы. Сейчас же компании, которые выпускают игры стараются сделать как можно качественную графику, а соответственно и ресурсы компьютера задействуют по максимуму.      

      Какие же требования к компьютеру предъявляет Microsoft, чтобы установить Windiows 8 Release Preview? 

1) Процессор 1 ГГц и выше;

2) ОЗУ или оперативная память - 1 Гб для 32 разрядной системы и 2 Гб для 64 разрядной системы.

3) Свободное место на жестком диске: 16 Гб для 32 разрядной системы или 20 Гб для 64 разрядной системы. 

4) Графическое устройство Microsoft DirectX 9 с драйвером WDDM.
5) Для использования сенсорных возможностей требуется планшет или монитор с поддержкой мультисенсорной технологии.
6) Чтобы получить доступ к Магазину Windows для загрузки и запуска приложений, требуется активное подключение к Интернету и разрешение экрана не менее 1024 x 768 пикселей.
7) Для привязки приложений требуется разрешение экрана не менее 1366 x 768 пикселей.
8) Доступ к Интернету (может взиматься плата поставщиком услуг Интернета)

      Да, требования гораздо серьёзней, чем например у Windows XP. Приятно, что Майкрософт идёт вперед и изобретает новые операционные системы. К сожалению, слабенькие компьютеры не потянут ни Windows 8, ни WIndows 7. Таким образом пользователей компьютеров порой такая ситуация вынуждает покупать новое, не смотря на то, что старое тоже может хорошо работать.

      Например у компьютера с мощностью 1 Гб оперативной памяти и 1.7 ГГц процессор была установлена Windows Vista, которую неохотно приняли программисты и продвинутые пользователи. Компьютер зависал во время игры, попросили устранить проблему. Какое же действие помогло? Устранение всех виджетов на рабочем столе, они забирали последние ресурсы компьютера. После этого, проблем более не возникало. 

      Почему-то существует уверенность, что Windows 8 сначала не будет с радостью воспринята рядовыми пользователями и консерваторами, для которых пуск - это пуск в левом нижнем углу и так далее. Я до сих пор сижу на Windows XP Professional SP3. И доволен, более для работы ничего и не нужно, а всякие виджеты, красочные рисунки и "навороты" мешают и мне, и компьютеру, когда забирают память, которая порой очень нужна, когда идёт многозадачный режим. 

      Да кстати, про многозадачность вспомнился анекдот:

— Папа, а что такое многозадачность?

— Ну, это когда компьютер позволяет тебе делать несколько дел одновременно
— Покажешь?
— Сейчас, только дискету доформатирую…

      Прошли года, а анекдот не теряет своей правдивости, к примеру трудно перекачивать 1 Гб с диска внешнего жесткого и при этом заниматся видеомонтажём, компьютер просто зависнет. Многозадачность возможна, когда происходят легкие процессы. Например играет музыка и мы, параллельно, листаем фотографии. 

Мы переехали на свой собственный домен

Теперь мы располагаемся на сайте sourceprograms.ru
Блог будет существовать и дальше, сюда мы будем писать наши наблюдения за рынком IT-услуг, виденье нашими глазами новостей (так называемый "рерайт"). Также в ближайшее время планируем ввести в строй все наши проекты, которые были заморожены очень давно, например:
kakzarabotat-dengi.narod.ru будет рассказывать о проверенных видах заработка в интернете и в общем о коммерции в интернете;
np-so.narod.ru будет рассказывать о разных городах мира, в которых мы побывали;
все остальные планы пока не будем разглашать, думаю вскоре вы их увидите.
- - - - -
После долгого затишья, нам приятно вновь пообщаться с вами уважаемые читатели.
Следующее сообщение будет посвящено интересным новостям IT.
- - - - -
До скорой встречи!