Питання з інформатики

1. Поняття інформаційної технології.

ІТ - кошти, методи та системи збору, передачі, обробки та представлення інформації користувачеві.

Існують 4 етапи еволюції:

Поява мовлення;

Поява писемності;

Поява коштів Вт (Сучасні і тд .).

У сучасному ІТ виділяють 3 складові:

Апаратне забезпечення (кошти Вт та оргтехніки - hardware);

Програмне забезпечення (прикладне та системне ПЗ, методичне та інформаційне забезпечення - software);

Організаційне забезпечення (включаючи людину в системи ІТ, взаємодія людини з цими системами, системне використання технічних і програмних засобів - orgware)

ІТ = нові ІТ = сучасні ІТ.

Нові ІТ -- сучасна ІТ технологія, що використовує розвинений (інтелектуальний) інтерфейс з кінцевим користувачем.

ІТ як прикладна наука, що вивчає фундаментальні співвідношення у великих інформаційних системах.

ІТ як практика - Інтелектуальна діяльність з проектування і створення конкретних технологій обробки даних.

В ІТ виділяють 3 складові:

Базові ІТ. Забезпечують рішення окремих компонентів у тієї чи іншої задачі, служать для створення прикладних ІТ. Наприклад: технології програмування, СУБД, системи розпізнавання зображення і тд.

Прикладні ІТ. Формуються на основі базових інформаційних технологій, які призначені для повної інформатизації об'єкта. Наприклад: САПР, АСУП, геоінформаційні системи.

що забезпечують ІТ. Забезпечують реалізацію базових і прикладних ІТ. На ринку представлені їх окремі частини. Наприклад: сучасна мікроелектронна база коштів Вт, перспективні системи та комплекси (оптичні й еволюційний, трансп'ютерів).

3.Основні методи організації текстових файлів.

Цепочечние файли.

До самої БД додається довідник, який має наступну структуру:

Ключ - значуще слово, що характеризує той чи інший документ. Поруч пишеться адресна посилання на той текстовий файл, який має даний ключ як значимий терміну. І до цієї підрядку додаються власне текстові файли.

Цепочечная модель: скільки індексних термінів у тексті виділено стільки і має бути посилань.

Переваги:

Максимальна довжина пошуку визначається найдовшою ланцюжком;

Нові записи (тексти) можна ставити в початок ланцюга, що спрощує її коригування.

Недоліки:

Ланцюги можуть бути довгими, якщо деякі терміни використовуються досить часто;

Необхідність виділення пам'яті для зберігання адресних посилань у самих текстах;

Якщо довідник дуже великий, він значно ускладнює роботу з текстами і вимагає організації додаткового доступу до себе самого.

Питання 5 (закінчення).

терміну k. Якщо Sk зменшується, то k або взагалі не розглядається як можливий індекс, або йому присвоюється негативний вагу.

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

Ми розглянули статистичні підходи (СП). Крім СП використовуються такі підходи, які передбачають місце розташування терміну в тексті.

Підходи:

1. У індексаціонние терміни включаються ті, які зустрічаються в назвах документів, назвах розділів, розділів і т.д.

2. Складаються списки значущих для деякої предметної області слів. Тобто складається глосарій за деякою предметної області.

Методи збільшення повноти. Часто буває необхідно видати найбільше число релевантних документів з масиву. У цьому випадку необхідно до використовуваних індексаціонним термінів додати додаткові, щоб розширити область пошуку.

1-й підхід до вирішення цього завдання: використання термінів заступників зі словника синонімів, який називають тезаріусом, в якому терміни згруповані в класи.

2) Метод асоціативного індексування. Заснований на використанні матриці асоційованого термінів, яка задає для кожної пари термінів показник асоційованими. Абсолютна запис цього ПА між термінами j і k:

f (j; k) = сум (i = 1 - n) fij * fjk - частота спільного використання f (j; k) = сум (i = 1 - n) fij * fjk/(сум (i = 1 - n) fij ^ 2 + сум (i = 1 - n) fjk ^ 2 - сум (i = 1 - n) fij * fjk -- для розрахунку відносного значення цього показника. fij, k - частота появи терміну j або k в i - м документі. 0 investigations -> artificial intelligence -> creation.

18.Задача автоматичного реферування текстів і методи її вирішення.

Завдання створення рефератов - завдання виявлення списку документів та короткий його подання.

Вихідні дані:

масив вихідних даних;

готові вектора документів (тобто вже повинна бути вирішена задача створення векторів (tik, wik }).

Методи для автореферірованія:

Розрахунковий -- визначаються ваги словосполучень, що містять 2 значущих терміну з вектора документа.

w = 1/2t * wi1 * wi2 - вага словосполучення з 2-х термінів.

wi1 і w i2 - ваги 1-го і 2-го терміну з вектора.

t -- кількість слів у тексті між термінами ti1 і t i2, які не є значимими.

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

Позиційний метод. Включає в себе наступні НЕ альтернативні кроки:

Найбільш значущі пропозиції, які або починають, або закінчують абзац або розділ.

Виключаються питальні речення, незважаючи на їхнє положення в абзаці.

До значущим відносяться пропозиції, що містять слова - підказки. Наприклад: "дана (слово-підказка) робота виконана по такому - то плану і т.д. "

З значущих виключаються ті пропозиції, в яких є посилання на малюнки, таблиці, цитати і т.д.

19.Цепочечние текстові файли.

До самої БД додається довідник, який має наступну структуру:

Ключ - значуще слово, що характеризує той чи інший документ. Поруч пишеться адресна посилання на той текстовий файл, який має даний ключ як значимий терміну. І до цієї підрядку додаються власне текстові файли.

Цепочечная модель: скільки індексних термінів у тексті виділено стільки і має бути посилань.

Переваги:

Максимальна довжина пошуку визначається найдовшою ланцюжком;

Нові записи (тексти) можна ставити в початок ланцюга, що спрощує її коригування.

Недоліки:

Ланцюги можуть бути довгими, якщо деякі терміни використовуються досить часто;

Необхідність виділення пам'яті для зберігання адресних посилань у самих текстах;

Якщо довідник дуже великий, він значно ускладнює роботу з текстами і вимагає організації додаткового доступу до себе самого.

20.Інвертірованние текстові файли.

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

Недолік: змінне число адрес в довіднику.

Гідність: швидкий пошук релевантних документів, так як їх адреси знаходяться відразу в довіднику, обробку якого можна організувати в оперативній пам'яті.

21.Рассредоточенние текстові файли.

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

Тут немає довідника, а існує обчислювальна процедура, тобто блок, названий блоком рандомізації, який по ключу (пошуковий термін) на підставі обчислювальної процедури визначає адресу, за якою знаходиться текст.

Ключ адреса цю ділянку

(ключ) пам'яті

називається

Бакет

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

Переваги:

Швидкий обчислюваний доступ;

Через відсутності довідника економиться пам'ять.

Недоліки:

Складність при виборі методу хешування;

Застосовується для коротких векторів запитів, коли в пошуку бере участь трохи слів;

Зміни векторів документів породжує складність у веденні файлів.

Питання 27 (закінчення).

4. Корекція кластерів зверху вниз.

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

Способи вибору початкових класів:

Як центрів класів використовуються випадкові документи;

Класом з ім'ям i можна вважати безліч документів, у векторах яких знаходиться термін i;

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

Процес корекції кластерів:

Обчислюється КП між кожним документом і кожним Центроїд кластеру;

Кластери перевизначаються шляхом віднесення документів до тих з них, по відношенню до яким, вони мають найбільшу подібність;

Формуються Центроїд нових кластерів.

Ці 3 кроки виконуються до тих пір, поки:

Буде необхідність у змінах;

Щоб процес не був нескінченним, він виконується в задане число ітерацій.

5.Однократная кластеризація.

Документи розглядаються в довільному порядку і кожен документ або відноситься до існуючого класу, якщо КП достатній, або утворює новий кластер.

"+": кожен документ обробляється тільки 1 раз, => потребує мало часу.

"-": склад і структура класів суттєво залежить від порядку розгляду документів.

28. Знаходження КЛИК.

Кліка - такий вид кластеру, в якому кожен документ подібний до будь-якого іншого документу. Кліка формується тоді, коли виникає повний граф, тобто повне співвідношення подібності між всіма елементами.

А В

З Д

Вихідними даними для методу є матриця подібності документа масиву, яка заповнюється коефіцієнтами подібності всіх пар документів.

Матриця: S (Di, Dj) - діагональна квадратна і симетрична.

i = 1, N; j = 1, N.

Нехай задано безліч пар:

VDi = ((ti, wi))

VDj = ((tj, wj))

Коефіцієнт подібності документів визначається:

S (Di, Dj) = сум (k = 1, N) rk/N

r -- ставлення; N -- потужність безлічі документів.

0, wi = 0 або wj = 0

rk = wi/wj інакше

Щоб завдання вирішувалася адекватно, вектора (*) повинні бути впорядковані за термінами, тобто одні і ті ж терміни повинні бути записані в одних і тих самих позиціях цих векторів. Вихідна матриця, яка отримана в результаті розрахунків, перетвориться в бінарну наступним чином: вводиться деяке граничне значення T коефіцієнта подібності, і ті коефіцієнти, які менше його замінюються на 0, в іншому випадку на 1:

S (Di, Dj) 0

S (Di, Dj)> T, => 1

Алгоритм:

1.В клас чи кластер включаються підгрупи порядку 2, тобто ті елементи, які стосовно подібності встановлені на парі.

2.Із підгрупи порядку 2 отримують підгрупу порядку 3 за таким правилом: якщо є підгрупи (Di, Dj), (Di, Dp), (Dj, Dp), то отримуємо: (Di, Dj, Dp) і підгрупи з початкового списку виключаються.

3.Із підгрупи порядку p формують підгрупу порядку (p +1), тобто (Di, Dj, ..., Dp) => (Di, Dj, ...,

Питання 33 (продовження).

Послідовність.

Ця властивість гарантує, що користувач, що освоїв роботу в однієї частини системи не заплутається, працюючи в іншій її частині.

виражено у 3-х явища:

Послідовність в побудові фраз. Тобто вводяться коди або команди в системі завжди трактуються однаково;

Послідовність у використанні форматів даних - аналогічні поля завжди представляються в одному форматі (суперечить вимозі гнучкості);

Послідовність у розміщенні даних на екрані.

Рекомендується наступний шаблон для оформлення екрану:

Праворуч в 2-х, 3-х рядках міститься заголовок і дані про стан системи;

Далі, під заголовком розміщується область для виведення довідкових повідомлень;

Основна область - для малювання або для введення даних;

Нижче - область для виведення повідомлень про помилки;

Опис функціональних клавіш.

Стислість.

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

Рекомендації:

Не слід запитувати інформацію, яку слід сформувати автоматично;

Інформація не повинна виводиться відразу ж, тільки тому, що вона стала доступна системі. Вона повинна виводиться тільки в тому обсязі, який потрібно користувачеві і в потрібному для нього форматі.

Підтримка користувача - міра допомоги, яку система надає користувачеві при роботі з ній.

Ця підтримка виражається в 3-х видах:

Інструкції користувача. Виводяться у вигляді підказок або довідкової інформації. При цьому довідкова інформація повинна бути контекстної, своєчасною та доступною в будь-якій точці діалогу. Крім внутрішньосистемної існує зовнішня довідкова інформація, яка супроводжує текст у вигляді паперового носія. Там вказується 5 моментів:

Загальний огляд, у якому описується призначення системи, основні поняття предметної області, необхідні для оцінки системи, пов'язані з цими поняттями принципи роботи системи;

Як розпочати роботу з системою;

Відомості про поведінці користувача при виході системи або окремих частин з ладу;

Приклад роботи з системою;

Обмеження на систему.

Повідомлення про помилках. Гарне повідомлення про помилку повинно відповідати наступним вимогам:

Мабуть викладено в термінах, зрозумілих користувачеві;

Потрібно точно визначити причину помилки;

Повинно пояснювати, як виправити помилку;

Мабуть своєчасним, поки не виконані речі, які незворотні.

Підтвердження будь-яких дій системи.

Гнучкість - міра того, наскільки добре діалог відповідає різним рівням підготовки і продуктивності праці користувача. Гнучкість називають властивістю адаптивності системи. системи, які характеризують її гнучкість:

37.Тіпи діалогів.

4 типу діалогу:

питання - відповідь;

меню;

командний мова;

екранні форми.

Запитання - відповідь. Сама стара форма ведення діалогу. Використовується в експертних системах, в інформаційно - пошукових системах до фактографічних або документальним баз даних.

3 види діалогу в режимі "запитання - відповідь":

Діалог з обмеженнями на предметну область. Форма запиту - довільна (обмежень немає), а лексика запиту будується на базі 2-х словників. 1-й містить функціональні слова, які або означають характер завдання, яке потрібно вирішити, або носять допоміжний характер, тобто ті запити з якими користувач звертається до БД. Ці функціональні слова є ключовими, сенс їх жорстко регламентований.

2-й словник містить специфічні терміни, які характеризують дану предметну область і, як правило, є іменами полів із записами бази даних. 1-е обмеження: якщо існують надійні закінчення, то кожне слово із запиту потрібно спроектувати на слова зі словника(де максимальне перехід, то і брати). 2-е обмеження в рамках діалогу -- обмеження на мову.

Вимоги:

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

Кожне пропозиція повинна починатися з функціонального слова, що визначає потрібне дію.

При формулюванні умов пошуку кожне значення поля БД повинно передувати назвою цього поля.

3-я форма -- природно мовна без обмежень.

Цей діалог застосовується тоді, коли діапазон або занадто великий, або взагалі не визначений.

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

Меню -- орієнтований діалог.

Тут у користувача є список варіантів відповіді і він вибирає потрібний номер.

Види меню:

1.

2. З використанням мнемонічних позначень опцій (Norton Commander);

3. Блокової;

4. Рядкове меню;

5. Меню у вигляді піктограм.

Вимоги до меню:

Кожне меню повинно містити 5-6 опцій;

При великому числі різних варіантів їх треба групувати (підменю);

Пункти меню повинні слідувати в природному порядку або за алфавітом.

Застосування меню:

Діапазон можливих відповідей невеликий і вони всі відомі заздалегідь і можуть бути представлені явно;

Коли користувачеві необхідно бачити відразу всі опції для вибору оптимальної, щоб оцінити всі можливі варіанти;

Коли користувач недосвідчений.

40.Метод спадного синтаксичного аналізу (СА).

Спадний СА (розгорнення) - дерево розбору будується від коренів до листів.

СА методом розгорнення. Тут робиться припущення, що вихідна пропозиція вже належить мові, а отже до ній застосовується 1-а продукція граматики, в якій ліва частина є початковим символом граматики. Цей крок є 1-м кроком алгоритму розгортки. Введемо тут поняття елемента розгортки, роль якого на 1-му кроці права частина продукції.

2-й крок: з елемента розгортки вибирається крайній ліворуч нетермінальний символ. Нетермінальний символ замінюється правою частиною продукції з відповідною лівою частиною того ж списку продукції. Управління передається початку 2-го кроку цього алгоритму. Якщо ланцюжок не містить нетермінальних символів, вона порівнюється з вихідною аналізованої ланцюжком. Якщо вони співпадають, то кінець алгоритму, інакше перехід до кроку 3.

Крок 3: розбір виконується заново і при альтернативних варіантах продукції вибираються ті, які раніше не використовувалися. Тобто виконується розбір пропозиції фактично, по трохи іншій схемі.

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

41.Метод висхідного синтаксичного аналізу (СА)

Висхідний синтаксичний аналіз СА (згортка) - дерево розбору будується від листя до кореня.

Алгоритм висхідного лівостороннього СА:

Зліва у фразі виділяється слово з морфологічними ознаками (елемент згортки). Якщо фраза порожня, по виконується крок 4, інакше наступний крок;

Елемент згортки порівнюється з правими частинами продукцій. Якщо його збіг, то елемент згортки заміняється на ліву частину продукції і виконується передача на початок кроку 2. Якщо збігів немає виконується наступний крок.

Вибирається елемент з стека. Якщо при цьому стек порожній, то елемент згортки поміщається в стек і виконується крок 1, інакше елемент зі стека і елемент згортки замінюються на поняття елемент згортки і виконується крок 2.

Виконується коли фраза оброблене повністю. Тут вибирається елемент з стека. Це має бути початковий символ граматики. У цьому випадку, якщо, до того ж, стек порожній, 2 робимо висновки:

Пропозиція належить мові.

Збудували його структуру, яка використовується на етапі СЕА.

Якщо умова не виконується (стек не порожній), то або пропозицію побудовано синтаксично невірно, або при пакунку були використані не ті продукції. У цьому випадку повертаються на той крок СА, де була можливість вибору альтернативної продукції.

45.Задача управління доступом .

При вирішенні цього завдання виділяють 3 поняття:

Суб'єкт -- користувач, який виконує деякі операції над даними;

Об'єкт операції доступу - ті дані, до яких виконується доступ;

Вид операції доступу.

У загальному випадку розрізняють 3 види доступу:

Необмежений доступ до всіх даних;

Необмежений доступ до групи даних;

Обмежений доступ до групи даних. З обмеженням як у суб'єкта, так і за видами операцій.

Підхід до управління доступом.

Використання ключів і замків (ідентифікація та аутентифікація користувача). Ідентифікація -- характеристики користувача, які його визначають. Ідентифікація дозволяє визначити себе користувачеві, повідомивши своє ім'я. Замок (засіб аутентифікації) дозволяє 2-йстороне (ПК) переконатися що суб'єкт - той, за кого себе видає.

Способи ідентифікації:

Пароль, особистий ідентифікаційний номер або криптографічний ключ і т.д.;

Публічний картка;

Голос або відбитки пальців;

Щось, асоційоване із суб'єктом.

Найбільш розповсюджений спосіб - використання паролів, коли аутентифікація реалізується в програмному забезпеченні. Символічно алгоритм аутентифікації можна уявити:

Вихід у залежно від

кількості користувачів

Перевага цього методу - гнучкість, доступність і простота реалізації.

Недоліки:

Потрібно багаторазово вводити пароль;

Зміна замку впливає на велику кількість користувачів;

Замок управління може реалізувати тільки та особа, яка розробляє ці програми.

Підвищення надійності парольного захисту здійснюється:

Пароль повинен бути не дуже коротким і використовувати різні символи;

Періодично міняти паролі;

Якщо паролі не вбудовані в програму, а реалізовані у вигляді файлу, то обмежити доступ до файлу паролями;

Якщо можливі помилки в паролі, то потрібно обмежити число повторних введень пароля;

Використання генераторів паролів, які дозволяють формувати благозвучні (добре запам'ятовуються) паролі.

Якщо як ідентифікатора використовується особиста картка, для аутентифікації використовується пристрій, який називається токенів - пристрій, володіння яким дозволяє визначити справжність користувача.

2 види токенів:

Пасивні (токени з пам'яттю);

Активні (інтелектуальні) токени.

Найбільш поширеними з огляду на дешевизну є токени 1-го класу. Це пристрої з клавіатурою і процесором, а особиста картка забезпечена магнітною смугою. При використанні цього токена користувач із клавіатури вводить свій ідентифікаційний номер, який перевіряється процесором на збіг з карткою і далі перевіряється справжність самої картки. Недоліки: дорожнеча, використання спеціальних пристроїв читання, незручність використання. 22.Кластерние текстові файли.

Документи розбиваються на родинні групи, які називають кластерами або класами. Кожен клас описується Центроїд (профілем) і вектор запиту перш за все порівнюється з Центроїд класу.

Переваги:

Можливий швидкий пошук, тому що число класів, як правило, невелика;

Можливо інтерактивне звуження (розширення) пошуку за рахунок виключення або додавання додаткових кластерів.

Недоліки:

Необхідність формувати кластери;

Необхідність введення файлу Центроїд;

Додатковий витрата пам'яті для файлу Центроїд або профілів.

23.Основние способи визначення Центроїд.

1. Логічний профіль (позначається Р1).

задає вектор документів у наступному вигляді:

VDi = (d1, d2, d3, ..., dt), де t - число індексаціонних термінів, виділених у всіх документах нашого масиву. Тоді логічний профіль визначається як результат з логічною "або":

Р1 = VD1 v VD2 v VD3 v ...

1, якщо термін tk входить у вектор документа Di;

dk (k = 1, t) = 0, в іншому випадку.

2.Профіль частотного документа (Р2).

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

3.Профіль частотності терміна (Р3).

Тут використовуються ваги термінів у документах:

VDi = (w1, w2, w3, ..., wt), де wi - ваги термінів входять у вектор документа VDi.

У обчисленні Р3 беруть участь ваги.

Р3 (k = 1, t) = сум (j = 1, N) wik, де j - порядковий номер документа; N - число документів кластеру; t - число індексаціонних термінів у масиві; k -- порядковий номер терміну.

24. Логічний спосіб визначення Центроїд.

Логічний профіль (позначається Р1).

задає вектор документів у наступному вигляді:

VDi = (d1, d2, d3, ..., dt), де t - число індексаціонних термінів, виділених у всіх документах нашого масиву. Тоді логічний профіль визначається як результат з логічною "або":

Р1 = VD1 v VD2 v VD3 v ...

1, якщо термін tk входить у вектор документа Di;

dk (k = 1, t) = 0, в іншому випадку.

25.Профіль частотності документа.

Вихідні дані також вектора документів. Вихідна інформація задана матрицею, а у формулі використовуються НЕ логічне додавання, а арифметичне:

26.Профіль частотності терміна.

Тут використовуються ваги термінів у документах:

VDi = (w1, w2, w3, ..., wt), де wi - ваги термінів входять у вектор документа VDi.

У обчисленні Р3 беруть участь ваги.

Р3 (k = 1, t) = сум (j = 1, N) wik, де j - порядковий номер документа; N - число документів кластеру; t - число індексаціонних термінів у масиві; k -- порядковий номер терміну.

Питання 28 (закінчення).

Dp +1), якщо існують пари: (Di, Dp 1), (Dj, Dp 1), ..., (Dp, Dp 1).

Алгоритм закінчується, коли подальше злиття неможливо.

Недолік методу: утворюється велика кількість кластерів.

29.Метод одного зв'язку.

Тут класи представляються документами, між якими встановлені відносини подібності, які підпорядковуються наступного вимогу: між двома документами встановлюється зв'язок при виконанні одного з наступних умов: існують Di, Dj,

S (Di, Dk), S (Dk, Dj);

S (Di, Dk), S (Dk, Dm) , S (Dm, Dj);

Найсильніше вимога: S (Di, Dk) - якщо в матриці подібності вже існує подібність.

Якщо одне з умов виконується, то документи в одному класі.

30.Кластерізація навколо вибіркових документів.

Замість побудови матриці подібності використовують щільність простору деяких документів. Як можливі центрів кластеру виступають ті документи, які за результатами розрахунків виявилися розташованими в щільних зонах простору. Всі документи в цьому методі поділяються на 3 класи:

Документи, що вже включені у кластери;

Документи, ще що не піддався дослідженню (не включені в кластери);

Вільні документи. Ті документи, щодо яких робилася спроба включення до кластер, але вона закінчилася невдачею.

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

Алгоритм:

Вибирається черговий, не включений в кластери документ і вважається можливим центром кластеру;

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

Щільність вважається достатньою, якщо:

існує по щонайменше n1 документів, коефіцієнти подібності яких по відношенню до вибраного документу перевищує деяке граничне значення T1;

Існує по Принаймні n2 документів, коефіцієнти подібності (КП) яких, по відношенню до досліджуваного документу перевищують граничне значення T2;

Якщо між n2 і T2 існує деякий співвідношення: n2> = n1; T2 0

S (Di, Dj)> T, => 1

2.Метод однієї зв'язку.

Тут класи представляються документами, між якими встановлені відносини подібності, які підпорядковуються наступного вимогу: між двома документами встановлюється зв'язок при виконанні одного з наступних умов: існують Di, Dj,

S (Di, Dk), S (Dk, Dj);

S (Di, Dk), S (Dk, Dm) , S (Dm, Dj);

Найсильніше вимога: S (Di, Dk) - якщо в матриці подібності вже існує подібність.

Якщо одне з умов виконується, то документи в одному класі.

3.Кластерізація навколо вибіркових документів.

Замість побудови матриці подібності використовують щільність простору деяких документів. Як можливі центрів кластеру виступають ті документи, які виявилися розрахунків за результатами розташованими в щільних зонах простору. Всі документи в цьому методі поділяються на 3 класи:

Документи, що вже включені у кластери;

Документи, ще що не піддався дослідженню (не включені в кластери);

Вільні документи. Ті документи, щодо яких робилася спроба включення до кластер, але вона закінчилася невдачею.

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

Питання 30 (закінчення).

Документи, КП яких перевищує граничне значення T3, включаються до складу нового кластеру;

Документи, КП яких менше або дорівнює T3, але більше деякого порогового значення T4, включаються до безліч вільних документів;

Документи, КП яких не більше T4, називаються не включеними в кластери.

Цей процес повторюється до тих пір, поки всі документи не будуть віднесені до розряду вільних або не будуть включені в будь-якій кластер.

Розраховується КП всіх вільних документів з усіма Центроїд кластерів і там, де подібність виявиться максимальним і відносять кожен вільний документ.

31.Коррекція кластерів зверху вниз.

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

Способи вибору початкових класів:

Як центрів класів використовуються випадкові документи;

Класом з ім'ям i можна вважати безліч документів, у векторах яких знаходиться термін i;

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

Процес корекції кластерів:

Обчислюється КП між кожним документом і кожним Центроїд кластеру;

Кластери перевизначаються шляхом віднесення документів до тих з них, по відношенню до яким, вони мають найбільшу подібність;

Формуються Центроїд нових кластерів.

Ці 3 кроки виконуються до тих пір, поки:

Буде необхідність у змінах;

Щоб процес не був нескінченним, він виконується в задане число ітерацій.

32.Однократная кластеризація.

Документи розглядаються в довільному порядку і кожен документ або відноситься до існуючого класу, якщо КП достатній, або утворює новий кластер.

"+": кожен документ обробляється тільки 1 раз, => потребує мало часу.

"-": склад і структура класів суттєво залежить від порядку розгляду документів.

33.Основние критерії хорошого діалогу.

Природність;

Послідовність;

Стислість;

Підтримка користувача;

Гнучкість.

Природність - Властивості діалогу, відповідно до якого користувачеві не потрібно міняти свої традиційні способи вирішення завдання.

Властивість включає наступні аспекти:

Діалог повинен вестися рідною мовою користувача;

Стиль ведення діалогу має бути розмовною, тобто мається на увазі стислість;

Фрази не повинні вимагати додаткових пояснень;

Допускається використання жаргону користувача;

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

Повинна бути виключена попередня обробка даних перед їх введенням в систему.

35.Краткость і підтримка користувача як критерії хорошого діалогу.

Стислість.

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

Рекомендації:

Н?? слід запитувати інформацію, яку слід сформувати автоматично;

Інформація не повинна виводиться відразу ж, тільки тому, що вона стала доступна системі. Вона повинна виводиться тільки в тому обсязі, який потрібно користувачеві і в потрібному для нього форматі.

Підтримка користувача - Міра допомоги, яку система надає користувачеві при роботі з нею.

Ця підтримка виражається в 3-х видах:

Інструкції користувача. Виводяться у вигляді підказок або довідкової інформації. При цьому довідкова інформація повинна бути контекстної, своєчасною та доступною в будь-якій точці діалогу. Крім внутрішньосистемної існує зовнішня довідкова інформація, яка супроводжує текст у вигляді паперового носія. Там вказується 5 моментів:

Загальний огляд, у якому описується призначення системи, основні поняття предметної області, необхідні для оцінки системи, пов'язані з цими поняттями принципи роботи системи;

Як розпочати роботу з системою;

Відомості про поведінці користувача при виході системи або окремих частин з ладу;

Приклад роботи з системою;

Обмеження на систему.

Повідомлення про помилках. Гарне повідомлення про помилку повинно відповідати наступним вимогам:

Мабуть викладено в термінах, зрозумілих користувачеві;

Потрібно точно визначити причину помилки;

Повинно пояснювати, як виправити помилку;

Мабуть своєчасним, поки не виконані речі, які незворотні. будь-яких дій системи.

36.Гібкость як критерій хорошого діалогу.

Гнучкість - міра того, наскільки добре діалог відповідає різним рівням підготовки і продуктивності праці користувача. Гнучкість називають властивістю адаптивності системи.

Існує 3 системи, які характеризують її гнучкість:

Фіксована адаптація. При цьому користувач сам явно вибирає свій рівень підготовки;

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

Косметична. Займає проміжне місце між фіксованого повної і досягається використанням спеціальних прийомів:

Прийом використання скорочень (md - mkdir , Cd - chdir, *. bak);

Синоніми -- користувач вибирає те, що йому ближче;

Використання об'єктів за замовчуванням і макроси.

Питання

Алгоритм висхідного лівостороннього СА:

Зліва у фразі виділяється слово з морфологічними ознаками (елемент згортки). Якщо фраза порожня, по виконується крок 4, інакше наступний крок;

Елемент згортки порівнюється з правими частинами продукцій. Якщо його збіг, то елемент згортки заміняється на ліву частину продукції і виконується передача на початок кроку 2. Якщо збігів немає виконується наступний крок.

Вибирається елемент з стека. Якщо при цьому стек порожній, то елемент згортки поміщається в стек і виконується крок 1, інакше елемент зі стека і елемент згортки замінюються на поняття елемент згортки і виконується крок 2.

Виконується коли фраза оброблене повністю. Тут вибирається елемент з стека. Це має бути початковий символ граматики. У цьому випадку, якщо, до того ж, стек порожній, 2 робимо висновки:

Пропозиція принади