Блоґ одного кібера

Історія хвороби контуженого інформаційним вибухом

Vim і конспекти

with 14 comments

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

Сьогодні на лекції з ТП як завжди підключав проектор, але презентацію показували з ноутбука Стружа[1]. Тому мій ноутбук виявився незайнятим, і включеним в резетку. Волею випадку було відкрито робоче середовище:

Процес конспектування

Процес конспектування



І мені в голову прийшла ідея спробувати писати конспект зразу в електронному виді. І зразу цю ідею і почав втілювати написавши :r !date. Ця до геніального проста могутність Vim просто причаровує.

Текстові файли мають деякі обмеження стововно паперу, але як каже теорія текст дозволяє записати будь-яку мову. Треба лише правильно підібрати граматику. Граматика в мене була дуже нечітка. Конспект писався в дивному псевдокоді, який дуже віддалено нагадує вікірозмітку, LaTeX, і C. 🙂

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

== Лекція з ТП ==

== Лекція з ТП == понеділок, 26 жовтня 2009 08:41:14 +0200

=== Властивості контекстно-вільних мов === Ми вивчаємо їх тому, що вони близькі
до БНФ.

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

Дві складові - теоретико множинна (функціональна), та (інтенціональна).

Які властивоті можна досліджувати для граматик?  Еквівалентність. 

Лема (Про перейменування нетерміналів) Якщо ми візмемо іншу множину
нетерміналів, яка має бієкцію з нашою, то нова граматика буде еквівалентною.

В деяких випадках контекстно-вільна граматика може містити символи та правила,
що не вживаються для виводу термінальних ланцюжків.

Приклад: Маємо граматику G=({S,A,B},{a,b,c},P,S), де P={S->a,S->cS,A->b},
нетермінал A, і термінал Б, не можуть з'являтись у жодному ланцюжку виведення.
Тaким чином ці символи не приймають участь у породженні мови, і можуть бути
видалені без зміни мови яка виводиться.

Щоб знайти недосяжні нетермінали спочатку визначимо досяжні нетермінали. Ця
множина легко визначається за допомогою індуктивних визначень: #R_0={S}
#R_i={B|є правило A->\alpha B \ b\in P, що A \in R_{i-1}, B \in N} \cup R_{i-1}
i \in N

Наприклад: S->a S->A A->AB B->b C->c

Досяжні: S, A, B. 

Таким чином недосяжне тільки C, і його можна видалити.

#define Непродуктивний нетермінал (тупіковий) якщо з нього не можна вивести
жодного термінального ланцюжка.

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

C, B, S.  Непродуктивне тільки A.

Видаляємо всі непродуктивні і недосяжні. І так кілька разів, бо після того як ми
видалимо непродуктивні можуть з'явитись нові недосяжні. З попереднього прикладу
зробиться граматика S->a , і вона еквівалентна прикладу.

#define \epsilon -правила - це правила виду A->\epsilon

Лема: За кожною граматикою можна побудувати еквівалентну їй без епсілон-правил. 

ПРиклад: S->aSb S->bSa S->\epsilon

перетворюється в

S->aSb S->bSa S->ab S->ba

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

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

#define КВ-граматика називається граматикою у '''Нормальній формі Хомського''',
якщо її правила мають вигляд S->\epsilon, A->a, A->BC для деяких A,B,C \in N, a
\in T.

Лема: За кожною граматикою можна побудувати еквівалентну їй граматику у
нормальній формі Хомського.





Перерва: понеділок, 26 жовтня 2009 09:32:26 +0200




Метод перетворення граматики в нормальну форму Хомського !не зрозумів S->ASA
S->aSb S->bSa A->a

перетворюємо:

S->ASA S->DSB

#define Нормальна форма Грейбах Її правила мають вигляд: A->a\alpha (тобто кожне
правило починається з термінального символу).

Шейла Грейбах - американська дослідниця.

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

#define Рекурсивний нетермінал (самовставний, циклічний) якщо існує вивід виду
A=>*\alpha A \beta Інакше нетермінал нерекурсивний.

