1. За основную единицу измерения количества информации принят … А) 1 бит
2. Переведите число 101010101 из двоичной системы счисления в десятичную. D) 341
3. В какой системе счисления хранится информация в компьютере с технической точки зрения? А) двоичной
4. Сколько секунд минимум потребуется модему, передающему сообщения со скоростью 28800 бит/с, чтобы передать 100 страниц текста в 30 строк по 60 символов каждая, при условии что каждый символ кодируется одним байтом? D) 62,5 с
5. Число 11010111 в двоичной системе счисления соответствует числу в восьмеричной системе счисления: D) 327
6. Современный компьютер - это … В) многофункциональное электронное устройство для работы с информацией
7. В подъезде 16 квартир. Сколько информации несет сообщение о том, в какой квартире живет Ваш друг? С) 4 бита
8. Накопителем информации является С) диск
9. Четвертое поколение ЭВМ сконструировано на основе А) больших интегральных схем
10. Во время исполнения программа хранится в С) оперативной памяти
11. Единица выводимой информации при работе дисплея в графическом режиме называется…: В) пиксель
12. Каков минимальный объем памяти (в Кб), достаточный для хранения растрового изображения размером 128 х 128 пикселей, если известно, что используется палитра из 256 цветов. С) 16 Кбайт
13. Для хранения растрового изображения размером 64 х 64 пикселя отвели 1,5 Кб памяти. Каково максимально возможное число цветов в палитре. С) 8
14. Понятие "телекоммуникация" означает В) обмен информацией на расстоянии
15. Электронная почта позволяет передавать С) сообщения и приложенные файлы
Граф, изображенный на плоскости, называется плоским графом, если его ребра не пересекаются в точках, отличных от вершин графа. Заметим, что данное понятие касается только геометрического изображения графа, но не графа как множества вершин и связей. Часто один и тот же граф может быть изображён как плоский, так и как не плоский.
Важное практическое приложение плоских графов - прокладка коммуникаций между объектами при условии, что пересечение коммуникаций нежелательно.
Теперь об одном важном свойстве плоских графов. Сначала важное понятие. Гранью в плоском представлении графа называется часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов. Заметим, что часть плоскости, лежащая "вне" фигуры графа, также подходит под определение грани и считается гранью. При определении граней графа нужна осторожность - опасно пренебрегать выражением "не содержащая других циклов" в определении термина. Так, на рис. 2 область 2-4-3-5-2 не является гранью - она ограничена простым циклом, но сама содержит простой цикл 2-3-5-2.
Теперь собственно свойство. Пусть В - количество вершин в графе, Г - количество граней в плоском представлении графа, Р - количество рёбер в графе. Тогда получаем формулу Эйлера: В + Г - Р = 2 для связного графа. Для несвязного графа с K компонентами связности формула имеет вид В + Г - Р = K + 1. Подставьте в неё K=1 и сравните с предыдущей. Интересное совпадение, не правда ли?
Формула Эйлера для выпуклых многогранников Также заметим, что формула Эйлера выполняется для выпуклых многогранников. И это не случайно: выпуклый многогранник может быть представлен как плоский граф, если вершины и рёбра многогранника рассматривать как вершины и рёбра графа.
Теперь покажем это на деле: возьмём n-угольную пирамиду с выпуклым многоугольником в основании и "превратим" её в плоский граф (см. рис. 3). У пирамиды n+1 граней (основание и n боковых граней), n+1 вершин (n в основании и одна "обособленная") и 2n рёбер (n в основании и n соединяющих "обособленную" вершину" с остальными). Легко проверить - формула Эйлера тут работает.
Теперь разберёмся с плоским графом на рис. 3 справа. Аналогично несложно понять, что имеются n+1 вершин и 2n рёбер. Теперь разберёмся с гранями. Их опять n+1 (n граней-треугольников и "внешняя" грань вне фигуры). Снова формула Эйлера работает: n+1+n+1-2n=2.
Сейчас похожий фокус проделаем с n-угольной призмой. Имеем n+2 граней (два основания и n боковых граней), 2n вершин (по n вершин в каждом основании) и 3n рёбер (по n в каждом основании и ещё n соединяющих основания). Получаем B + Г - Р = 2.
Теперь разбираемся с графом. Количество вершин и рёбер считается легко. Граней снова n+2: "внутренний" n-угольник, n четырехугольников и "внешняя" грань. И снова формула Эйлера работает.
Планарные графы и проверка на планарность Планарный граф - граф, который может быть изображён как плоский. Приведём пример планарного графа:
Не всякий граф является планарным графом. Согласно теореме Куратовского-Понтрягина (иногда её также называют теоремой Понтрягина-Куратовского, а иногда и вовсе опускают одну из фамилий), граф планарен тогда и только тогда, когда он не содержит подграфов типов, приведённых на рис. 6.
На основе теоремы Куратовского-Понтрягина очень просто получить один примечательный вид непланарных графов. Поскольку полный граф с 5 вершинами непланарен, а полный граф с n>5 вершинами содержит такой подграф, то верно следующее. Полный граф с n>4 вершинами обязательно непланарен.
На первый взгляд кажется, что всё просто - у нас лишь два типа "вредных" подграфов. На самом же деле задача анализа большого графа на наличие таких подграфов весьма непроста. Одним из алгоритмов, проверяющих, планарен ли граф, является алгоритм, разработанный в 1970г. Хопкрофтом и Тарьяном и улучшенный ими в 1974г. Алгоритм работает за линейное время.
А) 1 бит
2. Переведите число 101010101 из двоичной системы счисления в десятичную.
D) 341
3. В какой системе счисления хранится информация в компьютере с технической точки зрения?
А) двоичной
4. Сколько секунд минимум потребуется модему, передающему сообщения со скоростью 28800 бит/с, чтобы передать 100 страниц текста в 30 строк по 60 символов каждая, при условии что каждый символ кодируется одним байтом?
D) 62,5 с
5. Число 11010111 в двоичной системе счисления соответствует числу в восьмеричной системе счисления:
D) 327
6. Современный компьютер - это …
В) многофункциональное электронное устройство для работы с информацией
7. В подъезде 16 квартир. Сколько информации несет сообщение о том, в какой квартире живет Ваш друг?
С) 4 бита
8. Накопителем информации является
С) диск
9. Четвертое поколение ЭВМ сконструировано на основе
А) больших интегральных схем
10. Во время исполнения программа хранится в
С) оперативной памяти
11. Единица выводимой информации при работе дисплея в графическом режиме называется…:
В) пиксель
12. Каков минимальный объем памяти (в Кб), достаточный для хранения растрового изображения размером 128 х 128 пикселей, если известно, что используется палитра из 256 цветов.
С) 16 Кбайт
13. Для хранения растрового изображения размером 64 х 64 пикселя отвели 1,5 Кб памяти. Каково максимально возможное число цветов в палитре.
С) 8
14. Понятие "телекоммуникация" означает
В) обмен информацией на расстоянии
15. Электронная почта позволяет передавать
С) сообщения и приложенные файлы