КОМБІНАТОРНІ МЕТОДИ У ЛІНГВІСТИЦІ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи № 2
з дисципліни «Методи опрацювання природної мови»
для магістрів галузі знань 12 «Інформаційні технології»
спеціальності 122 «Комп’ютерні науки та інформаційні технології»
спеціалізації «Системи штучного інтелекту»
Затверджено
на засіданні кафедри інформаційних систем та мереж
Протокол №01 від25.08.2016 р.
Львів-2016
Комбінаторні методи у лінгвістиці: Методичні вказівки до лабораторної роботи №2 / Укл.: В.А. Висоцька, Т.В. Шестакевич. – Львів: Видавництво Національного університету ”Львівська політехніка”, 2016. – 48 с.
Укладачі Висоцька В.А., к.т.н., доцент
Шестакевич Т.В., асистент
Відповідальний за випуск Литвин В.В., д.т.н., професор.
Рецензенти Берко А.Ю., д.т.н., професор.
Чирун Л.В., к.т.н, доцент.
ЗМІСТ
Вступ
1 ТЕОРЕТИЧНІ ВІДОМОСТІ
1.1 Елементи комбінаторного аналізу
1.1.1 Правило додавання
1.1.2 Правило добутку
1.1.3 Основне правило комбінаторики
1.2 Число різних k-елементних підмножин n-елементної множини
1.2.1 Розміщення з повтореннями
1.2.2 Розміщення без повторень
1.2.3 Перестановки
1.2.4 Сполуки
1.2.5 Сполуки з повтореннями
1.2.6 Перестановки з повтореннями, мультимножини
1.3 Впорядковане розбиття множин
1.4 Невпорядковане розбиття множин
1.5 Поліноміальна формула
1.6 Біном Ньютона
1.7 Інверсії
1.8 Зворотні перестановки
2 ВИСНОВКИ
3 КОНТРОЛЬНІ ПИТАННЯ
4 ЗАВДАННЯ
5 ЛІТЕРАТУРА
6 КОМБІНАТОРНІ СХЕМИ
7 ВИМОГИ ДО ЛАБОРАТОРНОЇ РОБОТИ
ДОДАТОК
Мета роботи: В даній роботі зроблений огляд типових задач комбінаторики. Знання та розуміння комбінаторних схем, вміння їх застосувати є важливим при для теоретичного аналізу текстів. Зацікавленому студентові рекомендується звернутися до спеціальної літератури.
Вступ
Запровадження інформаційних технологій у сферу інтелектуальної діяльності людини покликало до життя нову комунікативну систему «людина – машина – людина», в межах якої функціонування природної мови відрізняється від функціонування її в безпосередньому людському спілкуванні. Дослідження й опис природної мови в нових комунікативних системах вимагає й нових методів та підходів. Для розв’язування поставлених проблем прикладна лінгвістика повинна, використовуючи власне лінгвістичні дані, звертатися до багатьох інших дисциплін – кібернетики, математики, психології, фізики, медицини. Цим вона сприяє розширенню контактів мовознавчої науки з іншими науками і збагаченню лінгвістики новими очними методами дослідження мови. До них належать: методи математичної статистики, математичного програмування, булевої алгебри, імовірнісно-інформаційні методи, комбінаторні методи; структурні методи.
У зв’язку з поширенням інтелектуальних інформаційних систем обробки інформації та систем перекладу з однієї природної мови на іншу, зростає необхідність підготовки інженерних кадрів, які володіють точними методами у мовознавстві та можуть кваліфіковано та свідомо використовувати весь спектр сучасного програмного забезпечення у цій галузі. Застосування математичних методів у лінгвістиці обумовлено двома причинами.
По-перше, розвиток теорії і практики мовознавства вимагає введення все більш точних і об’єктивних методів для аналізу мови і тексту. Разом з тим, використання математичних прийомів при систематизації, вимірюванні та інтерпретації лінгвістичного матеріалу у поєднанні з якісним аналізом результатів дозволяє мовознавцям глибше проникнути у таємниці побудови мови і утворення тексту.
По-друге, контакти мовознавства з іншими науками (акустикою, фізіологією вищої нервової діяльності, кібернетикою та обчислювальною технікою тощо) постійно розширюються і можуть існувати тільки при використанні математичної мови, яка має високий ступінь загальності та універсальності для різних гілок знань. Особливо наполегливо математизується мовознавство у зв’язку з використанням природної мови в інформаційних і управлінських системах людина-машина-людина. В існуючих системах машинного перекладу, автоматичного анотування, людино-машинного діалогу будь-яке повідомлення на природній мові перекодовується в математичну мову комп’ютера.
Застосування математичних методів у мовознавстві має на меті замінити звичайно дифузну, інтуїтивно сформульовану і таку, що не має повного розв’язку, лінгвістичну задачу однією або декількома простішими, логічно сформульованими математичними задачами, які мають алгоритмічний розв’язок. Таке розділення складної лінгвістичної проблеми на простіші задачі, які алгоритмізуються, ми будемо називати математичною експлікацією лінгвістичного об’єкту або явища.
Математична експлікація цікава не тільки з чисто пізнавальної і теоретичної точки зору. Вона абсолютно необхідна при розв’язуванні прикладних завдань, пов’язаних з аналізом і синтезом усної мови або інформаційною обробкою текстів з використанням комп’ютера. Математична експлікація лінгвістичних об’єктів застосовується не тільки при розв’язуванні з допомогою комп’ютера нескладних, хоча і важливих задач такого типу, як упорядкування частотних і алфавітних словників або послівного і пооборотного машинного перекладу, але також при складанні і реалізації таких евристичних алгоритмів штучного інтелекту, як семантичний переклад або тезаурусне реферування тексту.
Відзначимо, що абстрактні моделі використовуються при вивченні мови дуже давно – з тих часів, як існує граматика. Такі елементарні поняття граматики, як підмет, присудок, відмінок, рід тощо, є достатньо абстрактними конструкціями, які відносяться до фактів мови саме як моделі. Усвідомити їх абстрактний характер важко лише через їх звичність. За своєю суттю ці поняття досить близькі до математичних. Тут доречно зауважити, що на базі понять підмета і присудка було вироблено центральне поняття сучасної математичної логіки – поняття предиката.
Створення абстрактних моделей завжди було головним засобом теоретичного вивчення мови. Але значення цього факту було усвідомлено лише на початку XX століття, коли у працях основоположників так званої структурної лінгвістики виникла концепція мови як абстрактної знакової системи, у якій визначальна роль належить не матеріальній природі знаків, а співвідношенням між ними. Тому засобом пізнання законів мови є побудова абстрактних моделей її структури та їх вивчення.
Із вказаної концепції природно було зробити висновок, що мову потрібно вивчати засобами, що є близькими до тих, котрими користується математика при аналізі своїх формальних систем. Ці системи, як і мова, характеризуються тим, що в них важливими є тільки відношення між об’єктами, а не матеріальна природа останніх. По суті, математичні системи – це спеціальні різновиди мови, які вирізняються особливо чіткою структурою. Іншими словами, математика може виявитись придатною метамовою для вивчення природних мов і тим самим стати універсальною мовою лінгвістики. Саме це і відбулося з виникненням математичної лінгвістики.
У середині 50-х років XX століття визначились основні принципи трактування лінгвістичних понять – і математична лінгвістика почала бурхливо розвиватись. Прискоренню її розвитку істотно сприяла та обставина, що власне тоді, у зв’язку з появою обчислювальних машин і швидким зростанням потоку наукової інформації, була поставлена задача автоматизованого перекладу, інформаційного пошуку, побудова штучного здорового глузду та розпізнавання мови. Ці задачі привернули до лінгвістики увагу спеціалістів у галузі точних наук і поставила до неї вимоги, які неможливо було задовольнити без різкого підвищення рівня строгості лінгвістичних понять.
З допомогою математичної лінгвістики можна вирішувати такі практичні задачі прикладної лінгвістики:
- Створення і вдосконалення писемності;
- Дешифрування невідомих писемностей;
- Автоматичне розпізнавання та автоматичний синтез усної мови;
- Удосконалення засобів зв’язку шляхом оптимізації мовної інформації;
- Автоматизований інформаційний пошук;
- Машинний переклад;
- Автоматичне оброблення текстів, записаних природними мовами;
- Автоматичне реферування та автоматичне індексування тексту.
1 ТЕОРЕТИЧНІ ВІДОМОСТІ
- 1Елементи комбінаторного аналізу
На практиці люди часто зустрічаються з задачами, в яких необхідно підрахувати число всіх можливих способів розміщення деяких предметів скінченої множини або число всіх можливих способів виконання певної дії зі скінченої множини таких дій. Наприклад, скількома способами можуть розподілитися медалі на чемпіонаті світу з футболу серед 16-ти команд-учасниць фінальної групи? Задачі такого типу називаються комбінаторними, а методи їх розв’язку – методами комбінаторного аналізу. Оскільки комбінаторика має справу зі скінченими множинами, то її часто називають теорією скінчених множин.
(Для ознайомлення з повним текстом статті необхідно залогінитись)