понеділок, 24 листопада 2008 р.

Графіка в Інтернеті

Переважна більшість користувачів Internet дотепер застосовують в роботі звичайні телефонні лінії, що комутирують, і модеми, підтримуючі низьку (28 800-56 000 біт) швидкість передачі даних. Швидкість передачі найчастіше лімітується якістю телефонних ліній і великим завантаженням зовнішніх каналів, що особливо актуально для нашої країни. У такому випадку ця швидкість падає навіть нижче номінальної швидкості модему.
Графічна інформація передається значно повільніше, ніж текстова. Це визначає необхідність розумного підходу при створенні зображень для поширення по мережі. Розміри графічних файлів повинні бути не занадто великі, щоб користувач-читач не покинув сторінку тому, що йому набридло чекати закінчення її завантаження. Час завантаження зображень пропорційно розміру їх графічних файлів. Можна виділити чотири способи мінімізації цих розмірів:
1. зниження розмірів і дозволу зображень;
2. зменшення кількості кольорів у зображенні;
3. використання стислих і спеціальних форматів файлів, їхня оптимізація;
4. оптимізацію параметрів стиску для окремих фрагментів зображення.
Всі ці способи використаються при підготовці зображень для Web-сторінок. Важливо знайти компроміс між швидкістю і якістю зображення, щоб, не стомлюючи користувача тривалим очікуванням, представити ефектну й інформативну сторінку.
Для подання графіки в Internet широко використаються індексовані зображення. Вони, дозволяють передавати до 256 фіксованих кольорів. Набір кольорів зображення (палітра) зберігається у файлі разом із зображенням і використається браузером для демонстрації.
Зображення з індексованим кольором одержують із повно-кольорових зображень шляхом зменшення кількості кольорів. Кольори, що зустрічаються в зображенні, становлять його палітру. Відсутні в палітрі кольори передаються декількома сусідніми пікселями близьких кольорів. Розташовані поруч, вони сприймаються як якийсь "середній" колір.
Якщо дизайн Web-сторінки вимагає певного шрифту або особливого форматування, доводиться перекладати текст у растрове зображення. Особливо вдалим варто визнати використання для цієї мети індексованих кольорів. Для передачі тексту й малюнків 256 кольорів навіть зайві - можна обійтися й меншою кількістю. Індексовані формати надають вам таку можливість. Менша кількість кольорів дозволяє створювати графічні файли меншого розміру.
Як тільки передача графічної інформації із глобальних мереж стала звичайною справою, компанія CompuServe (найбільша On line служба) запропонувала формат GIF, в основі якого лежить ефективний (у відмінність від більше ранніх форматів, наприклад PCX) алгоритм стиску LZW. Цей формат використається в Internet і по сьогоднішній день. Він працює тільки с індексованими зображеннями. Другим форматом графічних файлів в WWW є JPEG, унікальний алгоритм якого дозволяє домагатися 15-кратної щільності стиску.
Високі щільності стиску досягаються ціною погіршення якості зображення, що неприйнятно для видавничих систем, але не дуже істотно для Web-сторінок. У форматі JPEG зберігаються повно кольорові напівтонові зображення, що чудово доповнює можливості формату GIF. Обоє формату - GIF й JPEG - підтримують чересстрочную розгорнення, коли зображення завантажується не підряд, а через трохи (2-5) рядків. Це виглядає так, начебто в міру завантаження сторінки зображення стає більш чітким і докладним.
Неможливість створення повно кольорових зображень із прозорими ділянками в рамках форматів GIF й JPEG привела до появи нового формату.
Формат PNG був розроблений як альтернатива формату GIF для подання зображень у мережі World Wide Web й в інших електронних мережах. Він зберігає всю колірну інформацію й один альфа-канал зображення. Крім того, для мінімізації обсягу файлу застосовується алгоритм ущільнення, що не приводить до втрати даних.. Щільність стиску png-файлів аналогічна щільності tiff-файлів, оскільки застосовуються подібні алгоритми, які не приводять до зниження якості зображень. На жаль, старі версії деяких браузерів не підтримують цей формат, але якщо ви орієнтуєтеся на Internet Explorer або Netscape Navigator, ви можете сміло ним користуватися.
Ідеального графічного формату для Internet не існує, оскільки кожний покликаний вирішувати строго певне коло завдань. Щоб частина пікселів зображення не була видна на Web-сторінці, вони повинні бути прозорими. Формати GIF й PNG підтримують збереження інформації про прозорість пікселів, але роблять це по-різному. Формат GIF дозволяє зарезервувати один із кольорів індексованої палітри під "прозорий колір". Ті пікселі зображення, які мають цей колір, інтерпретуються браузерами як прозорі. Замість них демонстрірується тло, що перебуває на Web-сторінці під зображенням. Очевидно, прозорість у форматі GIF не може бути часткової: піксель або прозорий, або немає. При імітації часткової прозорості надходять так же, як і при згладжуванні індексованих кольорів: сусідство прозорих і непрозорих пікселів сприймається як напівпрозорість.
У форматі PNG інформація про прозорість зберігається в альфа-каналі. Таким чином , вона реалізується не тільки для індексованих, але й для повно кольорових зображень. До того ж відтінки сірого в альфа-каналі дозволяють використати часткову прозорість. На жаль, не всі браузери повністю й правильно інтерпретують альфа-канали в png-файлах.
Однозначного рецепта для вибору програмного забезпечення для створення графіки для Web дати неможливо, тому що багато чого в цьому питанні залежить від переваг конкретного дизайнера. У цей момент для роботи з растром основна маса дизайнерів використають Adobe Photoshop, Corel Photopaint або Ulead Photo Impact. Для роботи з векторною графікою Adobe Illustrator, Corel Draw або Macromedia Freehand.
Для оптимізування графіки можна використати як стандартні засоби графічних пакетів (Photoshop, Photopaint і т.д.), так і спеціальне ПО. До такого ПО можна віднести Ulead Smart Saver, Adobe Image Ready і деякі інших. Так само можна використати спеціальні он-лайн сервіси, наприклад, http://www.gifwizard.com/

