Графы и деревья

Дерево — это связный ациклический граф.^[1] Связность означает наличие путей между любой парой вершин, ацикличность — отсутствие циклов и то, что между парами вершин имеется только по одному пути.

Ориентированное (направленное) дерево — ацикличный орграф (ориентированный граф, не содержащий циклов), в котором только одна вершина имеет нулевую степень захода (в неё не ведут дуги), а все остальные вершины имеют степень захода 1 (в них ведёт ровно по одной дуге). Вершина с нулевой степенью захода называется корнем дерева, вершины с нулевой степенью исхода (из которых не исходит ни одна дуга) называются концевыми вершинами или листьями. ^[2]

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

Теория графов - довольно молодая наука (по сравнению, скажем, с геометрией). В 1736 году Санкт-Петербургская академия наук опубликовала труд Леонарда Эйлера, где рассматривалась задача о кенигсбергскихмостах ("Можно ли, пройдя все городские мосты ровно по одному разу, вернуться в исходную точку?"). Это была первая работа по будущей теории графов.
Особенно приятно то, что в данном случае Россия - родина пусть и не новой породы слонов, но зато нового научного направления!
Графы: определения и примеры
Итак, перейдем к изложению некоторых понятий современной теории графов.
Неориентированные графы
Граф - это двойка <V, E>, где V - непустое множество вершин, а Е - множество ребер, соединяющих эти вершины попарно. Две вершины, связанные между собой ребром, равноправны, и именно поэтому такие графы называются неориентированными: нет никакой разницы между "началом" и "концом" ребра.

 

11)история компьютера

С 1975 г. в США было начато серийное производство персональных компьютеров (ПК). Это событие часто называют второй информационной революцией (первой информационной революцией считается появление печатного станка и книгопечатания – 1445 г.). ПК появился на базе мини- и микро ЭВМ для обеспечения персональных вычислений, т.е. для работы специалиста в той или иной предметной области на своем рабочем месте. За дисплей ПК смог сесть пользователь – непрофессионал в программировании. С 1981 г. стали выпускаться персональные ЭВМ, имеющие блочно-модульную конструкцию. Эти простые в эксплуатации и сравнительно дешевые машины предназначались для потребителей, не обладающих знаниями в области вычислительной техники и программирования. Широкое распространение мини-ЭВМ в начале 1970-х гг. определялось необходимостью приблизить компьютер к пользователю. Мини-ЭВМ устанавливались на предприятиях и в организациях, где использование больших ЭВМ было экономически невыгодным.

Таким образом, ПК – это компьютер, предназначенный для индивидуального использования. В настоящее время это мощный универсальный компьютер; он успешно работает как дома, так и на рабочих местах в офисах, легко подключается к различным вычислительным сетям.

Основные критерии отнесения компьютера к классу ПК – малые размеры, отсутствие необходимости в обслуживании, низкая цена, функциональная универсальность и простота модернизации.

Так как технической основой ПК служит микропроцессор, то именно их развитие определило смену поколений персональных ЭВМ:

8-разрядный микропроцессор (1975 – 1980 гг.);

16-разрядный (1981 – 1985 гг.);

32-разрядный (1986 – 1992 гг.);

64-разрядный (1993 г. – по настоящее время).

Важную роль в развитии ПК сыграло появление компьютера IBM PC, произведенного корпорацией IBM (США) на базе микропроцессора Intel-8086 в 1981 г. Этот персональный компьютер занял ведущее место на рынке себе подобных. Его основное преимущество – так называемая открытая архитектура, благодаря которой пользователи могут расширять возможности приобретенной ЭВМ, добавляя различные периферийные устройства и модернизируя компьютер. В дальнейшем другие фирмы начали создавать свои ПК, но компьютер IBM PC стал неким стандартом в классе персональных компьютеров. В наши дни более 85% всех продаваемых ПЭВМ базируется на архитектуре IBM PC.По назначению ПК классифицируют на бытовые, общего назначения и профессиональные.Бытовые и общего назначения ПЭВМ предназначены для массового потребителя, поэтому они должны быть достаточно дешевыми, надежными и иметь, как правило, простую базовую конфигурацию. ПК используют в домашних условиях для развлечений (видеоигры), обучения и др. Вместе с тем архитектура этих машин позволяет подключать их к каналам связи, расширять набор периферийного оборудования. Такие компьютеры также используются для работы с текстом, решения научных и инженерных задач. На ПК общего назначения работают, прежде всего, пользователи-непрофессионалы. Поэтому такие компьютеры снабжены развитым программным обеспечением, включающим операционные системы, трансляторы с алгоритмических языков, пакеты прикладных программ.

 

12) Логические элементы компьютера (вентили, триггеры, счетчики, регистры)

Логические элементы — устройства, предназначенные для обработки информации в цифровой форме (последовательности сигналов высокого — «1» и низкого — «0» уровней вдвоичной логике, последовательность «0», «1» и «2» в троичной логике, последовательности «0», «1», «2», «3», «4», «5», «6», «7», «8» и «9» в десятичной логике). Физически логические элементы могут быть выполнены механическими, электромеханическими (на электромагнитных реле), электронными (на диодах и транзисторах), пневматическими, гидравлическими, оптическими и др.С развитием электротехники от механических логических элементов перешли к электромеханическим логическим элементам (на электромагнитных реле), а затем к электронным логическим элементам на электронных лампах, позже — на транзисторах. После доказательства в 1946 г. теоремы Джона фон Неймана об экономичности показательных позиционных систем счисления стало известно о преимуществах двоичной и троичной систем счисления по сравнению с десятичной системой счисления. От десятичных логических элементов перешли к двоичным логическим элементам. Двоичность и троичность позволяет значительно сократить количество операций и элементов, выполняющих эту обработку, по сравнению с десятичными логическими элементами.Логические элементы выполняют логическую функцию (операцию) над входными сигналами (операндами, данными).Всего возможно логических функций и соответствующих им логических элементов, где — основание системы счисления, — число входов (аргументов), — число выходов, то есть бесконечное число логических элементов. Поэтому в данной статье рассматриваются только простейшие и важнейшие логические элементы.

Всего возможны двоичных двухвходовых логических элементов и двоичных трёхвходовых логических элементов (Булева функция).

Кроме 16 двоичных двухвходовых логических элементов и 256 трёхвходовых двоичных логических элементов возможны 19 683 двухвходовых троичных логических элементов и 7 625 597 484 987 трёхвходовых троичных логических элементов (троичные функции).

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

При изготовлении триггеров применяются преимущественно полупроводниковые приборы (обычно биполярные и полевые транзисторы), в прошлом — электромагнитные реле,электронные лампы. В настоящее время логические схемы, в том числе с использованием триггеров, создают в интегрированных средах разработки под различные программируемые логические интегральные схемы (ПЛИС). Используются, в основном, в вычислительной технике для организации компонентов вычислительных систем: регистров, счётчиков,процессоров, ОЗУ.

 

13)представление данных в памяти пк

Форма и язык представления информации. Воспринимая информацию с помощью органов чувств, человек стремится зафиксировать ее так, чтобы она стала понятной и другим, представляя ее в той или иной форме.Музыкальную тему композитор может наиграть на пианино, а затем записать с помощью нот. Образы, навеянные все той же мелодией, поэт может воплотить в виде стихотворения, хореограф выразить танцем, а художник — в картине.Человек выражает свои мысли в виде предложений, составленных из слов. Слова, в свою очередь, состоят из букв. Это — алфавитное представление информации.Форма представления одной и той же информации может быть различной. Это зависит от цели, которую вы перед собой поставили. С подобными операциями вы сталкиваетесь на уроках математики и физики, когда представляете решение в разной форме. Например, решение задачи: «Найти значение математического выражения..." можно представить в табличной или графической форме. Для этого вы пользуетесь визуальными средствами представления информации: числами, таблицей, рисунком.Таким образом, информацию можно представить в различной форме:

знаковой письменной, состоящей из различных знаков, среди которых принято выделять

символьную в виде текста, чисел, специальных символов (например, текст учебника);

графическую (например, географическая карта);

табличную (например, таблица записи хода физического эксперимента);

в виде жестов или сигналов (например, сигналы регулировщика дорожного движения);

устной словесной (например, разговор).