Методическое пособие по курсу Основы математической лингвистики
 Скачать 418.5 Kb.
| Образовательный портал Как узнать результаты егэ Стихи про летний лагерь 3агадки для детей |
| Методическое пособие по курсу “Основы математической лингвистики”
Пусть требуется выполнить одно за другим какие-либо m действий. Если первое действие можно выполнить  способами, второе действие –  способами и так до m -го действия, которое можно выполнить  способами, то все m действий могут быть выполнены  способами. Это называется правилом произведения. Пусть требуется выполнить одно из каких-либо m действий, взаимно исключающих друг друга. Если первое действие можно выполнить способами, второе действие – способами и так до m -го действия, которое можно выполнить nm способами, то выполнить одно из этих m действий можно  способами. Это называется правилом суммы.Рассмотрим некоторое множество S , состоящее из n различныхэлементов. Пусть  . Назовём множество, состоящее из k элементов, упорядоченным, если каждому элементу этого множества поставлено в соответствие число от 1 до k , причём различным элементам множества соответствуют разные числа.Размещениями из n элементов по k называются упорядоченные подмножества множества S, состоящие из k различных элементов и отличающиеся друг от друга составом элементов или порядком их расположения. Число размещений из n элементов по k равно:  (1.1)Размещениями с повторениями из n элементов по kназываются упорядоченные подмножества множества S , состоящие из k элементов, среди которых могут оказаться одинаковые, и отличающиеся друг от друга составом элементов или порядком их расположения. Число размещений с повторениями из n элементов по k равно:  (1.2)Сочетаниями из n элементов по k называются подмножества множества S, состоящие из k различных элементов и отличающиеся друг от друга только составом элементов. Число сочетаний из n элементов по k равно:  (1.3)Перестановками из n элементов называются размещения из n элементов по n, т. е. упорядоченные подмножества множества S, состоящие из всех элементов данного множества и отличающиеся друг от друга только порядком их расположения. Число перестановок из n элементов равно: P n = n! (1.4) Число перестановок с повторениями из n элементов, в которые первый элемент множества S входит n1 раз, второй элемент – n2 раз и так до m -го элемента, который входит nm раз(n1 + n2 + … + nm = n)равно:  (1.5)Теперь обратимся к примерам комбинаторных задач, связанных с лингвистикой. В примерах на образование слов нужно понимать, что эти слова являются просто сочетанием букв и могут не иметь смысла. Число комбинаций всюду обозначено через N. Элементы множества записываются в любом порядке, и при этом множество не содержит повторяющиеся элементы. Пример 1. Сколькими способами можно выбрать две гласные и одну согласную из множества букв слова “биограф”? Гласные образуют множество: {и, а, о}, а согласные - множество: {б, г, р, ф}. Нам нужно выбрать 2 гласные из 3 и 1 согласную из 4. Поскольку нам не важен порядок выбираемых гласных, то следует найти число сочетаний для согласных и гласных по формуле (1.3), а затем по правилу произведения их перемножить:  Пример 2. Сколькими способами можно выбрать три или четыре различные буквы из множества букв слова “колонна”? Слово содержит только 5 различных букв. Поэтому нужно сложить числа сочетаний, вычисленных по (1.3):  Пример 3. Сколько можно составить двухбуквенных слов из букв слова “скороход”, если буквы этих слов a) не повторяются, b) могут повторяться? Множество содержит 6 различных букв. При составлении слов уже важен порядок букв, поэтому тут используется размещение. a) Это – размещение без повторения (1.1):  b) Это – размещение с повторением (1.2):  Пример 4. Сколькими способами можно переставить буквы в словах “март” и “колобок”? В слове “март” буквы не повторяются, поэтому применим формулу (1.4): N = P4 = 4! = 24 В слове “колобок” трижды повторяется буква “о” и дважды буква “к”. А “л” и “б” встречаются по одному разу. Поэтому здесь используется формула (1.5):  Пример 5. Сколькими способами можно переставить слова во фразе “Мальчик пришёл из школы, сестра была дома”, чтоб её смысл не изменился? Эта фраза делится на две синтагмы, разделённые запятой. В каждой синтагме слова (“из школы” рассматривается как один элемент) можно переставить друг с другом 3!=6 способами (в русском языке порядок слов в целом свободный). Кроме того, можно переставить и сами синтагмы. В итоге, N=3!3!2!=72. Пример 6. Сколькими способами можно переставить слова во фразе “В четверг директор не опоздал на заседание”, чтоб её смысл не изменился? Как и в предыдущей задаче, словосочетания “в четверг” и “на заседание” объединяются в один элемент. Частица “не” может перемещаться по фразе, но при этом изменяется её смысл, например: “В четверг не директор опоздал на заседание”, “Не в четверг директор опоздал на заседание”. Поэтому синтагма “не опоздал” также объединяется в один элемент. Тогда N=4!=24. Примеры для самостоятельного решения. 1.1. Сколькими способами можно выбрать две согласные из множества букв слова “букинист”? 1.2. Сколькими способами можно выбрать две гласные из множества гласных букв слова “гипотенуза”? 1.3. Сколькими способами можно выбрать две гласные и две согласные из множества букв слова “соревнование”? 1.4. Сколькими способами можно выбрать три согласных или две гласных из множества букв слова “библиотека”? 1.5. Сколько можно составить трёхбуквенных слов из множества букв слова “караван”, если буквы этих слов не повторяются? 1.6. Сколько можно составить четырёхбуквенных слов из множества букв слова “сад”, если буквы этих слов могут повторяться? 1.7. Сколько можно составить двухбуквенных слов, состоящих только из гласных или только из согласных букв слова “преобразование”, если буквы этих слов не повторяются? 1.8. Сколькими способами можно переставить буквы в словах “Стамбул” и “Душанбе”? 1.9. Сколькими способами можно переставить буквы в слове “Гаага”? 1.10. Сколькими способами можно переставить буквы в слове “Аддис-Абеба”, не смешивая две части топонима? 1.11. Сколько долгих слогов ((согласный) + краткий гласный + согласный, (согласный) + долгий гласный) можно составить из букв m, n,t, i, o, ā, ū, если допускаются повторения согласных? 1.12. В неогласованном арабском письме не передаются краткие гласные a, i , u. Сколькими способами можно прочесть слово sjd, если известно, что слово не начинается с гласного, сочетание гласных не допускаются, а в начале слова не может быть больше одного согласного? 1.13. Филолог работает над палимпсестом, предполагая два варианта стёршейся письменности и в каждом случае по три варианта чтения для каждой графемы. Сколькими способами можно прочесть стёртую надпись из четырёх графем? 1.14. Согласно закону сингармонизма, в одном (исконном) слове турецкого языка могут находиться гласные только одного из двух рядов: нёбного (e,i,ö,ü) и ненёбного (a,ı,o,u). Сколькими способами можно составить фонетически правильное двухсложное турецкое слово? 1.15. При передаче географических названий на японский язык после согласного, предшествующего другому согласному или стоящего в конце, вставляется u, согласный l передаётся через r. Например, Липецк – Ripetsuku. Установить, сколькими способами можно понять Homurusuku, выделив правильный вариант. 1.16. Из имеющихся 10 иероглифов 2 могут стоять только слева, 5 только справа и 3 с обеих сторон. Сколько сложных слов можно записать с помощью комбинации из двух разных иероглифов? 1.17. В грамматике пять параграфов, причём третий параграф использует данные первого, а четвёртый – данные первых двух. Сколькими способами можно прочесть грамматику, не нарушая логики повествования? 1.18. У существительного 6 значений. Сколькими способами их можно расположить в одной словарной статье? 1.19. У слова 4 именных и 3 глагольных значения. Сколькими способами их можно расположить в одной словарной статье, если именной цикл предшествует глагольному? 1.20. Сколькими способами можно переставить слова во фразе “Он решал пример в комнате, бабушка готовила на кухне, кот спал”, чтоб её смысл не изменился? 1.21. Сколькими способами можно переставить слова во фразе “Ты ручку, наверно, не со стола взял?”, чтоб её смысл изменился? 1.22. Сколькими способами можно переставить слова во фразе “Вернувшаяся домой Маша уже, наверно, спит”, чтоб её смысл и количество запятых не изменились? 1.23. Логаэдом называют строку, содержащую стопы разного типа, следующие в произвольном порядке. Сколькими способами можно составить логаэд из двух ямбических, двух хореических и одной дактилической стопы? 1.24. Сколькими способами можно срифмовать строчки секстины (шестистрочной строфы), произвольно используя три рифмы? 1.25. Сколькими способами можно переставить слова в строчках и сами строчки, чтобы количество слов в строчке не изменилось, и все строчки были срифмованными: “В лесах грибы растут, В морях киты плывут, В речах слова бегут”? 2. Вероятность и информация. Случайное событие, которое невозможно представить как объединение или пересечение более простых событий, называется элементарным событием. Вероятность наступления события p(A) определяется как отношение числа m элементарных событий, благоприятствующих наступлению события, к общему числу n элементарных событий. Эта формула носит название классической вероятности:  (2.1)Событие, противоположное событию А (не-A), обозначается как  . Вероятности исходного и противоположного события связаны формулой: (2.2)Произведением событий AB называется новое событие, состоящее в одновременном появлении событий A и B. Суммой событий A+B называется новое событие, состоящее в появлении либо события A, либо события B, либо обоих этих событий. События называются несовместными, если они не могут произойти одновременно. События образуют полную группу, если они попарно несовместны, а сумма их вероятностей равна 1. Вероятность суммы событий вычисляется так: p (A+B) = p (A) + p (B) – p (AB) (2.3) В случае несовместности событий последнее слагаемое обращается в ноль. События называются независимыми, если вероятность появления одного из них не зависит от появления другого. Вероятность произведения независимых событий равна: p (AB) = p (A) p (B) (2.4) Условная вероятность  означает вероятность события A при условии, что событие B произошло. В случае зависимых событий вероятность произведения равна:p (AB) = p (A) p (B/A) (2.5) Предположим, что событию A предшествуют n взаимно исключающих друг друга гипотез Hi. Вероятности этих гипотез должны удовлетворять равенству  . Тогда полная вероятность события A определяется так:  (2.6)Пусть проводится конечное число n последовательных независимых испытаний, в каждом из которых некоторое событие A может наступить с одинаковой вероятностью p. Вероятность того, что в серии из n независимых испытаний событие A наступит k раз, равно (формула Бернулли):  (2.7)Важной количественной мерой информации является неопределённость. Чем больше исходов опыта, тем выше его неопределённость. В случае одного исхода опыта неопределённость равна 0. Мера неопределённости называется энтропией. Энтропия H опыта связана с числом его исходов S: H = log2 S (2.8) Поскольку знание исхода опыта A полностью снимает его неопределённость, полученная в опыте A информация численно равна энтропии: H (A) = I (A) (2.9) Первая буква синтаксической информации обладает, очевидно, наибольшей неопределённостью, поэтому информация первой буквы – максимальна. Согласно простейшей модели угадывания, информация непрерывно убывает, обращаясь в 0 для последней буквы, которой считается пробел. Это объясняется тем фактом, что чем больше букв слова мы уже знаем, тем легче нам вычислить вероятность появления оставшихся букв. Пример 1. Студент при построении фразы может ошибиться в морфологии с вероятностью 0,6, а в синтаксисе – 0,3. Найти вероятность того, что при переводе фразы студент a) ошибётся в морфологии или в синтаксисе b) ошибётся или в морфологии, или в синтаксисе. c) ошибётся в морфологии и в синтаксисе d) ошибётся в морфологии, но не в синтаксисе. Введём элементарные события: A – “студент ошибётся в морфологии”, B – “студент ошибётся в синтаксисе”. a) Поскольку происходит одно из событий, воспользуемся формулой сложения вероятностей (2.3), отметив, что события совместны – значит, последнее слагаемое не обращается в ноль: p = 0,6 + 0,3 – 0,18 = 0,72. b) Здесь используется та же формула (2.3), но события уже не являются совместными (“или” …, “или” …), и последнее слагаемое исчезает: p = 0,6 + 0,3 = 0,9. c) Здесь происходят оба события, поэтому применяется формула умножения вероятностей (2.4): p = 0,6 · 0,3 = 0,18. d) Вероятность того, что студент не ошибётся в синтаксисе, вычисляется по формуле (2.2), а затем для общей вероятности применяется формула (2.4): p = 0,6 · (1 – 0,3) = 0,42. Пример 2. Дешифровщик обозначил графемы неизвестного слова как ABCDA. Вероятность правильности чтения каждой графемы он оценивает как 0,4. Найти вероятность того, что хотя бы одна из графем прочтена им верно. Пусть событие A – “одна из графем прочтена верно”. Перейдём к противоположному событию – “ни одна из графем не прочтена верно”. Это – вероятность произведений противоположных событий. По формуле (2.4)  . Тогда по формуле (2.2) получаем:  .Пример 3. Впростом слове, не содержащем инфиксов или трансфиксов, 8 букв. Найти вероятность того, что длина корня – три буквы. Поскольку в слове отсутствуют инфиксы или трансфиксы, буквы корня идут подряд. Значит, они могут занимать позиции в слове 123, 234…678. Таких вариантов 6. Теперь вычислим комбинации, при которых число букв корня меняется от 1 до 8. Если в корне 1 буква, то у неё 8 вариантов расположения: 1, 2, 3…8. Если в корне 2 буквы, то 7 вариантов: 12, 23, 34…78. Таким образом, найдём искомую вероятность по формуле (2.1):  .Пример 4. Во фразе 8 знаменательных слов: 2 глагола, 3 существительных и 3 прилагательных. Этимология глаголов филологу известна точно, этимология существительных с вероятностью 0,8, а этимология прилагательных – с вероятностью 0,7. Найти вероятность того, что филолог правильно определит этимологию любого слова из фразы. Введём гипотезы: H1 – “слово является глаголом”, H2 – “слово является существительным”, H3– “слово является прилагательным”. Вычислим их вероятности: p(H1) = 2/8 = 1/4 , p(H2) = p(H3) = 3/8. Событие A – “филолог правильно определит этимологию слова”. Условные вероятности: p(A/H1) = 1, p(A/H2) = 0,8, p(A/H3) = 0,7. Тогда по формуле (2.6) получается: p(A) = p(A/H1) p(H1) + p(A/H2) p(H2) + p(A/H3) p(H3) = 1/4 + 3/8 * (0,8 + 0,7) = 0, 8125. Пример 5. Информант, носитель одного из диалектов, правильно переводит фразу на литературный язык с вероятностью 0,7. Найти вероятность того, что двое из пяти информантов правильно переведут фразу на литературный язык. Применяем формулу Бернулли (p = 0,7, k=2, n=5).  Пример 6. Имеется трёхсловное предложение, каждое из слов которого выбирается из нескольких вариантов. Например, “Дима (Никита) любит (уважает) Катю (Надю, Свету, Алину)”. Найти энтропию фразы. Энтропия фразы складывается из энтропий её слов. Для первых двух слов существует 2 варианта, а для третьего четыре, поэтому H = H1 + H2 + H3 = log2 2 + log2 2 + log2 4 = log2 16 = 4. Пример 7. Найти синтаксическую информацию трёх последних значимых букв слова “филология”. Мы уже знаем первые шесть букв слова, и нам нужно угадать три последних буквы (самой последней буквой считается пробел, его мы здесь не учитываем). После “филоло-“ может стоять только буква г, поэтому I (г) = H (г) = log21 = 0. Для предпоследней буквы имеется 5 вариантов: и, а, у, о, е. Эти варианты мы для простоты считаем равнозначными. Поэтому I (и) = H (и) = log25. Для последней же буквы – 3 варианта: я, и, ч. I (я) = H (я) = log23. Примеры для самостоятельного решения. 2.1. Даны события: A – “в языке есть категория рода”, B – “в языке есть категория падежа”. Исследовать на совместность пары событий: A и B, и B, A и .2.2. К прошедшим временам английского языка относятся A – “Past Indefenite”, B – “Past Perfect”. Указать события, дополняющие A и B до полной группы событий. 2.3. Даны события: A – “слово стоит в единственном числе”, B – “слово стоит во множественном числе”, C – “слово стоит в родительном падеже”. Исследовать события A, B, C на попарную независимость. 2.4. Парень решил послать своей девушке поздравления на 8 языках, три из которых используют латиницу, два – кириллицу, а остальные письменности обоим незнакомы. Найти вероятность того, что первое письмо поздравления, увиденное девушкой, ей незнакомо. 2.5. Впростом слове, не содержащем префиксы, инфиксы или трансфиксы, 10 букв. Найти вероятность того, что корень слова состоит из пяти букв. 2.6. В простом слове, содержащем префикс, инфикс и суффикс, 7 букв. Найти вероятность того, что префикс и суффикс содержат одинаковое число букв. 2.7. В сложном двухкорневом слове, не содержащем префиксы, инфиксы, трансфиксы и интерфикс, 8 букв. Найти вероятность того, что в нём два суффикса, если в каждом корне не меньше 2 букв, а суффиксов не больше 2. 2.8. Для образования пятибуквенного слова может использоваться шесть букв. Найти вероятность того, что образованное слово – палиндром, соседние буквы которого не совпадают. 2.9. Студент может правильно прочесть фразу с вероятностью 0,6, а перевести её с вероятностью 0,4. Найти вероятность того, что студент a) правильно прочтёт и переведёт фразу, b) правильно прочтёт или переведёт фразу, с) неверно прочтёт и неверно переведёт фразу, d) или неправильно прочтёт, или правильно переведёт фразу. 2.10. Двенадцать слов языка равномерно распределены по трём семантическим полям. Найти вероятность того, что взятые из них наугад три слова относятся к одному семантическому полю. 2.11. Студент, разбирая сирийскую глагольную словоформу, пытается определить лицо, число и породу. Найти вероятность того, что он определит правильно два глагольных аспекта, если он правильно определяет лицо с вероятностью 0,6, число – с вероятностью 0,8, а породу – с вероятностью 0,4. 2.12. Студент может правильно транслитерировать египетскую фразу с вероятностью 0,6. Найти вероятность того, что студенту удастся правильно транслитерировать египетскую фразу только с четвёртой попытки. 2.13. Филолог пытается установить связь между четырьмя малоизученными языками, оценивая родство для каждой пары языков с вероятностью 0,2. Найти вероятность того, что хотя бы одна из гипотез филолога верна. 2.14. Существует 8 ритмических форм четырёхстопного ямба. Найти вероятность того, что в ямбическом катрене (строфе из 4 строк) все ямбы относятся к разным ритмическим формам. 2.15. Каждый из трёх амфибрахических катренов содержит по одной строке с метрическим нарушением. Найти вероятность того, что все эти строки занимают одинаковую позицию в строфе. 2.16. Индолог для поиска незнакомого санскритского слова в два раза чаще берёт словарь Монье-Уильямса, чем словарь Кочергиной. Вероятность найти слово для словаря Монье-Уильямса равна 0,9, а для словаря Кочергиной – 0,7. Найти вероятность того, что незнакомое слово будет найдено. 2.17. Студенту на экзамене с равной вероятностью может попасться один из 4 вопросов по грамматике хауса. На первый из них студент может правильно ответить с вероятностью 0,5, на второй – с вероятностью 0,6, на третий – с вероятностью 0,7, на четвёртый – с вероятностью 0,3. Найти вероятность того, что студент неверно ответит на попавшийся ему вопрос. 2.18. Филолог, владеющий ивритом, пытается понять арамейскую фразу, состоящую из пяти слов. Вероятность понять арамейское слово для него равна 0,8. Найти вероятность того, что он поймёт больше половины слов. 2.19. Студенту при переводе текста встретилось четыре слова, каждое из которых обладает двумя различными значениями. Найти вероятность того, что студент правильно переведёт хотя бы одно из этих слов. 2.20. Найти энтропию фразы: “В понедельник (вторник, пятницу, субботу) на первую (вторую, третью, четвёртую) пару опоздают (придут вовремя) пять (шесть, семь, восемь) студентов”. 2.21. В сборнике 5 пьес, которые можно прочесть в произвольном порядке. Найти энтропию числа способов прочтения пьес. 2.22. Из шести слов можно составить двухсловные синтагмы. Найти энтропию числа способов образования синтагм. 2.23. Найти синтаксическую информацию двух последних значимых букв слова “светлый”. 2.24. Определить буквы с нулевой синтаксической информацией слова “кенгуру”. 2.25. Найти синтаксическую информацию интерфикса и первой буквы второго корня слова “соковарка”.  перейти в каталог файлов | Образовательный портал Как узнать результаты егэ Стихи про летний лагерь 3агадки для детей |