пʼятницю, 7 листопада 2008 р.

Степінь вершини

Вершини в графі можуть відрізнятись тим, скільком ребрам вони належать.
Степінь вершини - це кількість ребер, яким належить дана вершина.
Наприклад, в графі, показаному нижче
Вершина 1 має степінь2
Вершина 4 має степінь3

Вершина 2 має степінь 3
Степінь кожної вершини повного графа на одиницю менша числа його вершин। Вершина називається парною, якщо її степінь - число парне। Вершина називається непарною, якщо її степінь – число непарне.Вершини, які не належать жодному ребру, називаються ізольованими.Дослідимо деякі властивості графа на такій задачі.

Учасники конференції при знайомстві обмінювались конвертами з адресами. Довести, що: а). Всього було передано парну кількість конвертів.б).Число учасників, які обмінювались конвертами непарне число разів – парне.
Доведення:Нехай учасники конференції А1, А2, А3, ... , Аn – вершини графа, а ребра, які їх з”єднують- передані конверти.
а).Так як кожне ребро – це пара конвертів, то кількість переданих конвертів завжди в два рази більша за кількість ребер в графі.б).Кількість конвертів завжди рівна сумі степенів вершин графа, вона парна з попереднього доведення. Сума степенів буде парною тоді, коли вона не містить непарних доданків, або містить їх парну кількість.
В ході рішення задачі було доведено дві теореми.
Теорема 1.
В графі сума степенів його вершин завжди парне число і рівна подвоєному числу ребер графа.
Теорема 2.
Число непарних вершин будь-якого графа парне.
Теорема 3.
В будь-якому графі, який має n вершин( n>=2) завжди знайдеться хоча б дві вершини з однаковим степенем। ДоведенняДоведемо цю теорему від супротивного.Нехай в графі всі вершини мають різні степені, тобто для n вершин ці значення складають від 0 до n-1. Але якщо існує вершина з степенем 0, то вершина з степенем n-1 не може існувати, так як ця вершина повинна бути з”єнаною ребрами з усіма вершинами в тому числі і з тою, що має степінь 0. Інакше кажучи, в графі з n вершинами не можуть бути присутні вершини з степенями 0 та n-1. Отже знайдуться хоча б дві вершини, степені яких рівні між собою.

Завдання

1. Чи знайдеться граф, у якого 5 вершин, і одна вершина ізольована, а друга з степенем 4?

2. В бюро по туризму , яке складає маршрути мандрівок для автотуристів, які повинні проїхати з пункту S в пункт R і продивитися всі місцеві визначні місця. Пункти і всі шосейні дороги, з'єднані між собою представлені на схемі.
Допоможіть бюро скласти такий маршрут, щоб туристи в кожне пункт попадали лише один раз. Випишіть послідовність пунктів для кожного знайденого маршруту.


3. Скільки вийде шматків паперу, якщо спочатку було m шматків, деякі шматки розрізали на 5 частин, а всього було розрізано k шматків.
4. Скільки отримається шматків паперу, якщо спочатку було m шматків, деякі з шматків розрізали на n частин, а всього було розрізано k шматків.

четвер, 6 листопада 2008 р.

Повний граф, доповнення графа

Граф називається повним, якщо кожні дві різні його вершини з’єднані одним і тільки одним ребром.

На малюнку показаний повний граф з 4 вершинамиАле графи також можуть бути неповними, наприклад граф, показаний нижче


Граф, який не є повним, можна перетворити в повний з тими ж вершинами, прибавивши ребра, яких не вистачає. Позначимо даний граф Г, він неповний. Провівши потрібні ребра, ми отримуємо повний граф з такою ж кількістю вершин . Вершини графа Г і прибавлені ребра також утворюють граф, який називається доповненням графа.


Доповненням графа Г називається граф Г2 з тими ж вершинами, що і граф Г, і з тими і тільки тими ребрами, які необхідно додати до графа Г, щоб отримати повний граф.


Завдання
Намалюйте граф, який є доповненням графа Г, зображеного на малюнку


середу, 5 листопада 2008 р.

Знайомство з програмою Photoshop

Програма працює з цифровими растровими зображеннями, тобто з зображеннями, які являють собою набір пік селів, точок

У цій програмі можна створювати оригінали або імпортувати зображення, які зберігаються в інших форматах. Можна сканувати зображення, фотографії, або імпортувати відео кліпи, чи зображення які знятті цифровою камерою.

Растрові зображення являють собою сукупність точок – пікселів. Кожний піксель має своє положення і колір. Кожний об'єкт являє собою набір зафарбованих пікселів.

При опрацюванні растрових зображень користувач працює над точками. Всі зображення, які створюються в програмі – растрові.

Растрові зображення передають більшу точність. Якість растрових зображень залежить від роздільної здатності кількості пікселів по горизонталі і по вертикалі.

Векторні зображення формуються шляхом математичного опису фігур, які називаються векторами.



2. Рядок стану

Після завантаження програми перед нами з’являється екран який містить певні елементи .

Рядок стану знаходиться внизу екрана. В ньому відображаються розмір файлу, розширення і масштаб






Масшаб

Для зміни масштабу, можна ввести своє число.

Якщо зитримати курсор мишки на об’ємі, то з’явиться вікно, в якому демонструється зображення на друкованому листі. Вигляд інформації можна змінювати.









Вигляд інформації можна змінювати.

Для цього потрібно включити меню і вибрати степінь використання оперативної пам”яті, час виконання останньої операції і т.д.









Деяка інформація, яка відображається в рядку стану

Розмір документа

Об’єм на диску з одним слоєм // об’єм зі всіма слоями





Тимчасовий розмір

Використання на даний момент ОЗП // вся ОЗП для опрацювання зображення .

Якщо ліве число більше правого, то використовується віртуальна пам’ять, що сповільнює роботу.





Ефективність. Відображається процент операцій обробки зображення, для яких використовується тільки ОЗП. Якщо число менше 100 то використовується віртуальна пам’ять.

Поняття про граф

Для вирішення багатьох задач, може бути застосоване таке поняття, як граф.
Граф-це множина точок (вершин), які з’єднані між собою лініями, що називаються дугами або ребрам.
Приведемо приклад задачі, яка може бути розв’язана, за допомогою графів.Задача На вечірку запрошено шестеро людей, чи може бути така ситуація,що кожен знав тільки двох запрошених.
Розв’язання:Кожного з цієї компанії зобразимо точкою, і пронумеруємо їх। Якщо двоє знайомі, то з’єднаємо їх відрізком (ребром). Виявляється, що така ситуація не тільки можлива, але й може описуватися декількома схемами.









Тобто можна сказати, що граф-це сукупність об’єктів, зв’язками між якими служать ребр. Приклади графів з декількома вершинами та ребрами.





Прикладами графів можуть слугувати схеми метрополітенів, схеми шосейних чи залізничних доріг, карти, які показують зв’язки між окремими об’єктами