Якщо мова нескінченна то в граматиці є рекурсивний нетермінал. І навпаки, якщо
мова скінченна, то її граматика не містить рекурсивних нетерміналів. 

#define Регулярне слово wtf?

Лема про накачку.  ... Дивитись слайди про синтактику

=== Операції над формальними мовами ===

Лема Мова L3={a^nb^nc^n|n\geq 0} не є контекстно вільною.  #proof Методом від
супротивного. Якби мова L3 була б КВ-мовою, то тоді існували б ланцюжки
ut_1^ixt_2^iv \in L3 \forall i=0,1,\ldots . (А з чого це взяли?) Зрозуміло, що
t_1 (як і t_2) не може складатися з різних символів ( інакше для деякого i
ланцюжок ut_1^ixt_2^iv не буде належати L3. Але якщо t_1 складається лише з
одного символу, то збільшуючи i можна порушити баланс символів a,b,c.
Протиріччя.

Яка теоретико множинна-операція виводить нас з класу рекурсивно-перелічних
множин?  Доповнення. Тищенко rulez!

за чиїмись підрахунками дзвоник

понеділок, 26 жовтня 2009 10:14:36 +0200

Мораль

Що нам каже цей експеримент? Що писати електронні конспекти можна! Звісно не завадив би такий корисний міфічний девайс як світлове перо, але ж можна тримати збоку зошит для ілюстрацій. А швидкість друку, і швидкість письма, ще варто порівняти. Чим я можливо трохи пізніше займусь.

Що можна вдосконалити в написанні конспекту? Варто згадати, що Vim – шустрий редактор, і має купу фіч типу :abbreviate НТ нетермінал, макросів, і підсвітки.

Можна розробити мову для коспектів семантично схожу на XML а синтаксично на LaTeX та wiki, і написати модуль підсвітки, і команд для цієї мови. А також транслятори в чистий LaTeX, wiki-розмітку та XHTML.

Примітки

  1. Бачте формат презентації був pptx, а в Стружа Windows 7, і офіс нової версії. Це новий формат, який базується на XML (Microsoft підтягується за OpenOffice). Хоча OpenOffice мав би вміти відкривати такі презентації, але є малелька проблема з Microsoft Office. Microsoft не дотримується стандартів Юнікоду, і тому деякі математичні символи закодовує неправильно. Через це його документи несумісні з світом. А це все я веду до того, що хоча Microsoft Office комусь може здаватись зручним, але він неймовірно невідповідає світовим стандартам. Принаймі так мені пояснив Улідтко, а він мало не член консорціуму. Чекаю на холівар.
  2. Advertisements

Written by bunyk

Жовтень 26, 2009 at 15:01

Відповідей: 14

Subscribe to comments with RSS.

  1. Ну, ідея звісно не нова…
    max@ulidtko:~$ cd Документи/конспекти/
    max@ulidtko:~/Документи/конспекти$ ls
    БД конспект 12 жов.odt СРП конспект семінар 14 жов.odt ТІ конспект.odt ЧМ 8 жов.odt
    БД конспект 12 жов query 1.sql ТІ конспект 6 жов.odt ТП 8 жов.odt

    І порівнював я швидкість писання літер ручкою і клавіатурою ще, здається, в третьому семестрі. Різниця була мало не в 5 разів, наскільки можу пригадати (щоб не було сумнівів: так, перевага в сторону клавіатури). Але коли справа доходить до формул, швидкість стає приблизно такою ж, як і у Кашпур по дошці 🙂 І це в OpenOffice’і.

    >Що нам каже цей експеримент? Що писати електронні конспекти можна!
    Тут згоден стовідсотково.

    Щодо MS офісу і юнікоду… 🙂 Ні, Бунику, там не зовсім так 🙂 _Моя здогадка_ щодо того, чому опен офіс показує не всі символи у формулах, наступна: MS офіс створює для поточного документа новий шрифт; в цьому шрифті на місця E000-F8FF (так звана приватна зона юнікоду; стандарт тут, фактично, не порушений) ставляться нові символи малюночки символів (glyphs); і по всьому документу до цих малюночків звертаються по їх кодам, як і характерно взагалі для використання шрифтів. Наприклад, на місце U+E000 MS офіс може поставити малюночок, схожий на маленьку грецьку літеру дельта в шрифті serif, нахилену (italic); на місце U+E001 — маленьку грецьку літеру дельта в шрифті sans-serif, жирну (bold). І далі по всьому тексту ставить символи U+E000 і U+E001, форматуючи їх як маючими шрифт: , і посилаючись таким чином до потрібних гліфів. Зрозуміло, що новостворений шрифт повинен бути якимось чином вкорінений (embedded) в документ, і збережений в тому ж самому .doc[x] файлі. А от OpenOffice.org же чомусь не в змозі такі шрифти звідти виймати (хехе, «чомусь»). В результаті ми маємо все ті ж символи U+E000, U+E001, але в звичайному, не кастомному шрифті. А в звичайних шрифтах на тих місцях стоять placeholder’и — квадратики (до речі, тест: U+E000 – “”, U+E001 – “”). Ось така тут, на мою думку, ситуація. Мораль — для read-only документообігу використовувати PDF.

    ulidtko

    Жовтень 26, 2009 at 17:21

    • ну що таке 😦 Де все, що я писав у кутових дужках? Де мій попередній перегляд? 😦

      ulidtko

      Жовтень 26, 2009 at 17:24

      • Листа в Automattic я ще не написав, тому попереднього перегляду поки що не буде.

        bunyk

        Жовтень 26, 2009 at 17:53

  2. 1. Ідея нова для української освіти загалом. Те що ти оцифровував конспекти ще до мене, я пам’ятаю 🙂

    (23:55:14) Улідтко: зараз на черзі Убунту та мої вересневі конспекти-на-листочках
    (23:55:31) bunyk: врозумінні?
    (23:55:49) Улідтко: ну, я їх планую повністю оцифрувати

    2. Ну, різних людей швидкість письма різна. Як впринципі і друку. В мене ~40 wpm = 200 cpm, за даними http://play.typeracer.com/ . А в когось 137 wpm. Правда в Vim цю швидкість можна трохи збільшувати для специфічних задач, за допомогою абревіатур, макросів, і призначенню функцій певним клавішам. Деякі задроти Vim навіть призначують функцію переходу в звичайний режим кнопці Caps lock бо вона ближче до мізинця лівої руки. Хотів би я побачити як працюють люди з швидкістю 130 wpm в налаштованому під них Vim. Як вони взагалі тоді встигатимуть думати?

    3. Дякую за детальне пояснення проблеми сумісності. Я правда поки що залишаюсь прихильником алфавіту з 256 символів, і різноманітних мов розміток. І хоча це схоже на кодування на ассемблері, але мені подобається. Комп’ютер розуміє текст, і я його розумію. Перекладач не потрібен, і сумісність майже ідеальна.

    bunyk

    Жовтень 26, 2009 at 18:11

    • 3. дивно, хто взагалі придумав ці бінарні формати текстів %)

      ulidtko

      Жовтень 26, 2009 at 18:29

      • Ну, бінарні файли таки компактніші, і доступ до них швидший. Але це проблема для древнього заліза.

        bunyk

        Жовтень 26, 2009 at 19:30

  3. Ах, згадав. Ну, так може купимо метрів 15 переноски?

    bunyk

    Жовтень 26, 2009 at 22:04

    • блін, точно. Купимо прямо завтра

      ulidtko

      Жовтень 26, 2009 at 22:41

  4. хмм.. тарас, ти будеш продовжувати писати конспекти в ел форматі, чи це був одиничний експеримент?

    danbst

    Жовтень 26, 2009 at 22:26

    • Біда в тому, що в мене дуже слабкий акумулятор, і зараз найбільше на що спроможний – це виконувати функції UPS. Але над проблемою використарння комп’ютерів в навчанні я працюю вже більше півроку, і буду продовжувати. В мене оце щойно почала збільшуватись впертість.

      Подивись що написано на правому полі внизу (вгорі відносно цього коментаря).

      bunyk

      Жовтень 26, 2009 at 22:38

  5. […] Vim і конспекти […]


Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: