Tuesday, September 30, 2014

Ավարտական աշխատանքի տեքստի ձևավորումը

Վաղուց ես ուզում էի գրել այս թեմայով և ներկայացնել տարիների ընթացքում իմ կուտակած փորձն ու դիտարկումների արդյունքները։ Բայց ստացվեց այնպես, որ վերջերս ես ավելի հաճախ սկսեցի հանդիպել անփույթ ձևավորված տեքստերի, և ավելի հաճախ սկսեցի հարցեր ստանալ այն մասին, թե ինչպես ավարտական կամ կուրսային աշխատանքի փաստաթուղթը կազմելիս ստանալ այս կամ այն արդյունքը։ Օրինակ, ինչպե՛ս ձևավորել գեղեցիկ ու ճիշտ տիտղոսաթերթ, ինչպե՛ս կազմել և որտե՛ղ տեղադրել բովանդակության ցանկը, ինչպե՛ս փաստաթղթում ներդնել պատկերներ, աղյուսակներ, ինչպե՛ս կազմել գրականության (կամ աղբյուրների) ցանկը և հղումներ կատարել դրա տարրերին, ինչպե՛ս և ի՛նչ տեսքով ներկայացնել ծրագրավորման լեզուների տեքստը և այլն, և այլն։ Այս և շատ այլ հարցերի մասին եմ ես պատմում իմ գրառման մեջ՝ որպես աշխատանքային գործիք օգտագործելով TeX հրատարակչական համակարգի համար ստեղծված LaTeX մակրոսների փաթեթը։
Ամեն ինչ գրելիս ես ենթադրում եմ հայերեն տեքստերը, հետևաբար ենթադրում եմ նաև, որ ձեռագիրը պատրաստված է Unicode (ավելի կոնկրետ՝ UTF-8) կոդավորմամբ, և օգտագործվում է LaTeX-ի xetex իրականացման xelatex ծրագիրը։

Փաստաթղթի մակետի ընտրություն

Մակետ (LaTeX-ում ասում են document class) ասելով հասկացվում է փաստաթղթի ընդհանուր հատկությունների ամբողջությունը։ Օրինակ, լուսանցքների չափը, վերնագրերի ձևավորումը, ցանկերի կազմակերպումը, ոչ-տեքստային օբյեկտների տեղադրումը և այլն։ Ստանդարտ LaTeX փաթեթում առավել հաճախ օգտագործվում են չորս հիմնական մակետներ. letter, որ նախատեսված է նամակների համար, article՝ հոդվածների պատրաստման համար, report` ավելի ընդարձակ հոդվածների, փոքր գրքերի, ատենախոսությունների համար, book` լիարժեք գրքերի համար։

Ուսանողական ավարտական (կամ մագիստրոսական) աշխատանքի տեքստի պատրաստման համար ամենահարմարը report մակետն է: Սա հնարավորություն է տալիս \chapter, \section, \subsection այլ նմանատիպ մակրոսներով փաստաթուղթը բաժանել գլուխների, բաժինների ենթաբաժինների և այլ տրամաբանական մասերի։ Մակետի ընտրությունը կատարվում է LaTeX ձեռագրի \documentclass մակրոսով։
\documentclass[a4paper,11pt]{report}
Քառակուսի փակագծերում նշված a4paper պարամետրով նշված է, որ փաստաթուղթը կառուցելիս պետք է նկատի ունենալ A4 ստանդարտի տպագրական թուղթը, իսկ 11pt պարամետրն ասում է, որ տեքստի հիմնական տպատառի չափը 11 է և օգտագործվող մյուս բոլոր տառերի չափն ընտրվելու է 11 չափի հարաբերությամբ։

Լռելությամբ report մակետում ընդունված է լուսանցքների այնպիսի չափ, որ տեքստի համար մնացած տարածում, հաշվի առնելով ընթեռնելիության որոշ հարցեր, մեկ տողը պարունակի 60-70 տառ (նիշ)։ Բայց մեզ մոտ ընդունված չէ այդպիսի լայն լուսանցքներ։ Սովորաբար ընտրվում է (և աչքի համար էլ հաճելի է) ձախից և ներքևից 3 սմ, իսկ աջից և վերևից՝ 2 սմ լուսանցքներ։ Այս կարգավորումներն անելու համար կարելի է օգտագործել geometry փաթեթը՝ \usepackage հրամանի պարամերտրերում տալով լուսանցքների նախընտրելի չափերը։
\usepackage[top=2cm,bottom=3cm,left=3cm,right=2cm]{geometry}

Տպատառերի (կամ տառատեսակների) ընտրություն

Քանի որ մեր բուհերում ավարտական աշխատանքների պաշտպանության ներկայացվող տեքստերը պատրաստվում են հիմնականում հայերենով, ապա ես ուզում եմ հղում կատարել իմ բլոգի մեկ այլ գրառման՝ Հայերեն LaTeX, որտեղ ես մանրամասն պատմում եմ, թե ինչպես LaTeX-ն օգտագործել հայերեն փաստաթղթեր պատրաստելու համար։ Այդտեղ պատմում եմ նաև տպատառերի ընտրության մասին։

Տիտղոսաթերթի պատրաստումը

Տարիների ընթացքում ստացվել է այնպես, որ մեր բուհերում ներկայացվող ավարտական կամ կուրսային աշխատանքների տիտղոսաթերթերն ունեն մի ընդհանուր սխեմա՝ երբեմն այս կամ այն մանր փոփոխություններով։ Ստորև իմ մագիստրոսական աշխատանքի տիտղոսաթերթի նկարն է.
Չեմ պնդում, որ սա անթերի և օրինակելի սխեմա է, բայց այն ընդունելի է շատերի կողմից, իսկ ինձ արված միակ դիտողությունն այն էր, թե էջի վերևում «Երևանի Պետական Համալսարան» ու «Տեղեկատվական Տեխնոլոգիաների Կրթական և Հետազոտական Կենտրոն» արտահայտություններում պետք չէ բոլոր բառերը սկսել մեծատառերով։

LaTeX կոդը, որով ես կառուցել եմ այս տիտղոսաթերթը, այնքան պարզ է, որ նույնիսկ մեկնաբանությունների կարիք չկա։ Ստորև ներկայացնում եմ այն.
% titlepage միջավայրը սկսում է նոր մաքուր էջ, որի վրա բացակայում է էջի համարը
\begin{titlepage}

\begin{centering}
\LARGE{Երևանի \ Պետական \ Համալսարան}\\
\Large{Տեղեկատվական Տեխնոլոգիաների Կրթական և Հետազոտական Կենտրոն}\par
\vskip6cm
\textbf{\Huge{ԱՎԱՐՏԱԿԱՆ~~ԱՇԽԱՏԱՆՔ}}\par
\end{centering}

\null\smallskip\null

\begin{centering}
\begin{tabular}{rl}
\textbf{Թեմա:}    & \textit{Բովանդակությամբ հասցեավորվող հիշող սարքերը}\\
                   & \textit{տեստավորող ալգորիթմների կառուցում} \\[4pt]
\textbf{ՈՒսանող:} & \textit{Արմեն Բադալյան} \\[4pt]
\textbf{Ղեկավար:} & տ.~գ.~թ.~\textit{Գուրգեն Հարությունյան} \\
\end{tabular}
\par
\end{centering}

\null\vfill\null

\begin{centering}
Երևան - 2011\par
\end{centering}

\end{titlepage}

Տեքստի տրամաբանական տրոհում

report մակետում տեքստի տրամաբանական տրոհման ամենամեծ միավորը «գլուխ»-ն է, որ սկսվում է \chapter մակրոսով։ Բացի այն, որ \chapter մակրոսը վերնագիրը ձևավորում է տվյալ պահին որոշված ոճով, այն նաև մեկով ավելացնում է գլուխների հաշվիչի արժեքը։ Օրինակ,
\chapter{Ծրագրի ընդհանուր նկարագրություն}
Հաջորդ տրամաբանական միավորները «բաժին», «ենթաբաժին» և «ենթա-ենթաբաժին»-ն են, որ սկսվում են համապատասխանաբար \section, \subsection և \subsubsection մակրոսներով։ Այդ միավորներից ամեն մեկն ունի իր հաշվիչը, որոնց արժեքը ավելանում է համապատասխան մակրոսի կիրառմամբ, իսկ այդ հաշվիչների արժեքն արտածվում է վերնագրի մեջ։ Օրինակ, իմ աշխատանքի երրորդ գլուխն ուներ հետևյալ տեքստը.
Տեքստի տրամաբանական տրոհման հրամանները տեղեկություններ են հավաքում նաև բովանդակության ցանկն արտածող \tableofcontents հրամանի համար։ Սովորաբար բովանդակության ցանկը տեղադրում են տիտղոսաթերթից հետո։
    Եթե փաստաթուղթը հավելվածներ է պարունակում, ապա ձեռագրի համապատասխան տեղում պետք է ավելացնել \appendix մակրոսը։ Այդ կետից սկսած գլուխների վերնագրերը կսկսվեն «Հավելված» (կամ «Appendix») բառով և կհամարակալվեն լատինական այբուբենի տառերով։ Օրինակ այսպես.

Պատկերների տեղադրում

LaTeX-ը հնարավորություն է տալիս փաստաթղթում ներդնել (համարյա) կամայական ֆորմատի պատկերներ (նկարներ). PNG, JPEG, EPS և այլն։ Նախ հարկավոր է կցել graphicx փաթեթը.
\usepackage{graphicx}
Հետո, տեքստի այն տեղում, որտեղ պետք է ներդրվի նկարը, \includegraphics մակրոսով նշվում է նկարի ֆայլի անունը։ Օրինակ, camcell.png նկարը 0.85 մասշտաբով ներդնելու համար պետք է գրել.
\includegraphics[scale=.85]{camcells.png}
LaTeX-ում նախատեսված են այսպես կոչված «սահող» (floating) միջավայրեր։ Դրանք նախատեսված են պարունակել օբյեկտներ, որոնք ամբողջությամբ պետք է տեղավորվեն մեկ էջի վրա, ինչպես նաև թույլ են տալիս այդ օբյեկտների համար սահմանել վերնագրեր ու խաչաձև հղումների նշիչներ (labels)։ Նկարները տեքստում տեղադրվում են figure սահող միջավայրի օգնությամբ։ Օրինակ,
\begin{figure}[h]
\centering
\includegraphics[scale=.85]{camcells.png}
\caption{\textsf{SRAM}, \textsf{BCAM} բջիջներ։}
\label{fig:cells}
\end{figure}
Ձեռագրի այս հատվածն ասում է, որ 0.85 մասշտաբով ներդրվում է camcells.png նկարը, որի ներքևում գրվելու է «SRAM, BCAM բջիջներ։» վերնագիրը (\caption), իսկ խաչաձև հղումների համար օգտագործվելու է fig:cells նշիչը (\label)։ Իսկ \centering մակրոսի կիրառումը նշում է, որ նկարը հորիզոնական ուղղությամբ պետք է կենտրոնադրվի։
    \begin{figure} տողի պոչից գրված [h] պարամետրը ցույց է տալիս, որ նկարը պետք է տեղադրվի հենց ճիշտ այն տեղում, որտեղ ձեռագրում հանդիպում է figure միջավայրը։ Բացի «h» (here) տառից, կարելի է տալ, օրինակ, նաև «t» (top) և «b» (bottom) տառերը։ Դրանցից առաջինն ասում է, թե նկարը պետք է միշտ տեղադրել (սահեցնել) էջի վերևում, իսկ երկրորդը՝ էջի ներքևում։ Ինչքան գիտեմ, լռելությամբ միացված է «t» պարամետրը (նկարները սահում են էջի վերին մասը)։ Օրինակ, հետևյալ երկու նկարներից առաջինում նկարը տեղադրելիս figure միջավայրին տրված է «h» տեղադրման պարամետրը, իսկ երկրորդում ոչինչ տված չէ։

Գրականության ցանկ և հղումներ

Փաստաթղթի կարևոր բաղադրիչներից է գեղեցիկ կառուցված գրականության ցանկը։ Բարեբախտաբար LaTeX համակարգի համար ստեղծվել է BibTeX գործիքը, որը հնարավորություն է տալիս ստանդարտ և, որ ավելի կարևոր է, պարզ գրառմամբ թվարկել աշխատանքում օգտագործված (կամ օգտագործվելիք) աղբյուրները։ Օրինակ, իմ մագիստրոսական աշխատանքի համար ես պատրաստել էի մի BibTeX ֆայլ (thesisbiblio.bib), որի պարունակության մի մասը այսպիսինն էր.
@article{hgsvz,
    author = "Grigoryan H. and Harutyunyan G. and Shoukourian S. and Vardanian V. and Zorian Y.",
    title = "Generic BIST Architecture for Testing of Content Addressable Memories",
    note = "IEEE International on-line testing symposium",
    year = "2011"
}

@article{art1,
    author="W. K. Al-Assadi and A. P. Jayasumana and Y. K. Malaiya",
    title="On fault modeling and testing of content-addressable Memories",
    journel="IEEE International Workshop on Memory Technology, Design and Testing",
    year=1994
}

@article{art2,
    author="J. Zhao and S. Irrinki and M. Puri and F. Lombardi",
    title="Testing SRAM-Based Content Addressable Memories",
    journal="IEEE Transactions on Computers",
    year=2000
} 
 
@article{art3,
    author="Zh. Xuemei and Y. Yizheng and Ch. Chunxu",
    title="Tests for Word Oriented Content Addressable Memories",
    journal="Asian Test Symposium",
    year=2002
}
Այստեղ BibTeX լեզվով նկարագրված են երեք հոդվածներ (@article), որոնց տրված են համապատասխանաբար hgsvz, art1, art2 և art3 նշիչները։ BibTeX ֆայլում թվարկված գրառումներին LaTeX ձեռագրում հղում են անուն հենց այս նշիչներով։ Հղումները կարող են լինել երկու տեսակի. \cite և \nocite մարոսներով։ Առաջինի օգտագործման դեպքում հղված տարրի համարն արտածվում է հղման կետում, իսկ երկրորդի դեպքում՝ ոչ։ \nocite մակրոսն օգտագործում եմ այն դեպքում, երբ ուզում եմ գրականության ցանկին տարր ավելացնել, բայց այդ տարրը չհիշատակել աշխատանքի տեքստում։ Օրինակ, իմ աշխատանքի առաջին գլխի առաջին նախադասությունը ձեռագրում ունի հետևյալ տեսքը, որտեղ \cite մակրոսով հղում եմ կատարել hgsvz նշիչն ունեցող հոդվածին։
Բովանդակությամբ հասցեավորվող հիշող սարքերը \cite{hgsvz} 
(\textsf{Content Addressable Memory} – \CAM) դրանք հիշող 
սարքերի մի հատուկ տեսակ են, որոնք օգտագործվում են որոնման 
մեծ արագություն պահանջող ապարատային կիրառություններում:
Փաստաթղթի այն տեղում, որտեղ ուզում եմ, որ հայտնվի գրականության ցանկը (սովորաբար գրականության ցանկը տեղադրում են վերջում), գրում եմ հետևյալ տողերը.
\bibliographystyle{plain}
\bibliography{thesisbiblio}  
Սրանցից առաջինն ասում է, որ փաստաթղթում պետք է տեղադրել plain ոճի (այդ ոճերի մասին առաայժմ չընդարձակավեմ) գրականության ցանկ, իսկ երկրորդը նշում է .bib ֆայլի անունը։
    Առաջին անգամ ձեռագիրը կոմպիլյացնելուց հետո .aux ֆայլում գրառումներ են կատարվում գրականության հղումների մասին։ Այնուհետև պետք է աշխատեցնել bibtex ծրագիրը՝ արգումենտում տալով .aux ֆայլը, որը գեներացնում է միայն ձեռագրում հիշատակված աղբյուրները պարունակող .bbl ֆայլը։ Եվ հետո նորից պետք է կոմպիլյացնել ձեռագիրը, որպեսզի փաստաթղթում ավելանա գրականության ցանկը, իսկ այն կետերում, որտեղ կատարվել են հղումները, ավելացվեն համապատասխան համարները։ Հրամանների տիպիկ հաջորդականությունը կարող է ունենալ հետևյալ տեսքը, որտեղ m0.tex-ն ձեռագրի ֆայլն է։
$ xelatex m0.tex
$ bibtex m0.aux
$ xelatex m0.tex

Ծրագրերի կոդի ներկայացումը

Երբեմն անհրաժեշտություն է առաջանում փաստաթղթում ունենալ մի որևէ ծրագրավորման լեզվով գրված տեքստ։ Ստանդարտ LaTeX-ի verbatim միջավայրը իր պարունակությունն արտածում է առանց ֆորմատավորման. այնպես, ինչպես գրված է ձեռագրում։ Բայց այդ, fancyvrb փաթեթը տրամադրում է Verbatim միջավայրը, որը հնարավորություն է տալիս անփոփոխ արտածվող տեքստն արտածել լրացուցիչ ատրիբուտներով, տողերի համարներ, շրջանակ, տառատեսակի փոփոխություն և այլն։

Ամփոփում

Առայժմ այսքանը աշխատանքների ձևավորման մասին։ Կրկնեմ նորից, որ ոճական տեսկետից ես ներկայացնում եմ միայն իմ սեփական կարծիքը։ LaTeX-ը թույլ է տալիս կամայական փոփոխություններ կատարել և վերջնական փաստաթուղթը հարմարեցնել նույնիսկ ամենաքմահաճ պահանջներին։

Thursday, September 18, 2014

C++: Ֆունկցիա

Մաթեմատիկական մեկնաբանությամբ ֆունկցիան մի գործողություն է, որը մի բազմությունը՝ որոշման տիրույթը, արտապատկերում է մեկ այլ բազմության՝ արժեքների տիրույթին։ C++ լեզվում նույնպես այդպես է․ ֆունկցիան ստանում է արգումենտներ և վերադարձնում է արժեք։ Բայց նաև, ծրագրավորման գործի առանձնահատկություններից ելնելով, C++ լեզուն թույլատրում է սահմանել ֆունկցիաներ, որոնք արգումենտներ չեն ստանում կամ/և արժեքներ չեն վերադարձնում։

main ֆունկցիայի օրինակով արդեն տեսանք, որ C++ լեզվում ֆունկցիայի սահմանումն ունի չորս բաղադրիչ. i) վերադարձվող արժեքի տիպ, ii) անուն, iii) արգումենտների ցուցակ, iv) մարմին։ Օրինակ, եթե սահմանենք տրված շառավղով շրջանի մակերեսը հաշվող area ֆունկցիան, ապա այն կունենա այսպիսի տեսք.
double area( double radius )
{
  return radius * radius * 3.14159265358979323846;
}
Այս ֆունկցիայի վերադարձվող արժեքի տիպը double է, անունը area է, արգումենտների ցուցակում թվարկված է միակ radius արգումենտը՝ իր տիպի հետ, իսկ մարմինը բաղկացած է միակ return հրամանից, որի արգումենտում շրջանի մակերեսի հաշվման բանաձևն է։

Ֆունկցիայի տիպ է կոչվում վերադարձրած արժեքի տիպի ու արգուենտների տիպերի ցուցակի համադրությունը։

Եթե հարկավոր է սահմանել մի ֆունկցիա, որից արժեք չենք ակնկալում, ապա պետք է վրա վերադարձվող արժեքի տիպը նշել որպես void։ Այսպիսի ֆունկցիային երբեմն անվանում են նաև պրոցեդուրա։ Օրինակ, սահմանենք մի ֆունկցիա, որը ստանում է առանց նշանի ամբողջ թիվ (unsigned int) և արտածում է այդ թվի տասական, ութական ու տասնվեցական ներկայացումները։ Այդ ներկայացումները ստացվում են հոսքերի dec, oct և hex մանիպուլյատորների օգնությամբ, որոնք սահմանված են iostream ֆայլում։
void print_number( unsigned int num )
{
  std::cout << std::setw(8) << std::dec << num
            << std::setw(8) << std::oct << num
            << std::setw(8) << std::hex << num
            << std::endl;
}
Արտածման հոսքի setw պարամետրով մանիպուլյատորը, որ սահմանված է գրադարանի iomanip ֆայլում, հնարավորություն է տալիս սահմանել այն դիրքերի քանակը, որոնք պետք է օգտագործվեն արժեքի արտածման համար։

Եթե ֆունկցիան պետք է ստանա մի քանի արգումենտներ, ապա դրանք արգումենտների ցուցակում թվարկվում են իրարից ստորակետով անջատված։ Օրինակ, սահմանենք avg3 ֆունկցիան, որը արգումենտում ստանում է երեք իրական թիվ և վերադարձնում դրանց թվաբանական միջինը։
double avg3( double a, double b, double c )
{
  auto sum = a + b + c;
  return sum / 3;
}
Եթե մի որևէ f() ֆունկցիայում օգտագործվելու է մի այլ g() ֆունկցիա, ապա այն պետք է ավելի շուտ հայտարարված կամ սահմանված լինի։ Օրինակ, ծրագրում այդ երկու ֆունկցիաների փոխադարարձ դասավորությունը կարող է լինել այսպիսին.
int g( double a, char b )
{
    // ինչ-որ հրամաններ
    return 777;
}

void f( int x )
{
    // ինչ-որ հրամաններ
    auto v = g( 3.14, 'p' );
    // ինչ-որ հրամաններ
}
Կամ, f() ֆունկցիային կարող է նախորդել միայն g() ֆունկցիայի հայտարարությունը։ Ահա այսպես.
int g( double, char );

void f( int x )
{
    // ինչ-որ հրամաններ
    auto v = g( 3.14, 'p' );
    // ինչ-որ հրամաններ
}

int g( double a, char b )
{
    // ինչ-որ հրամաններ
    return 777;
}
Առաջին տողում գրված արտահայտությունը կոմպիլյատորին տեղեկացնում է, որ գոյություն ունի double և char տիպի արգումենտներ ստացող և int արժեք վերադարձնող g անունով ֆունկցիա, որի սահմանումը գալու է քիչ ավելի ուշ։

Wednesday, September 17, 2014

C++: Փոփոխական

C++ լեզվով գրված ծրագրերի առանցքային բաղադրիչներից մեկը փոփոխականն է։ Ծրագրի տեսակետից փոփոխականը մի անվանված օբյեկտ է, որին կարելի է ծրագրի կատարման տարբեր պահերին վերագրել տարբեր արժեքներ։ Օրինակ, եթե պետք է ունենալ մի փոփոխական, որի մեջ պահելու ենք շրջանի շառավիղը, ապա կարող ենք գրել.
double radius;
Այս արտահայտություն կոչվում է փոփոխականի հայտարարություն. C++ լեզվի double ծառայողական բառը նշում է, որ raduis փոփոխականը հայտարարված է որպես կրկնակի ճշտության (double precision) իրական թիվ։ Կամ ասում են, որ radiusտիպը double է։ Այդ տիպով է որոշվում ԷՀՄ-ի հիշողության մեջ փոփոխականի զբաղեցրած չափը և նրա հետ թույլատրելի գործողությունները։

Մի որևէ տիպի չափն իմանալու համար կարելի է օգտագործել sizeofգործողությունը։ Այն իր արգումենտում սպասում է տիպի կամ փոփոխականի անուն և վերադարձնում է դրա չափը։ Օրինակ, համոզվելու համար, որ կրկնակի ճշտության իրական թվերի double տիպը զբաղեցնում է հիշողության 8 բայթ (64 բիթ), բուլյան bool տիպը՝ 1 բայթ, ամբողջ թվերի int տիպը՝ 4 բայթ և այլն, կարող ենք օգտագործել հետևյալ ծրագիրը.
#include <iostream>

int main()
{
    using namespace std;
    cout << "  bool " << sizeof(bool) << endl;
    cout << "  char " << sizeof(char) << endl;
    cout << "   int " << sizeof(int) << endl;
    cout << "double " << sizeof(double) << endl;
}
Փոփոխականը հայտարարելիս ցանկալի է նշել նաև նրա սկզբնական արժեքը, հակառակ դեպքում հայտնի չէ, թե կատարման ժամանակ այն ինչպիսին կլինի։ Սկզբնական արժեքը տալու համար այն պետք է պարզապես գրել փոփոխականի անունից հետո՝ վերցրած «{» և «}» փակագծերի մեջ։ Օրինակ, count և length ամբողջաթիվ փոփոխականները հայտարարելու և նրանց 0 սկզբնական արժեքը տալու համար պետք է գրել.
int count{0}, length{0};
Փոփոխականի հայտարարությունը ուժի մեջ է այն լեքսիկական բլոկում, որտեղ ինքը սահմանված է։ Այդ բլոկը որոշվում է կամ {} փակագծերով, կամ ղեկավարող կառուցվածքների մարմնով։ Օրինակ, հետևյալ ծրագրի կատարման արդյունքում կարտածվի թվերի 10, 20, 10 հաջորդականությունը, որից էլ երևում է, որ տեքստի 7-րդ տողում սկսվող և 10-րդ տողում ավարտվող բլոկում սահմանված x փոփոխականը և 5-րդ տողում սահմանված x փոփոխականն ունեն տարբեր տեսանելիության տիրույթներ (scope).
#include <iostream>

int main()
{
    int x{10};
    std::cout << x << ", ";
    {
        int x{20};
        std::cout << x << ", ";
    }
    std::cout << x << std::endl;
}
Փոփոխականի ընթացիկ արժեքը փոխվում է (նրան նոր արժեք է վերագրվում) վերագրման (=) գործողության միջոցով։ Օրինակ, վերը հայտարարված radius փոփոխականին \(2.54\) արժեքը (1 մատնաչափ, դյույմ) վերագրելու համար պետք է գրել.
radius = 2.54;
Վերագրման գործողությունը կարելի է օգտագործել նաև փոփոխականի հայտարարության մեջ, նրան սկզբնական արժեք տալու համար։ Օրինակ, սահմանենք area փոփոխականը և նրան վերագրենք radius շառավղով շրջանի մակերեսը.
auto area = radius * radius * 3.1415;
Եթե փոփոխականի հայտարարման ժամանակ տիպի փոխարեն գրված է auto ծառայողական բառը, ապա կոմպիլյատորը փոփոխականի տիպը որոշում է ըստ նրան վերագրված արժեքի. կատարվում է տիպի արտածում (տիպի դուրսբերում)։ Քանի որ radius փոփոխականի և \(3.1415\) թվի տիպերը double են, և բազմապատկման (*) գործողությունն էլ վերադարձնելու է double տիպի արժեք, ապա կոմպիլյատորը եզրակացնում է, որ area փոփոխականի տիպը նույնպես պետք է լինի double։

Գրենք մի ծրագիր, որն օգտագործողից հարցնում է շրջանի շառավիղը և արտածում է այդ նույն շրջանի մակերեսն ու եզրագծի երկարությունը։ Նորից գործարկենք տեքստային խմբագրիչը և ստեղծենք ex04.cpp ֆայլը՝ հետևյալ պարունակությամբ.
#include <iostream>

int main()
{
    std::cout << "ներմուծեք շրջանի շառավիղը ";
    double radius{0.0};
    std::cin >> radius;

    const double pi = 3.14159265358979323846;

    auto length = 2 * pi * radius;
    auto area = pi * radius * radius;

    std::cout << "երկարությունը = " << length << std::endl
              << "      մակերեսը = " << area << std::endl;
}
7-րդ տողում գրված cin (console input) օբյեկտը կապված է համակարգի ստանդարտ ներմուծման հոսքի հետ։ Իսկ >> գործողությունը իր ձախ արգումետից եկած արժեքը գրում է աջ արգումենտի մեջ։ Տվյալ դեպքում cin >> radius արտահայտությունը ստեղնաշարից կարդում է մի թվային արժեք և այն վերագրում radius փոփոխականին։

9-րդ տողում const ծառայողական բառն ասում է, որ պետք է սահմանել pi անունով և \(3.14159265358979323846\) արժեքով իրական հաստատուն։ Հաստատունի արժեքը, բնականաբար, փոխել չի կարելի։ Եթե ծրագրում փորձ կատարվի, օրինակ, pi օբյեկտին նոր արժեք վերագրել, ապա կոմպիլյատորն այդ առթիվ կարտահայտի իր դժգոհությունը և կտա համապատասխան հաղորդագրություն։

10-րդ և 11-րդ տողերում հաշվվում են length (երկարություն) և area (մակերես) փոփոխականների արժեքները։

13-րդ և 14-րդ տողերում կազմված է << գործողությունների շղթա։ Սա հնարավոր է դառնում այն բանի շնորհիվ, որ << գործողությունը որպես արժեք վերադարձնում է իր ձախ արգումենտը։ endl մանիպուլյատորը արտածման հոսքին է ուղարկում նոր տողի անցման նիշը։
Կոմպիլյատորի օգնությամբ թարգմանենք այս ծրագիրը և աշխատեցնենք.
$ g++ -std=c++11 -o ex04 ex04.cpp
$ ./ex04
ներմուծեք շրջանի շառավիղը 2.54
երկարությունը = 15.9593
     շառավիղը = 20.2683
Երբեմն կարող է անհարմարության զգացողություն առաջացնել այն փաստը, որ STL-ի բոլոր օբյեկտների, դասերի կամ ֆունկցիաների անուններից առաջ պետք է գրել stl:: նախդիրը։ Դրանից կարելի է խուսափել main ֆունկցիայի սկզբում գրելով using namespace std; արտահայտությունը։ Սա կոմպիլյատորից պահանջում է տեսանելի դարձնել std անունների տիրույթի բոլոր անունները։ Եթե հարկավոր է տեսանելի դարձնոլ միայն որոշ ընտրված անուններ, օրինակ, cout, cin և endl անունները, ապա կարող ենք using հրամանով թվարկել դրանք.
using std::cin;
using std::cout;
using std::endl;
Այս հայտարարություններից հետո արդեն կարող ենք ծրագրի տեքստում cout, cin և endl անուններից առաջ չգրել stl:: նախդիրը։

Փոփոխականին հատկացված հիշողության տիրույթի առաջին բայթի համարը կոչվում է փոփոխականի հասցե։ Այն կարելի է ստանալ & ունար գործողության միջոցով։ Օրինակ, radius փոփոխականի հասցեն արտածելու համար պետք է գրել.
std::cout << &radius << std::endl;
Փոփոխականի հասցեն կարելի է վերագրել նաև հասցեի տիպ ունեցող մեկ այլ փոփոխականի։ Օրինակ.
auto p_radius = &radius;
Մի որևէ տիպի փոփոխականի հասցե պահելու համար նախատեսված փոփոխական հայտարարելիս պետք է պարզապես հայտարարության մեջ տիպի անունից հետո գրել * նիշը։ Օրինակ,
double* p_radius2{&radius};
Հասցե պարունակող փոփոխականին անվանում են ցուցիչ։ Օրինակ, p_radius և p_radius_2 փոփոխականները double տիպի օբյեկտների ցուցիչներ են։

Եթե ցուցիչի հայտարարման պահին դեռևս հայտնի չէ, թե այն ինչ օբյեկտի է «ցույց տալու», ապա այն պետք է արժեքավորել nullptr արժեքով։ Այսպիսի ցուցիչներին անվանում են զրոյական։

Tuesday, September 16, 2014

C++: Առաջին ծրագիրը մեկնաբանություններով

C++ ծրագրավորման լեզվի ուսումնասիրությունը սկսենք մի կարճ ծրագրից, որը պետք է ստանդարտ արտածման հոսքին դուրս բերի «Ողջո՜ւյն, այդ ես եմ, քո առաջին ծրագիրը։» տողը։

Գործարկենք տեքստային խմբագրիչը և նրա օգնությամբ ստեղծենք ex01.cpp ֆայլը՝ հետևյալ պարունակությամբ․
// Առաջին C++ ծրագիրը
#include <iostream>

int main()
{
    std::cout << "Ողջո՜ւյն, այդ ես եմ, քո առաջին ծրագիրը:\n";
}
Շրագրի տեքստը ֆայլու գրառելուց հետո այն պետք է կոմպիլյատորի օգնությամբ թարգմանել մեքենայական հրամանների և կատարել։ Բայց մի փոքր առաջ անցնենք ու ծրագրի ամեն մի տողի համար տանք համառոտ մեկնաբանություն։

Առաջին տողը «//» նիշերով սկսվող և մինչև տողի վերջը շարունակվող մեկնաբանություն է։ Մեկնաբանությունները, որոնք կարող են պարունակել կամայական տեքստ, ծրագրի իմաստի վրա չեն ազդում և ամբողջովին անտեսվում են կոմպիլյատորի կողմից։ Դրանց նպատակն է ծրագում բացատրություններ թողնել մարդու համար։

Երկրորդ տողում գրված #include հրահանգը նախապրոցեսորից պահանջում է ծրագրին կցենլ iostream գրադարանային ֆայլը։ Այս ֆայլում են սահմանված ստանդարտ ներմուծման ու արտածման հոսքերի հետ աշխատող գործողություններն ու օբյեկտները։ Ի թիվս զանազան ֆունկցիաների ու օբյեկտների, iostream ֆայլը պարունակում է ստանդարտ արտածման հոսքի հետ կապված cout օբյեկտը և իր աջ արգումենտը ձախ արգումենտի մեջ գրող << գործողությունը։

C++ լեզվով գրված ամեն մի ծրագիր պետք է պարունակի main անունով միակ ֆունկցիա։ Այս ֆունկցիան հանդիսանում է ծրագրի մուտքի կետը, այսինքն՝ ծրագրիրը սկսում է կատարվել main ֆունկցիայից։ Ավելի պատկերավոր ասած՝ ծրագիրը կատարելու համար օպերացիոն համակարգը կանչում է main ֆունկցիան։ Տվյալ դեպքում main ֆունկցիան արգումենտներ չի սպասում և վերադարձնում է int (integer, ամբողջ թիվ) տիպի արժեք։ Օպերացիոն համակարգն այս ֆունկցիայի արժեքը մեկնաբանում է որպես ծրագրի հաջող կամ անհաջող ավարտի ազդանշան։ Ըստ պայմանավորվածության, 0 արժեքը համարվում է հաջող ավարտ, իսկ 0-ից տարբեր դրական ամբողջ թվերը՝ անհաջող ավարտ։ C++ ֆունկցիայից որևէ արժեք է վերադարձվում է return հրամանով։ Սակայն միայն main ֆունկցիայի համար կա բացառություն, որ, եթե բացահայտորեն նշված չէ return հրամանը, ապա վերադարձվող արժեքը համարվում է 0։

main ֆունկցիայի մարմինը, որ պարփակված է «{» և «}» փակագծերի մեջ, պարունակում է միակ արտահայտություն, որտեղ << գործողության օգնությամբ «Ողջո՜ւյն, աշխարհ։» տողն ուղարկվում է ստանդարտ արտածման հոսքի հետ կապված cout (cconsole output) օբյեկտին։ cout անունից առաջ գրված std:: նախդիրը ցույց է տալիս, որ այդ երկու անունները պատկանում են լեզվի Կաղապարների ստանդարտ գրադարանին (Standard template library, STL)։
Պետք է հիշել, որ cout-ը C++ լեզվի ծառայողական բառ չէ։ Այն ընդամենը iostream գրադարանում հայտարարված ավտոմատ օբյեկտ է։
Հիմա այս ծրագիրը թարգմանենք (կոմպիլյացնենք) մեքենայական կոդի և աշխատեցնենք։ C++ լեզվով գրված ծրագրերը թարգմանության ժամանակ անցնում է երեք հիմնական փուլ. i) նախնական մշակում - preprocessing -- այս փուլում մշակվում են # նիշով սկսվող հրահանգները, որոնք ծրագրի տեքստի հետ կատարվում են զուտ տեքստային գործողություններ։ Օրինակմ ֆայլերի կցում, անունների փոփոխում արժեքներով և այլն, ii) թարգմանություն - compilation -- այս փուլում ծրագրավորողի գրած տեքստը թարգմանվում է մեքենայական կոդի և ստեղծվում են այսպես կոչված օբյեկտային ֆայլեր, iii) կապակցում - linking -- այս փուլում նոր ստեղծված օբյեկտային ֆայլերը կապակցվում են գրադարանային (կամ այլ) օբյեկտային ֆայլերի հետ և ստեղծվում է կատարվող մոդուլ։

Սովորաբար ծրագրի տեքստից կատարվող մոդուլի ստացման այս երեք փուլերը թաքնված են օգտագործողից և, պարզ ծրագերի դեպքում, կատարվում են մեկ հրամանով։ Օրինակ, Bash ինտերպրետատորի հրամանային տողում ներմուծենք հետևյալը, որտեղ -std=c++11 պարամետրով կոմպիլյատորից պահանջում ենք միացնել C++11 ստանդարտի հատկությունները.
$ g++ -std=c++11 ex01.cpp
կամ, եթե ուզում ենք օգտագործել clang++ կոմպիլյատորը, ապա.
$ clang++ -std=c++11 ex01.cpp
Եթե կոմպիլյատորը որևէ սխալ չի հայտնաբերել, ապա ընթացիկ պանակում ստեղծվում է a.out անունով կատարվող մոդուլը։ Երբ հարկավոր է կատարվող մոդուլին այլ անուն տալ, ապա կարող ենք օգտագործել կոմպիլյատորի -o պարամետրը։ Օրինակ.
$ clang++ -std=c++11 -o ex01 ex01.cpp
այս հրամանի կատարման արդյունքում կատարվող մոդուլը a.out-ի փոխարեն կունենա ex01 անունը։

ex01 մոդուլն աշխատեցնելու համար պետք է Bash—ի հրամանային տողում ներմուծել.
$ ./ex01
Ողջո՜ւյն, աշխարհ։
Ծրագրի կատարման արդյունքում տեսնում ենք արտածված տողը. սա հենց այն է, ինչ ակնկալում էինք առաջին ծրագրից։

Որպեսզի համոզվենք, որ իսկապես main ֆունկցիայի վերադարձրած արժեքը փոխանցվում է օպերացիոն համակարգին, կարող ենք ծրագրի կատարումից հետո Bash ինտերպրետատորի echo հրամանով դուրս բերել $? փսևդոփոփոխականի արժեքը։
$ echo $?
0
Հիմա վերը բերված օրինակի ex01.cpp ֆայլը պատճենենք ex02.cpp անունով, և main ֆունկցիայի մարմինն ավարտող «}» փակագծից առաջ ավելացնենք «return 0;» հրամանը։
#include 

int main()
{
    std::cout << "Ողջո՜ւյն, աշխարհ։" << std::endl;
    return 7;
}
Ապա նորից կոմպիլյացնենք ծրագիրը, աշխատեցնենք ու արտածենք $? փսևդոփոփոխականի արժեքը։ Հրամանների հաջորդականությունը և արտածված արդյունքները հետևյալ տեսքն ունեն.
$ g++ -std=c++11 -o ex02 ex02.cpp
$ ./ex02
Ողջո՜ւյն, աշխարհ։
$ echo $?
7

Sunday, September 14, 2014

Յունգի աղյուսակ - Young tabelau

\(n\times m\) չափի \(A\) մատրիցը կոչվում է Յունգի աղյուսակ (Young tabelau), եթե նրա տարրերը տողերում կարգավորված են ձախից-աջ, իսկ սյուներում՝ վերևից-ներքև։ Եթե աղյուսակի մի որևէ վանդակ դատարկ է, ապա այն նշվում է \(\infty\) (անվերջություն) նշանով։ \(A\) Յունգի աղյուսակը համարվում է դատարկ, եթե \(A[0,0] = \infty\)։ Աղյուսակը համարվում է ամբողջովին լցված, եթե \(A[n-1,m-1] \ne \infty\)։ Աղյուսակի տարրերից կարգով ամենափոքրը միշտ գտնվում է \(A[0,0]\) բջջում։

Ահա Յունգի աղյուսակի մի նմուշ, որը պարունակում է \(0\), \(1\), \(2\), \(3\), \(5\), \(7\), \(9\) թվերը։
0029
357
Յունգի աղյուսակի հետ կատարվող տիպիկ գործողություններից կարելի է համարել նոր տարրի ավելացումը, մինիմալ տարրի հեռացումը, դատարկ կամ լցված լինելը ստուգելը։

Իրական թվերի համար նախատեսված Յունգի աղյուսակը կարելի է սահմանել C++ լեզվի հետևյալ դասով․
class Tabelau {
private:
    int rows;      // տողերի քանակը
    int columns;   // սյուների քանակը
    double** data; // տվյալների աղյուսակ

public:
    Tabelau( int, int );
    ~Tabelau();

    bool is_empty() const; // աղյուսակը դատարկ է
    bool is_full() const;  // աղյուսակը լցված է

    double minimum() const; // փոքրագույն տարրը
    void add( double );     // ավելացնել նոր տարր
    void remove();          // հեռացնել փոքրագույն տարրը

private:
    // աղյուսակի կարգավորում նոր տարրն ավելացնելուց հետո
    void add_aux( int, int );
    // աղյուսակի կարգավորում նոր տարրը հեռացնելուց հետո
    void remove_aux( int, int );
};
Դասի կոնստրուկտորի նպատակը նոր աղյուսակի ստեղծումն է, որի բոլոր բջիջները նախապես լրացված են \(\infty\) արժեքով։
Tabelau::Tabelau( int r, int c)
  : rows{r}, columns{c}
{
  data = new double*[rows];
  for( int i = 0; i < rows; ++i ) {
    data[i] = new double[columns];
    for( int j = 0; j < columns; ++j )
      data[i][j] = INFINITY;
  }
}
Դեստրուկտորը պարզապես ազատում է զբաղեցրած հիշողությունը։
Tabelau::~Tabelau()
{
    for( int i = 0; i < rows; ++i )
        delete[] data[i];
    delete[] data;
}
Աղյուսակի դատարկ լինելը ստուգվում է is_empty() մեթոդով, իսկ լցված լինելը՝ is_full() մեթոդով։
bool Tabelau::is_empty() const
{
  return data[0][0] == INFINITY;
}

bool Tabelau::is_full() const
{
  return data[rows-1][columns-1] != INFINITY;
}
Փոքրագույն տարրը վերադարձնում է minimum() մեթոդը․
double Tabelau::minimum() const
{
  return data[0][0];
}
\(A\) Յունգի աղյուսակում նոր տարրն ավելացվում է \(A[rows-1,columns-1]\) բջջում, այնուհետև այն փոխատեղվում է իրենից վերևում և ձախում գտնվող տարրերից մեծագույնի հետ։ Նույնը կրկնվում է այնքան անգամ, քանի դեռ դիտարկվող տարրից վերև կամ ձախ գոյություն ունի ավելի մեծ արժեքով տարր։
void Tabelau::add( double val )
{
  data[rows-1][columns-1] = val;
  add_aux( rows-1, columns-1 );
}
Նոր տարրը \(A[rows-1,columns-1]\) բջջում գրառելուց հետո աղյուսակի կարգավորումը կատարվում է add_aux() ռեկուրսիվ մեթոդով։
void Tabelau::add_aux( int r, int c )
{
  int k{r}, h{c};
  if( r > 0 && data[r][c] < data[r-1][c] )
    k = r - 1;
  if( c > 0 && data[k][h] < data[r][c-1] )
    k = r, h = c - 1;
  if( k != r || h != c ) {
    double temp{data[r][c]};
    data[r][c] = data[k][h];
    data[k][h] = temp;
    add_aux( k, h );
  }
}
Մինիմալ տարրը, որ միշտ գտնվում է \(A[0,0]\) բջջում, աղյուսակից հեռացնելու համար նրա տեղում գրվում է \(\infty\), և այդ պատճառով էլ խախտվում է Յունգի աղյուսակի հատկությունը։ Աղյուսակը նորից կարգավորելու համար պետք է \(\infty\) արժեքն այնքան ժամանակ տեղափոխել դեպի աջ կամ ներքև, քանի դեռ գոյություն ունի նրանից փոքր տարր։
void Tabelau::remove()
{
  data[0][0] = INFINITY;
  remove_aux( 0, 0 );
}
Տարրը հեռացնելուց հետո աղյուսակի կարգավորումը կատարվում է remove_aux() մեթոդով։
void Tabelau::remove_aux( int r, int c )
{
  int k{r}, h{c};
  if( r < rows - 1 && data[r][c] > data[r+1][c] )
    k = r + 1;
  if( c < columns - 1 && data[k][h] > data[r][c+1] )
    k = r, h = c + 1;
  if( k != r || h != c ) {
    double temp{data[r][c]};
    data[r][c] = data[k][h];
    data[k][h] = temp;
    remove_aux( k, h );
  }
}

Թերևս այսքանը Յունգի աղյուսակների մասին։ Նշեմ նաև, որ այն հաճախ օգտագործվում է նախապատվություններով հերթերի կազմակերպման և կարգավորման heap-sort ալգորիթմների իրականացման համար։

Tuesday, September 9, 2014

C++ ծրագրավորման միջավայր

Հաշվի առնելով այն փաստը, որ C++ լեզուն նոր սովորողները հաճախ դժվարանում են գտնել ու իրենց համակարգիչներում տեղադրել լեզվի կոմպիլյատոր ու ծրագրավոր միջավայր, նաև հաշվի առնելով օգտագործողների ճնշող մեծամասնության կողմից Windows օպերացիոն համակարգի օգտագործման փաստը, ես փորձեցի պարզել, թե գոյություն ունեցող կոմպիլյատորներից ու ծրագրավորման միջավայրերից որն է ավելի հարմար սկսնակների համար։
Հենց սկզբից ասեմ, որ իմ ընտրություն կանգ առավ Code::Blocks ծրագրավորման ինտեգրացված միջավայրի (IDE, integrated development environment) վրա: Այն ունի բազմաթիվ առավելություններ, որոնց թվում են.
  1. Անվճար է և տարածվում է բաց կոդով (open source)։
  2. Բազմապլատֆորմ է։ Աշխատում է Windows, GNU/Linux, Mac OS օպերացիոն համակարգերում։
  3. Հնարավորություն ունի օգտագործել տարբեր կոմպիլյատորներ. Visual C++, GNU GCC, clang և այլն։
  4. Ունի շրագրերի շտկման ներդրված գործիք (debugger):
  5. Բեռնվող փաթեթը բավականին փոքր է՝ իր մեջ պարունակող G++ կոմպիլյատորի հետ միասին մոտ 100 Մբ։
Տեղադրելու համար պետք է բեռնել 13.12 տարբերակի՝ Windows-ի համար նախատեսված փաթեթը և աշխատեցնել այն։ Տեղադրման պրոցեսը որ մի բարդություն չի ներկայացում և ու չեմ ուզում այստեղ ներկայացնել այդ քայլերը։
     Տեղադրելուց հետո, երբ ծրագիրն առաջին անգամ գործարկվում է, առաջարկում է ընտրել համակարգում հայտնաբերված կոմպիլյատորներից մեկը։ Եթե մինչ այդ այլ կոմպիլյատոր տեղադրված չի եղել, ապա միակ ընտրության հնարավորությունը Code::Blocks-ի հետ տեղադրված GNU GCC կոմպիլյատորն է (MinGW ներկայացմաբ): Այնուհետև բացվում է աշխատանքային միջավայրը՝ մոտավորապես ստորև բերված նկարի տեսքով.
Առաջին ծրագիրը գրելու համար պետք է սեղմել «Create new project» հղմանը (կամ մենյուից ընտրել File->New->Project...), այնուհետև Category ցուցակից ընտրել Console կետը, իսկ պրոյեկտների շաբլոնների ցուցակից ընտրել Console application շաբլոնը։
Հետո պետք է ընտրել C կամ C++ ծրագրավորման լեզուն և պրոյեկտի անունն ու տեղը։
Համակարգը պրոյեկտի համար գեներացնում է main.cpp ֆայլը՝ հետևյալ պարունակությոմբ։
#include 

using namespace std;

int main()
{
    cout << "Hello world!" << endl;
    return 0;
}
Բայց այս կոդի վերլուծությունն ու մեկնաբանությունը լրիվ այլ օպերա է :)

* * *
Կարելի է, իհարկե, հետևելով դասախոսների ու խնամի-ծանոթ-բարեկամների խորհրդին, տեղադրել Microsoft ֆիրմայի Visual Studio միջավայրը, որը մի հսկայական փաթեթ է, իր մեջ պարունակում է և՛ C++ լեզվի կոմպիլյատորը, և՛ ծրագրավորման ինտեգրացված միջավայր է, և՛ գրաֆիկական ծրագրերի նախագծման համակարգ է, ...։ Բայց կարծում եմ, որ տեղին չէ, ընդամենը ծրագրավորման հիմունքները սովորոելու համար, համակարգիչը զբաղեցնել տարատեսակ անպետք կամ ավելորդ գործիքներով։ Այլ կերպ ասած՝ «չարժե թնդանոթով կրակել ճնճղուկի վրա»։ Հենց այս պատճառով էլ, ամենևին չթերագնահատելով Visual Studio-ի արժանիքները, ես խորհուրդ չեմ տալիս տեղադրել այս փաթեթը։
     QtCreator ծրագրավորման ինտեգրացված միջավայրը ստեղծվել է Qt գրաֆիկական գրադարանների օգտագործմամբ ծրագրեր գրելու համար։ Այն անվճար տարածվող ծրագիր է։ Փաթեթը, որ պետք է բեռնել ու տեղադրել, մոտավորապես 600 Մբ է։ Նորից կարծում եմ, որ սա էլ շատ ավելորդ ու սկսնակների համար դեռևս անպետք գործիքներ է պարունակում։
     Համակարգչում տեղադրելով GNU GCC կոմպիլյատորը, կարելի է այնուհետև տեղադրել Eclipse կամ NetBeans միջավայրերն ու դրան կարգավորել այնպես, որ աշխատեն նշված կոմպիլյատորի հետ։ Սա նույնպես ընդունելի տարբերակ է, բայց պահանջում է մի քիչ ավելի շատ քայլեր։

Saturday, August 23, 2014

Խնդիրների լուծումներ Lisp լեզվով

Տարիներ առաջ, երբ ես սովորում էի ԵՊՀ-ի ԻԿՄ ֆակուլտետում, երկրորդ կամ երրորդ կուրսում անցնում էինք մի անհասկանալի առարկա։ Այդ առարկայի անվանումն էր «Ֆունկցիոնալ ծրագրավորման համակարգեր» (կամ «Ծրագրավորման ֆունկցիոնալ համակարգեր»)։ Դասախոսություններին պատմում էին ինչ-որ անհասկանալի ու ախմախ բաների մասին։ Բայց գործնական դասերը, որոնք ոչ մի կապ չունեին դասախոսությունների հետ, գոնե հետաքրքիր էին նրանով, որ խնդիրներ էինք լուծում Lisp լեզվով։ Խնդրագիրք ասած բանն, իհարկե, գոյություն չուներ․ դասախոսներն ունեին սովորական թղթերի վրա տպած մի ցուցակ, որից էլ դասերին վարժություններ էինք անում։

Ստորև բերված են այդ ցուցակի խնդիրներից մի մասի լուծումներ։ Որոշ խնդիրների պահանջներ միգուցե վատ են ձևակերպված, որոշներինը՝ ակնհայտ անհեթեթություն են։ Բայց սա այն է, ինչ որ կար...

Լրացում (12.մարտ.2016)։ Ինձ հայտնի դարձավ, որ ստորև բերված խնդիրների հավաքածուն ԵՊՀ ԻԿՄ ֆակուլտետում հրատարակվել (կապ պատրաստվում է հրատարակության) առանձին խնդրագրքի տեսքով։ Այս խնդիրների ձևակերպումների բոլոր հեղինակային իրավունքները պատկանում են այդ խնդրագրքի հեղինակին կամ հեղինակային խմբին։ Նույն այդ հեղինակները որևէ առնչություն չունեն խնդիրների հետ բերված լուծումների հետ։


Թվային ռեկուրսիա

4. Գրել տրված \(n\) թվի ֆակտորիալը հաշվարկող ծրագիր:

Հետևելով ֆակտորիալի սահմանմանը՝ \(n!=1\cdot 2\cdot\ldots\cdot n\), կգրենք հետևյալ ֆունկցիան։
(defun factorial (n)
  (if (= n 0)
      1
      (* n (factorial (1- n)))))
Բայց ավելի արդյունավետ կլինի գրել ֆակտորիալը հաշվող ֆունկցիայի tail recursive տարբերակը։ Հետևյալ factorial-b ֆունկցիայի մարմնում սահմանված է factorial-rec ֆունկցիան, որի երկրորդ արգումենտը նախատեսված է արդյունքը կուտակելու համար։
(defun factorial-b (n)
  (labels 
      ((factorial-rec (m r)
  (if (= m 1)
      r
      (factorial-rec (1- m) (* m r)))))
    (factorial-rec n 1)))
5. Գրել Ֆիբոնաչիի հաջորդականության N-րդ անդամը հաշվարկող ծրագիր:

Նորից հետևելով Ֆիբոնաչիի թվերի սահմանմանը, կարելի է սահմանել հետևյալ ֆունկցիան։
(defun fibonachi (N)
  (if (or (= N 0) (= N 1))
      1
      (+ (fibonachi (- N 1)) (fibonachi (- N 2)))))
Ֆիբոնաչիի թվերի համար էլ կարելի է սահմանել tail recursive ֆունկցիա։ Ահա այն․
(defun fibonacci-b (n)
  (labels
      ((fibonacci-rec (m a b)
  (if (< m 2)
      a
      (fibonacci-rec (- m 1) (+ a b) a))))
    (fibonacci-rec n 1 0)))
6. Գրել \(x\) բնական թիվը չգերազանցող զույգ թվերի գումարը:
(defun sum-of-evens (x)
  (cond 
    ((zerop x) 0)
    ((evenp x) (+ x (sum-of-evens (1- x))))
    (t (sum-of-evens (1- x)))))
(defun sum-of-evens-b (x)
  (labels
      ((sum-of-evens-rec (y s)
  (cond 
    ((zerop y) s)
    ((evenp y) (sum-of-evens-rec (1- y) (+ s y)))
    (t (sum-of-evens-rec (1- y) s)))))
    (sum-of-evens-rec x 0)))
7. Գրել \(x\) թվին չգերազանցող կենտ թվերի արտադրյալը:
(defun prod-of-odds (x)
  (cond ((= x 1) 1)
 ((oddp x) (* x (prod-of-odds (1- x))))
 (t (prod-of-odds (1- x)))))
(defun prod-of-odds-b (x)
  (labels
      ((prod-of-odds-rec (y p)
  (cond ((= y 1) p)
        ((oddp y) (prod-of-odds-rec (1- y) (* p y)))
        (t (prod-of-odds-rec (1- y) p)))))
    (prod-of-odds-rec x 1)))
8. Գրել \(x\) թվի կիսաֆակտորիալը հաշվող ֆունկցիա:
(defun semifactorial (x)
  (labels
      ((semifac-help (k)
  (if (< k 0)
      1
      (* (semifac-help (1- k)) (- x (* 2 k))))))
    (semifac-help (1- (ceiling x 2)))))
(defun semifactorial-b (x)
  (labels
      ((semifac-rec (k r)
  (if (< k 0)
      r
      (semifac-rec (1- k) (* r (- x (* 2 k)))))))
    (semifac-rec (1- (ceiling x 2)) 1)))
9. Lisp լեզվով սահմանել most-divisor ֆունկցիան. F(x)=x թվի ամենամեծ բաժանարարը, եթե \(x\ge0\), հակառակ դեպքում՝ \(0\):
(defun most-divisor (x)
  (labels
     ((most-div-help (a b)
        (cond
           ((zerop b) 1)
           ((zerop (rem a b)) b)
           (t (most-div-help a (1- b))))))
    (cond
       ((<= x 0) 0)
       ((< x 3) 1)
       ((evenp x) (/ x 2))
       (t (most-div-help x (1- x))))))
10. Lisp լեզվով սահմանել Էվիկլիդեսի ալգորիթմը:
(defun euclid(x y)
  (if (= y 0)
      x
    (euclid y (mod x y))))
11. Օգտվելով 1+ ֆունկցիայից Lisp-ով ծրագրավորել երկու տեղանի գումարման plus ֆունկցիան ամբողջ թվերի համար:
(defun plus (a b)
  (if (zerop b)
      a
      (plus (1+ a) (1- b))))
12. Օգտվելով + ֆունկցիայից, ծրագրավորել prod ֆունկցիան, ամբողջ թվերի համար:
(defun prod (x y)
  (labels
      ((prod-help (b r)
  (if (zerop b) 
      r
      (prod-help (1- b) (+ x r)))))
    (if (or (= y 0) (= x 0))
 0
 (prod-help y 0))))
13. Օգտվելով * ֆունկցիայից, ծրագրավորել աստիճան բարձրացնելու ex ֆունկցիան, ամբողջ թվերի համար:
(defun ex (x y)
  (if (zerop y)
      1
      (* x (ex x (1- y)))))
14. Սահմանել հետևյալ ֆունկցիան. \(F(x)=x!+(2x)!\), եթե \(x\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex14 (x)
    (if (< x 0)
        0
        (+ (factorial x) (factorial (* 2 x)))))
15. Սահմանել հետևյալ ֆունկցիան. \(F(x)=x!+x^y\), եթե \(x\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex15 (x y)
    (if (< x 0)
      0
      (+ (factorial x) (expt x y))))
16. Սահմանել հետևյալ ֆունկցիան. \(F(x,y)=(xy)!\), եթե \(x,y\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex16 (x y)
    (if (or (< x 0) (< y 0))
        0
        (* (factorial x) (factorial y))))
17. Սահմանել հետևյալ ֆունկցիան. \(f(x)=\sum\limits_{i=0}^x i^2\), եթե \(x\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex17 (x)
    (if (< x 0)
        0
        (+ (* x x) (ex17 (1- x)))))
18. Սահմանել հետևյալ ֆունկցիան. \(f(x)=\sum\limits_{i=0}^x (2i)!\), եթե \(x\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex18 (x)
    (if (minusp x)
        0
        (+ (factorial (* 2 x)) (ex18 (1- x)))))
19. Սահմանել հետևյալ ֆունկցիան. \(f(x,y)=\sum\limits_{i=0}^y(xi)!\), եթե \(x,y\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex19 (x y)
    (if (or (<= x 0) (<= y 0))
        0
        (+ (factorial (* x y)) (ex19 x (1- y)))))
20. Սահմանել հետևյալ ֆունկցիան. \(f(x,y)=\sum\limits_{i=0}^x i^y\), եթե \(x,y\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex20 (x y)
    (if (minusp x)
        0
        (+ (expt x y) (ex20 (1- x) y))))
21. Սահմանել հետևյալ ֆունկցիան. \(f(x)=\sum\limits_{i=0}^x\sqrt{i}\), եթե \(x\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex21 (x)
    (if (< x 0)
        0
        (+ (sqrt x) (ex21 (1- x)))))
22. Սահմանել հետևյալ ֆունկցիան. \(f(x)=\prod\limits_{i=0}^xe^i\), եթե \(x\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex22 (x)
    (if (<= x 0)
        1
        (* (exp x) (ex22 (1- x)))))
23. Սահմանել հետևյալ ֆունկցիան. \(f(x,y)=\prod\limits_{i=0}^y(x^i+i)\), եթե \(x,y\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex23 (x y)
    (if (< y 0)
        1
        (* (+ (expt x y) y) (ex23 x (1- y)))))
24. Սահմանել հետևյալ ֆունկցիան. \(f(x,y,z)=\prod\limits_{i=0}^z(x^i+y^i)\), եթե \(x,y,z\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex24 (x y z)
    (if (< z 0)
        1
        (* (+ (expt x z) (expt y z)) (ex24 x y (1- z)))))
25. Սահմանել հետևյալ ֆունկցիան. \(f(x,y,z)=\prod\limits_{i=0}^z(i^x+i^y)\), եթե \(x,y,z\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex25 (x y z)
    (if (< z 0)
        1
        (* (+ (expt z x) (expt z y)) (ex25 x y (1- z)))))
26. Սահմանել հետևյալ ֆունկցիան. \(f(x,y)=\sum\limits_{i=0}^y\log_yx\), եթե \(x,y\ge0\), հակառակ դեպքում՝ \(0\):
(defun ex26 (x y)
    (if (<= y 1)
        0
        (+ (log x y) (ex26 x (1- y)))))
27. Սահմանել ֆունկցիա, որը վերադարձնում է տրված \(x\) թվի բաժանարարների քանակը:
(defun count-divisors (x)
   (labels
       ((divisors-rec (y)
            (cond
              ((= 1 y) 1)
              ((zerop (rem x y)) (1+ (divisors-rec (1- y))))
              (t (divisors-rec (1- y))))))
   (cond 
     ((<= x 3) 1)
     ((evenp x) (divisors-rec (/ x 2)))
     (t (divisors-rec (1- x))))))
28. Սահմանել ֆունկցիա, որը վերադարձնում է տրված \(x\) թվի բաժանարարների գումարը:
(defun sum-of-divisors (x)
    (labels
       ((sum-of-div-rec (y)
          (cond
              ((= 1 y) 1)
              ((zerop (rem x y)) (+ y (sum-of-div-rec (1- y))))
              (t (sum-of-div-rec (1- y))))))
    (cond
        ((<= x 3) 1)
        ((evenp x) (sum-of-div-rec (/ x 2)))
        (t (sum-of-div-rec (1- x))))))
29. Սահմանել ֆունկցիա, որը ստուգում է տրված \(x\) թվի պարզ լինելը:
(defun prime-p (x)
    (= 1 (count-divisors x)))
30. Սահմանել ֆունկցիա, որը վերադարձնում է տրված \(x\) թվից փոքր կամ հավասար պարզ թվերի քանակը:
(defun count-primes (x)
    (cond 
        ((zerop x) 0)
        ((prime-p x) (1+ (count-primes (1- x))))
        (t (count-primes (1- x)))))
31. Սահմանել ֆունկցիա, որը վերադարձնում է տրված \(x\) թվի պարզ բաժանարարների քանակը:
(defun count-prime-divisors (x)
   (labels
       ((divisors-rec (y)
            (cond
              ((= 1 y) 1)
              ((and (prime-p y) (zerop (rem x y))) (1+ (divisors-rec (1- y))))
              (t (divisors-rec (1- y))))))
   (cond 
     ((<= x 3) 1)
     ((evenp x) (divisors-rec (/ x 2)))
     (t (divisors-rec (1- x))))))
32. Սահմանել ֆունկցիա, որը ստուգում է տրված \(x\) թվի կատարյալ լինելը:
(defun perfect-p (x)
    (= x (sum-of-divisors x)))
33. Սահմանել \(eiler\) (?) ֆունկցիան. \(f(x)=f(0)\cdot\ldots\cdot f(x-1)+1\):
(defun f (x)
   (labels
     ((h (y)
        (if (= y 1)
            1
            (* (h (1- y)) (f (1- y))))))
   (if (zerop x)
       1
       (1+ (h x)))))
34. Սահմանել ֆունկցիա, որը ստուգում է տրված \(x\) թվի զույգ լինելը:
(defun is-even (x)
    (zerop (logand x 1)))
35. Սահմանել ֆունկցիա, որը ստուգում է տրված \(x\) թվի կենտ լինելը:
(defun is-odd(x)
    (not (iseven x)))

Ցուցակային ռեկուրսիա

36. Սահմանել len_ անունով ֆունկցիա, որը վերադարձնում է տրված \(x\) ցուցակի երկարությունը (տարրերի քանակը) և nil, եթե արգումենտը ցուցակ չէ:
(defun len_ (x)
    (if (and (atom x) (not (null x)))
        nil
        (if (endp x)
            0
            (1+ (len_ (cdr x))))))
37. Սահմանել ֆունկցիա, որը վերադարձնում է տրված ցուցակի տարրերի գումարը:
(defun sum-1 (x)
    (if (endp x)
        0
        (+ (car x) (sum-1 (cdr x)))))
38. Սահմանել ֆունկցիա, որը վերադարձնում է տրված ցուցակի զույգ տարրերի գումարը:
(defun sum-of-evens (x)
        (if (endp x)
            0
            (if (evenp (car x))
                (+ (car x) (sum-of-evens (cdr x)))
                (sum-of-evens (cdr x)))))
39. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակի զույգ տարրերի ցուցակը:
(defun list-of-evens (x)
   (cond 
       ((endp x) '())
       ((evenp (car x)) (cons (car x) (list-of-evens (cdr x))))
       (t (list-of-evens (cdr x)))))
40. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակի կենտ տարրերի գումարը:
(defun sum-of-odds (x)
   (cond
       ((endp x) 0)
       ((oddp (car x)) (+ (car x) (sum-of-odds (cdr x))))
       (t (sum-of-odds (cdr x)))))
41. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակի կենտ տարրերի ցուցակը:
(defun list-of-odds (x)
   (cond
       ((endp x) '())
       ((oddp (car x)) (cons (car x) (list-of-odds (cdr x))))
       (t (list-of-odds (cdr x)))))
42. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակի դրական տարրերի քանակը:
(defun count-positivs (x)
   (cond
       ((endp x) 0)
       ((plusp (car x)) (1+ (count-positivs (cdr x))))
       (t (count-positivs (cdr x)))))
43. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակի դրական տարրերի ցուցակը:
(defun list-of-positivs (x)
   (cond
       ((endp x) '())
       ((plusp (car x)) (cons (car x) (list-of-positivs (cdr x))))
       (t (list-of-positivs (cdr x)))))
44. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակի ոչ զրոյական տարրերի քանակը:
(defun count-non-zeros (x)
   (cond
       ((endp x) 0)
       ((not (zerop (car x))) (1+ (count-non-zeros (cdr x))))
       (t (count-non-zeros (cdr x)))))
45. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակի ոչ զրոյական տարրերի ցուցակը:
(defun list-of-non-zeros (x)
   (cond
       ((endp x) '())
       ((not (zerop (car x))) (cons (car x) (list-of-non-zeros (cdr x))))
       (t (list-of-non-zeros (cdr x)))))
46. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակի ամենամեծ տարրը:
(defun maximum (x)
   (if (endp (cdr x))
       (car x)
       (let ((m (maximum (cdr x)))
      (c (car x)))
  (if (> c m) c m))))
47. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակի ամենափոքր տարրը:
(defun minimum (x)
   (if (endp (cdr x))
       (car x)
       (let ((m (minimum (cdr x)))
      (c (car x)))
  (if (< c m) c m))))
48. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) ոչ գծային ցուցակի ամենամեծ տարրը:
(defun max-list (x)
   (flet ((max-2 (a b) (if (> a b) a b)))
       (let ((a (car x)) (d (cdr x)))
           (if (endp d)
               (if (atom a) a (max-list a))
               (max-2 (if (atom a) a (max-list a)) (max-list d))))))
49. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) ոչ գծային ցուցակի ամենափոքր տարրը:
(defun min-list (x)
   (flet ((min-2 (a b) (if (< a b) a b)))
       (let ((a (car x)) (d (cdr x)))
           (if (endp d)
               (if (atom a) a (min-list a))
               (min-2 (if (atom a) a (min-list a)) (min-list d))))))
50. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակի ոչ զրոյական տարրերից ամենամեծը:
(defun max-non-zero (x)
    (maximum (list-of-non-zeros x)))
51. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակում \(y\)-ից մեծ և \(z\)-ին պատիկ թվերի քանակը:
(defun ex51 (x y z)
   (if (endp x)
       0
       (if (and (> (car x) y) (zerop (mod (car x) z)))
           (1+ (ex51 (cdr x) y z))
           (ex51 (cdr x) y z))))
52. Սահմանել ֆունկցիա, որը վերադարձնում է բնական թվերի \(x\) գծային ցուցակում \(y\)-ից մեծ և \(z\)-ին պատիկ թվերի ցուցակը:
(defun ex52 (x y z)
   (if (endp x)
       '()
       (if (and (> (car x) y) (zerop (mod (car x) z)))
           (cons (car x) (ex52 (cdr x) y z))
           (ex52 (cdr x) y z))))
53. Սահմանել ֆունկցիա, որը վերադարձնում է տրված \(x\) ցուցակի ատոմների քանակը (ցուցակը կարող է լինել նաև ոչ գծային):
(defun count-atoms (x)
   (cond
      ((endp x) 0)
      ((atom (car x)) (1+ (count-atoms (cdr x))))
      (t (+ (count-atoms (car x)) (count-atoms (cdr x))))))
54. Սահմանել ֆունկցիա, որը վերադարձնում է տրված ոչ գծային ցուցակի ատոմների ցուցակը:
(defun list-of-atoms (x)
   (cond
      ((endp x) '())
      ((atom (car x)) (cons (car x) (list-of-atoms (cdr x))))
      (t (append (list-of-atoms (car x)) (list-of-atoms (cdr x))))))
55. Սահմանել ֆունկցիա, որը վերադարձնում է տրված գծային ցուցակի \(n\)-րդ տարրը: Եթե ցուցակի երկարությունը փոքր է \(n\)-ից, ապա վերադարձնել ցուցակի երկարությունը՝ գումարած \(1\):
(defun n-th-elem (l n)
  (labels
    ((n-th-rec (j m)
        (cond
            ((endp j) (1+ m))
            ((= n m) (car j))
            (t (n-th-rec (cdr j) (1+ m))))))
    (n-th-rec l 0)))
56. Տարրական ֆունկցիաներով ծրագրավորել երկու ցուցակների միակցումը վերադարձնող ֆունկցիան:
(defun append-2 (x y)
    (if (endp x)
        y
        (cons (car x) (append-2 (cdr x) y))))
57. Սահմանել ֆունկցիա, որը վերադարձնում է տրված ցուցակի վերջին տարրը:
(defun last-elem (l)
    (if (endp (cdr l))
        (car l)
        (last-elem (cdr l))))
58. Սահմանել ֆունկցիա, որը տրված \(x\) ցուցակին աջից կցում է տրված \(y\) ատոմը:
(defun add-right (x y)
    (if (endp x)
        (cons y '())
        (cons (car x) (add-right (cdr x) y))))
59. Սահմանել պրեդիկատ, որը ստուգում է տրված \(e\) ատոմը գոյությունը \(l\) գծային ցուցակում:
(defun contains (l e)
    (cond
        ((endp l) nil)
        ((equal (car l) e) t)
        (t (contains (cdr l) e))))
60. Սահմանել պրեդիկատ, որը ստուգում է տրված \(e\) տարրի գոյությունը \(l\) ոչ գծային ցուցակում:
(defun contains-nl (l e)
   (if (endp l)
       nil
       (let ((a (car l)) (d (cdr l)))
         (or (if (atom a) 
                 (equal a e)
                 (contains-nl a e))
             (contains-nl d e)))))
61. Սահամնել ֆունկցիա, որը վերադարձնում է \(l\) ցուցակում \(e\) տարրի դիրքը: Եթե \(e\)-ն ցուցակում բացակայում է, ապա վերադարձնել ցուցակի երկարությունը՝ գումարած \(1\):
(defun elem-pos (l e)
  (labels
      ((elem-pos-rec (j m)
          (cond
             ((endp j) (1+ m))
             ((equal (car j) e) m)
             (t (elem-pos-rec (cdr j) (1+ m))))))
    (elem-pos-rec l 0)))
62. Սահմանել ֆունկցիա, որը վերադարձնում է \(l\) ցուցակում \(e\) տարրին հաջորդող տարրը: եթե այդպիսին չկա, վերադարձնել nil:
(defun next-elem (l e)
    (cond
        ((or (endp l) (endp (cdr l))) nil)
        ((equal (car l) e) (cadr l))
        (t (next-elem (cdr l) e))))
63. Սահմանել ֆունկցիա, որը վերադարձնում է \(l\) ցուցակում \(e\) տարրերի քանակը:
(defun count-elem (l e)
    (cond
        ((endp l) 0)
        ((equal (car l) e) (1+ (count-elem (cdr l) e)))
        (t (count-elem (cdr l) e))))
64. Սահմանել ֆունկցիա, որը վերադարձնում է \(l\) ցուցակի շրջված ցուցակը:
(defun rev-list (l)
  (labels
      ((rev-rec (l r)
  (if (endp l)
      r
      (rev-rec (cdr l) (cons (car l) r)))))
    (rev-rec l '())))
65. Սահմանել ֆունկցիա, որը աճման կարգով կարգավորված բնական թվերի \(l\) ցուցակում ավելացնում է \(e\) տարրը:
(defun insert-elem (l e)
  (if (endp l)
      (cons e '())
      (if (< e (car l))
   (cons e l)
   (cons (car l) (insert-elem (cdr l) e)))))
66. Սահմանել ֆունկցիա, որը վերադարձնում է տրված ցուցակը՝ կարգավորված ըստ տարրերի արժեքների աճման:
(defun insertion-sort (x)
    (if (endp l)
        '()
        (insert-elem (insertion-sort (cdr x)) (car x))))
67. Սահմանել ֆունկցիա, որը վերադարձնում է տրված ցուցակը՝ կարգավորված ըստ տարրերի արժեքների նվազման:
(defun sort-desc (x)
    (rev-list (insertion-sort x)))
68. Սահմանել ֆունկցիա, որը հեռացնում է տրված ցուցակի վերջին տարրը:
(defun rem-last (x)
    (if (or (endp x) (endp (cdr x)))
        '()
        (cons (car x) (rem-last (cdr x)))))
69. Սահմանել ֆունկցիա, որը հեռացնում է տրված ցուցակում առաջին զույգ թվին հաջորդող տարրը:
(defun rem-next-to-even (x)
  (cond
    ((endp x) '())
    ((evenp (car x)) (cons (car x) (cddr x)))
    (t (cons (car x) (rem-next-to-even (cdr x))))))
70. Սահմանել ֆունկցիա, որը տրված ցուցակում բոլոր կենտ թվերը փոխարինում է իրենց քառակուսով:
(defun odd-to-sqr (x)
  (if (endp x)
      '()
      (let ((a (car x)) (d (cdr x)))
        (cons (if (oddp a) (* a a) a) (odd-to-sqr d)))))
71. Սահմանել ֆունկցիա, որը տրված ցուցակում բոլոր զույգ դիրքերում կանգնած \(a\)-երը փոխարինում է \(b\)-երով:
(defun ex71 (x a b)
  (if (or (endp x) (endp (cdr x)))
      '()
      (cons (car x) 
        (cons (if (equal (cadr x) a) b (cadr x)) 
              (ex71 (cddr x) a b)))))
72. Սահմանել ֆունկցիա, որը սիմվոլների \(x\) գծային ցուցակում \(y\) սիմվոլի բոլոր մուտքերը պատճենում է:
(defun ex72 (x y)
  (if (endp x)
      '()
      (if (equal (car x) y) 
          (append (list y y) (ex72 (cdr x) y))
          (cons (car x) (ex72 (cdr x) y)))))
73. Սահմանել պրեդիկատ, որը ստուգում է արդյոք տրված ցուցակը կազմված է nil-ից տարբեր ատոմներից:
(defun no-nils (x)
  (if (endp x)
      t
      (and (not (null (car x)))
           (no-nils (cdr x)))))
74. Սահմանել ֆունկցիա, որը սիմվոլներից կազմված \(x\) գծային ցուցակում բոլոր a-երը փոխարինում է b-երով:
(defun ex74 (x a b)
  (if (endp x)
      '()
      (cons (if (eq (car x) a) b (car x))
            (ex74 (cdr x) a b))))
75. Սահմանել պրեդիկատ, որը ստուգում է տրված ցուցակի գծային լինելը:
(defun linear-p (x)
  (if (endp x)
      t
      (and (atom (car x)) (linear-p (cdr x)))))
76. Սահմանել ֆունկցիա, որը տրված \(x\) գծային ցուցակից ստանում է նոր ցուցակ հետևյալ կերպ.
(a b c) -> (((c) b) a)
(defun ex76 (x)
  (cond 
    ((endp x) (print x) '())
    ((endp (cdr x)) (cons (car x) '()))
    (t (list (ex76 (cdr x)) (car x)))))
77. Սահմանել ֆունկցիա, որը տրված \(x\) գծային ցուցակից ստանում է նոր ցուցակ հետևյալ կերպ.
(a b c) -> (a (b (c)))
(defun ex77 (x)
  (cond 
    ((endp x) (print x) '())
    ((endp (cdr x)) (cons (car x) '()))
    (t (list (car x) (ex77 (cdr x))))))
78. Սահմանել ֆունկցիա, որը տրված \(x\) գծային ցուցակից ստանում է նոր ցուցակ հետևյալ կերպ.
(a b c) -> (((a) b) c)
(defun ex78 (x)
  (ex76 (reverse x)))
79. Սահմանել ֆունկցիա, որը տրված \(x\) գծային ցուցակից ստանում է նոր ցուցակ հետևյալ կերպ.
(((a) b) c) -> (a b c)
(defun ex79 (x)
  (if (atom x)
      (cons x '())
      (append (ex79 (car x)) (cdr x))))
80. Սահմանել ֆունկցիա, որը տրված \(x\) և \(y\) գծային ցուցակներից ստանում է նոր ցուցակ հետևյալ կերպ.
(a b c),(1 2 3) -> ((a 1)(b 2)(c 3))
(defun zip (x y)
  (if (or (endp x) (endp y))
      '()
      (cons (list (car x) (car y))
            (zip (cdr x) (cdr y)))))
81. Սահմանել ֆունկցիա, որը տրված \(x\) գծային ցուցակից ստանում է նոր ցուցակ հետևյալ կերպ.
(a b c d e f) -> ((a b)(c d)(e f))
(a b c d e) -> ((a b)(c d)(e nil))
(defun zip-2 (x)
  (if (endp x)
      '()
      (cons (list (car x) (cadr x))
            (zip-2 (cddr x)))))
82. Սահմանել ֆունկցիա, որը վերադարձնում է \(x\) ցուցակի խորությունը:
  
(defun depth-1 (x)
  (if (or (not (listp x)) (null x))
      0
      (1+ (apply #'max (mapcar #'depth-1 x)))))
83. Սահմանել ֆունկցիա, որը վերադարձնում է \(x\) ոչ գծային ցուցակի խորությունը:
(defun depth-2 (x)
  (if (atom x)
      0
      (1+ (apply #'max (mapcar #'depth-2 x)))))
84. Սահմանել տրված ցուցակի սիմետրիկությունը ստուգող պրեդիկատ:
(defun palindrome-p (x)
  (equal (reverse x) x))

(defun palindrome-p-2 (x) (print x)
  (if (or (endp x) (endp (cdr x)))
      t
      (and (equal (first x) (car (last x)))
           (palindrome-p-2 (butlast (cdr x))))))
85. Սահմանել պրեդիկատ, որը ստուգում է արդյոք \(x\) ցուցակը \(y\) ցուցակի սկիզբն է:
(defun prefix-p (x y)
  (if (endp y)
      t
      (and (equal (car x) (car y))
           (prefix-p (cdr x) (cdr y)))))
86. Սահմանել ֆունկցիա, որը տրված \(x\) ցուցակի սկզբից հեռացնում է \(y\) ցուցակին համապատասխանող տարրերը:
(defun ex86 (x y)
  (if (prefix-p x y)
      (nthcdr (list-length y) x)
      x))
87. Սահմանել պրեդիկատ, որը ստուգում է արդյոք տրված \(x\) ցուցակը \(y\) ցուցակի իտերացիան է:
(defun ex87 (x y)
  (if (equal x y)
      t
      (if (prefix-p x y)
          (ex87 (nthcdr (list-length y) x) y)
          nil)))
88. Սահմանել ֆունկցիա, որն արգումենտում ստանում է ինֆիքսային տեսքով գրված արտահայտություն (ցուցակի տեսքով, առանց հաշվի առնելու գործողությունների առաջայնությունը, բոլոր գործողություները երկտեղանի են) և վերադարձնում է նրա արժեքը:
((-2 + 4) * 3) -> 6
(-2 + (4 * 3)) -> 10
((-2 > 0) and (3 < 5)) -> t
-2 -> -2
(defun calc (x)
  (flet
    ((func-op (op)
       (case op
         ((and) #'(lambda (a b) (and a b)))
         ((or) #'(lambda (a b) (or a b)))
         (t op))))
   (if (atom x)
       x
      (funcall (func-op (second x))
               (calc (first x))
               (calc (third x))))))

Խնդիրներ բազմությունների վերաբերյալ

89. Սահմանել is-in պրեդիկատը, որը վերադարձնում է t, եթե yx բազմության տարր է: Հակառակ դեպքում վերադարձնում է nil:
(defun is-in (y x)
  (if (endp x)
      nil
      (or (equal (car x) y) (is-in y (cdr x)))))
90. Սահմանել is-set պրեդիկատը, որը ստուգում է տրված ցուցակի բազմություն լինելը:
(defun is-set (x)
  (if (endp x)
      t
      (and (not (is-in (car x) (cdr x)))
           (is-set (cdr x)))))
91. Սահմանել list-to-set ֆունկցիան, որը վերադարձնում է տրված գծային ցուցակի տարրերի բազմությունը:
(defun list-to-set (x)
  (cond
    ((endp x) '())
    ((member (car x) (cdr x)) (list-to-set (cdr x)))
    (t (cons (car x) (list-to-set (cdr x))))))
92. Սահմանել list-set ֆունկցիան, որը վերադարձնում է տրված ոչգծային ցուցակի տարրերի բազմությունը:
(defun tree-to-set (x)
  (labels
     ((flatten (y)
       (cond
         ((null y) '())
         ((atom y) (list y))
         (t (mapcan #'flatten y)))))
    (list-to-set (flatten x))))
93. Սահմանել set-of-evens ֆունկցիան, որը վերադարձնում է տրված \(X\) բնական թվերի ցուցակի զույգ տարրերի բազմությունը:
(defun set-of-evens (x)
  (remove-duplicates (remove-if #'oddp x)))

(defun set-of-evens-1 (x)
  (if (endp x)
      '()
      (let ((head (car x))
            (tail (set-of-evens-1 (cdr x))))
        (if (and (evenp head) (not (member head tail)))
            (cons head tail)
            tail))))
94. Սահմանել set-not-zero ֆունկցիան, որը վերադարձնում է տրված \(X\) բնական թվերի ցուցակի ոչզրոյական տարրերի բազմությունը:
        
(defun set-not-zero (x)
  (remove-duplicates (remove-if #'zerop x)))
95. Սահմանել lonion ֆունկցիան, որը վերադարձնում է տրված երկու բազմությունների միավորումը:
      
(defun lunion (x y)
  (cond
    ((endp x) y)
    ((member (car x) y) (lunion (cdr x) y))
    (t (cons (car x) (lunion (cdr x) y)))))
96. Սահմանել union-of-odds ֆունկցիան, որը վերադարձնում է տրված երկու բազմությունների կենտ տարրերի ենթաբազմությունների միավորումը:
(defun union-of-odds (x y)
  (union (remove-if-not #'oddp x) (remove-if-not #'oddp y)))
97. Սահմանել lintersection ֆունկցիան, որը վերադարձնում է տրված երկու բազմությունների հատումը:
(defun lintersection (x y)
  (cond
    ((or (endp x) (endp y)) '())
    ((member (car x) y) (cons (car x) (lintersection (cdr x) y)))
    (t (lintersection (cdr x) y))))
98. Սահմանել ֆունկցիա, որը վերադարձնում է տրված երկու բազմությունների թիվ հանդիսացող ատոմների հատումը:
(defun ex98 (x y)
  (intersection (remove-if-not #'numberp x)
                (remove-if-not #'numberp y)))
99. Սահմանել ֆունկցիա, որը վերադարձնում է տրված երկու բազմությունների տարբերությունը:
(defun ldifference (x y)
  (cond
    ((endp x) '())
    ((endp y) x)
    ((member (car x) y) (ldifference (cdr x) y))
    (t (cons (car x) (ldifference (cdr x) y)))))
100. Սահմանել ֆունկցիա, որը վերադարձնում է տրված երկու բազմությունների սիմետրիկ հանումը:
(defun sim-diff (x y)
  (set-difference (union x y) (intersection x y)))
101. Սահմանել երկու բազմությունների դեկարտյան արտադրյալը վերադարձնող ֆունկցիա:
(defun cartesian (x y)
  (if (endp x)
      '()
      (append (mapcar #'(lambda (e) (list (car x) e)) y)
              (cartesian (cdr x) y))))
102. Սահմանել պրեդիկատ, որը ստուդում է երկու բազմությունների հատվող լինելը:
(defun are-intersect (x y)
  (if (endp x)
      nil
      (or (member (car x) y) (are-intersect (cdr x) y))))

(defun are-intersect-2 (x y)
  (not (null (intersection x y))))
103. Սահմանել պրեդիկատ, որը ստուդում է երկու բազմությունների չհատվող լինելը:
(defun are-not-intersect (x y)
    (null (intersection x y)))
104. Սահմանել is-subset ֆունկցիան, որը ստուգում է. արդյոք տրված \(X\) բազմությանը \(Y\) բազմության ենթաբազմություն է:
(defun is-subset (x y)
  (if (endp x)
      t
      (and (member (car x) y) (is-subset (cdr x) y))))
105. Սահմանել is-own-subset ֆունկցիան, որը ստուգում է. արդյոք տրված \(X\) բազմությանը \(Y\) բազմության սեփական ենթաբազմություն է:
(defun is-own-subset (x y)
    (and (is-subset x y) (> (list-length y) (list-length x))))

Monday, March 31, 2014

Java և Kawa: Տեքստի տրոհումը Scanner դասի օգնությամբ

Շարունակելով բլոգիս «Tcl: Բառարանների օգտագործումը», «Python: Բառարանի օգտագործումը» և «C++11: Տեքստի տրոհումը բառերի՝ istream-ի միջոցով» գրառումների թեման, ես ուզում էի այս գրառմանս մեջ պատմել Java լեզվի միջոցներով տեքստը բառերի տրոհելու և բառերի հաճախությունը հաշվելու մասին։ Ինձ գայթակղեց Java-ի Scvanner դասը, որը կարելի է կանոնավոր արտահայտությունների միջոցով կարգավորել տեքստից բառեր կարդալու համար։ Բայց այս գրառման մեջ ուզում եմ նաև Java-ի HashMap բառարանի օգտագործումը համեմատ ել JVM վիրտուալ մեքենայով աշխատող GNU Kawa լեզվի (Scheme լեզվի իրականացում) hashtable բառարանի օգտագործման հետ։

Նախ ներկայացնեմ Java տարբերակը (օգտագործված է JDK 8-ը)։
package wordcount;

import java.io.File;
import java.io.FileNotFoundException;
import java.util.HashMap;
import java.util.Scanner;

/**/
public class WordCount {
  /**/
  private static void readFile( String name, HashMap<String,Integer> words )
  {
    // տրված անունով ֆայլի համար ստեղծել Scanner օբյեկտ
    try( Scanner scan = new Scanner(new File(name)) ) {
      // բացի մեծատառերից ու փոքրատառերից ամեն ինչ համարել բաժանիչ
      scan.useDelimiter( "[^A-Za-z]+" );
      // քանի դեռ Scanner-ից կարելի է կարդալ
      while( scan.hasNext() ) {
        // կարդալ հերթական բառը
        String wo = scan.next().toLowerCase();
        // գտնել կարդացած բառի արտապատկերումը բառարանում
        Integer co = words.get(wo);
        // եթե այդ բառը բառարանում չկա, ավելացնել այն՝ 1 քանակով, 
        // իսկ եթե կա՝ քանակն ավելացնել 1-ով
        words.put(wo, co == null ? 1 : co + 1);
      }
    }
    catch( FileNotFoundException ex ) {
      System.err.println(ex.getMessage());
    }
  }
    
  /**/
  public static void main(String[] args) 
  {
    // ստեղծել String->Integer արտապատկերում
    HashMap<String,Integer> words = new HashMap<>();
    // կարդալ ֆայլի պարունակությունը words բառարանի մեջ
    readFile("~/Projects/martineden.txt", words);
    // բառ-քանակ զույգերն արտածել ստանդարտ արտածման հոսքին
    words.forEach( (k,v) -> System.out.printf("%s\t%s\n", k, v) );
  }
}
* *
Kawa լեզուն JVM վիրտուալ մեքենայի համար գրված բազմաթիվ լեզուներից մեկն է։ Բայց ինձ համար հետաքրքիր է նրանով, որ այն Lisp լեզվի Scheme դիալեկտի իրականացում է Java լեզվով։ Ամբողջովին գրված լինելով Java լեզվով՝ այն ա) պլատֆորմից անկախ է, և բ) հնարավորություն ունի օգտագործել Java լեզվի ստանդարտ գրադարանը՝ այն ամենը, ինչ մատչելի է JVM կատարման միջավայրում։

Հիմա ցույց տամ, թե ինչպես եմ Kawa լեզվի միջոցներով կարդում ֆայլի բառերի հաջորդականությունը և կազմում դրանց հաճախությունների բառարանը։ Նախ սահմանեմ read-all-words ֆունկցիան, որն արգումենտում ստանում է Java լեզվի Scanner օբյեկտը և վերագարձնում է տեքստի բառերի հաճախությունների բառարանը՝ որպես Scheme լեզվի hashtable օբյեկտ։
(define (read-all-words sca :: Scanner)
  (define (read-all-words-rec ht)
    (when (invoke sca 'hasNext)
      (add-to-table (string-downcase (invoke sca 'next)) ht)
      (read-all-words-rec ht)))
  (let ((words (make-hashtable string-hash string=?)))
    (read-all-words-rec words)
    words))
read-all-words ֆունկցիայի համար սահմանված է read-all-words-rec լոկալ ռեկուրսիվ ֆունկցիան, որը Scanner օբյեկտից կարդում է մեկ բառ, այդ բառի բոլոր մեծատառերը դարձնում է փոքրատառ՝ string-downcase ֆունկցիայով, ապա ավելացնում է արգումենտում տրված բառարանում։ Բառարանը ստեղծվում է որպես read-all-words ֆունկցիայի լոկալ օբյեկտ՝ make-hashtable ֆունկցիայով։ Բառը բառարանում ավելացնող add-to-table ֆունկցիան սահմանված է հետևյալ կերպ․
(define (add-to-table w table)
  (let ((co (hashtable-ref table w 0)))
    (hashtable-set! table w (+ co 1))))
read-file ֆունկցիան, որ կսահմանեմ ստորև, տրված ֆայլի անունի համար ստեղծում է մի Scanner օբյեկտ և "[^A-Za-z]+" արտահայտությունը սահմանում է որպես դրա բաժանիչ։ Հետո read-all-words ֆունկցիայով ստանում է բառերի հաճախությունների բառարանը, այդ բառարանից կազմում է կետով զույգերի (dotted pair) ցուցակ, և վերադարձնում է այդ վերջին ցուցակն՝ ըստ բառերի այբբենական կարգի կարգավորած։
(define (read-file name :: )
  (let ((sca (Scanner:new (File:new name))))
    (invoke sca 'useDelimiter "[^A-Za-z]+")
    (let-values (((ks vs) (hashtable-entries (read-all-words sca))))
      (invoke sca 'close)
      (list-sort (lambda (a b) (stringlist ks) (vector->list vs))))))
* *
Ինձ դուր է գալիս Lisp լեզվով ծրագրավորումը։ Բայց ինձ դուր է գալիս նաև Java լեզվի գրադարանները։ Kawa իրականացումը հնարավորություն է տալիս մեկտեղել երկու դուրեկան բան :)

Friday, March 21, 2014

Java: Անանուն ֆունկցիաները Java 8 լեզվում

Պատահաբար հանդիպեցի Java 8 լեզվում անանուն ֆունկցիաների իրականացման մասին Oracle ֆիրմայի մի հաղորդագրության։ Այդտեղ օրինակներ էր բերված, թե ինչ նպատակների համար են նախատեսված Java 8 լեզվի լյամբդա ֆունկցիաները, և թե ինչպես կարելի է օգտագործել դրանք։
     Իմ բլոգի «Բարձր կարգի ֆունկցիաներ և անանուն ֆունկցիաներ» գրառման մեջ ես ֆունկցիայի ինտեգրալի թվային հաշվման օրինակով համեմատել էի Common Lisp և C++11 լեզվի անանուն ֆունկցիաները։ Այս գրառման մեջ ուզում եմ նույն այդ օրինակը ցույց տալ Java 8 լեզվի անանուն ֆունկցիաների օգտագործմամբ։

Մաթեմատիկական ֆունկցիան, որ կարելի է ինտեգրել, իրականացնում է MathFunc ինտերֆեյսը։ Այն սահմանված է MathFunc.java ֆայլում։
package integral;

public interface MathFunc {
 public double apply( double x );
}
Թվային ինտեգրման մեթոդն իրականացնում է Method ինտերֆեյսը, որը սահմանված է Method.java ֆայլում՝ հետևյալ կերպ։
package integral;

public interface Method {
 public double apply( MathFunc f, double a, double b );
}
Սահմանեմ Integral դասը և սահմանեմ այդ դասի evaluate մեթոդը, որն արգումենտում սպասում է ինտեգրման մեթոդը, ինտեգրվող ֆունկցիան, ինտեգրման միջակայքը և միջակայքի՝ հատվածների տրոհման գործակիցը։ Հաշվելու եղանակը պարզագույնն է. meth օբյեկտի apply մեթոդին են փոխանցվում ինտեգրվող ֆունկցիան և այն փոքր հատվածը, որի վրա նշված թվային մեթոդով հաշվվում է ինտեգրալը։
package integral;

public class Integral {
    public static double evaluate(Method meth, MathFunc func, 
                                double left, double right, double epsilon)
    {
        double result = 0.0;
        for( double x = left; x < right; x += epsilon )
            result += meth.apply(func, x, x + epsilon);
        return result;
    }
}
Որպեսզի, օրինակ, Integral դասի evaluate ստատիկ մեթոդի օգնությամբ հաշվեմ \(f(x)=3x^2-2x+1\) ֆունկցիայի ինտեգրալը, պետք է նախ՝ \(f(x)\) ֆունկցիան սահմանեմ որպես MathFunc ինտերֆեյս իրականացնող օբյեկտ, իսկ ինտեգրման մեթոդը, օրինակ սեղանների կանոնը, սահմանեմ որպես Method ինտերֆեյսն իրականացնող օբյեկտ։
     Սահմանեմ Calc դասը՝ main մուտքի կետով։
package integral;

public class Calc {
    /**/ 
    public static void main( String[] args )
    {
        // ինտեգրման մեթոդ
        Method Simple = new Method() {
            @Override
            public double apply( MathFunc f, double a, double b )
            { return (b - a) * f.apply((b + a) / 2); }
        };

        // ինտեգրվող ֆունկցիա 
        MathFunc Sin = new MathFunc() {
            @Override
            public double apply( double x )
            { return 3*x*x - 2*x + 1; }
        };

        // ինտեգրալի հաշվումն ու արտածումը
        double r0 = Integral.evaluate(Simple, Sin, 0, 1, .0001);
        System.out.println( r0 );
    }
}
Բայց սա հնացած եղանակն է։ Անանուն ֆունկցիաների օգտագործմամբ գրվում է շատ ավելի համառոտ, գեղեցիկ ու հասկանալի կոդ։ Ստորև բերված main ֆունկցիայում ինտեգրման մեթոդն ու ինտեգրվող ֆունկցիան evaluate ֆունկցիային փոխանցված են որպես անանուն ֆունկցիաներ։
package integral;

public class Calc {
    /**/ 
    public static void main( String[] args )
    {
        double r1 = Integral.evaluate( (f,a,b)->(b-a)*f.apply((b+a)/2), 
                                       (x)-> 3*x*x - 2*x + 1, 0, 1, .0001 );
        System.out.println( r1 );
    }
}
* * *
Java 8 լեզվում անանուն (լյամբդա) ֆունկցիան սահմանվում է հետևյալ քերականությամբ․

(արգումենտների ցուցակ) -> ֆունկցիայի մարմին

Օրինակ, թվային մոտավոր ինտեգրման սեղանների կանոնի բանաձևը վերը բերված օրինակում սահմանված է ահա այսպես․
(f, a, b) -> (b - a) * f.apply((b + a) / 2)
Կարելի է անանուն ֆունկցիան կապել որևէ փոփոխականի հետ, օրինակ, թվային մոտավոր ինտեգրման Սիմպսոնի կանոնի բանաձևը սահմանված է որպես անանուն ֆունկցիա և վերագրված է simpson փոփոխականին․
public static Method simpson = 
   (f, a, b) -> ((b - a) / 6) * (f.apply(a) + f.apply(b) + 4*f.apply((a+b)/2));
Ինտեգրալը հաշվելիս կարելի է evaluate ֆունկցիային փոխանցել simpson փոփոխականը․
double r2 = Integral.evaluate( simpson, (x)-> 3*x*x - 2*x + 1, 0, 1, .0001 );

Առայժմ այսքանը։ Ես դեռ նոր եմ ուսումնասիրում Java 8-ի անանուն ֆունկցիաները։ Հետքգայում միգուցե նորից անդրադառնամ այս թեմային ու ներկայացնեմ ավելի հետաքրքիր օրինակներ։

Thursday, March 20, 2014

C++11: Տեքստի տրոհումը բառերի՝ istream-ի միջոցով

Իմ բլոգի գրառումներում արդեն երկու անգամ անդրադարձել եմ տրված տեքստի բառերի հաճախության աղյուսակի կառուցման խնդրին։ Մի անգամ Tcl լեզվով և մի անգամ էլ Python լեզվով։ Այս անգամ որոշել էի նույն խնդիրը գրել C++11 լեզվով՝ այդ լեզվի հնարավորություններն ուսումնասիրելու համար։

Խնդիրը բաղկացած է երկու մասից ա) տրված տեքստը տրոհել բառերի, և բ) հաշվել տեքստում ամեն մի բառի հանդիպելու հաճախությունը։

Ֆայլից սիմվոլ առ սիմվոլ տեքստը կարդալու և բառեր կազմելու հավես ես չունեի։ C լեզվի գրադարանային strtok ֆունկցիան էլ տարբեր պատճառներով չէի ուզում օգտագործել։ Նպատակ ունեի օգտագործել C++ լեզվի istream դասը և այդ դասի համար սահմանված operator>> գործողությունը։ Ավելի պարզ ասած, ուզում էի, որ հետևյալ read_file ֆունկցիան filename ֆայլից կկարդա բառերը և կլցնի words վեկտորի մեջ.
void read_file( char* filename, std::vector<std::string>& words )
{
  std::string w{ "" };
  std::ifstream fin{ filename };
  while( !fin.eof() ) {
    fin >> w;
    words.push_back( w );
  }    
  fin.close();
}
Բայց պարզ է, որ words վեկտորը պարզապես լցվելու է տեքստի՝ բացատներով բաժանված հատվածներով, որովհետև լռելությամբ operator>> գործողությունը բաժանիչ (delimiter) է համարում միայն բացատները։
     Իմ խնդրի համար բաժանիչ պետք է համարել այբուբենի մեծատառերից ու փոքրատառերից տարբերովող բոլոր նիշերը։ Եվ istream դասի օբյեկտը պետք է մի որևէ եղանակով կարգավորել այնպես, որ բաժանիչ համարվեն և անտեսվեն բոլոր ոչ պետքական նիշերը։      Ինտերնետում քչփորելուց հետո հասկացա, որ իմ ուզած բաժանիչները սահմանելու համար պետք է ստեղծեմ նոր locale օբյեկտ։ Հետո այդ locale-ի համար էլ սահմանեմ այնպիսի ctype ֆասետ (facet - սրա անունը այդպես էլ չհասկացա), որում արդեն այբուբենի տառերից տարբերվող նիշերին տրված է space դիմակը (mask)։ Ահա այդ նոր սահմանված դասը, որ ժառանգած է std::ctype<char>-ից։
class word_ctype : public std::ctype<char> {
private:
  static const mask* custom_table()
  {
    mask* wcs = new mask[table_size];
    std::copy_n(classic_table(), table_size, wcs);
    for( int c = 32; c < table_size; ++c ) {
      if( isalpha(c) ) continue;
      wcs[c] = (mask)space;
    }
    return wcs;
  }
public:
  word_ctype( std::size_t refs = 0 )
    : ctype(custom_table(), true, refs)
  {}
};
Հետո արդեն ավելի հետաքրքիր մասն է։ Սահմանեցի create_dictionary ֆունկցիան, որի առաջին արգումենտը վերլուծվող ֆայլի անունն է, իսկ երկրորդը՝ կառուցվելիք բառարանի ֆայլի անունն է։ Ստացվեց համարյա ֆունկցիոնալ կոդ։
void create_dictionary( char* infile, char* outfile )
{
  // բառարան է, որը հաշվում է ամեն մի բառի քանակը
  std::map<std::string,int> dict;
  // ընթերցման հոսքի ստեղծում՝ տրված ֆայլի անունով
  std::ifstream fin{infile};
  // ընթերցման հոսքում ներդնել նոր locale օբյեկտ՝ վերը սահմանված facet-ով
  fin.imbue(std::locale{std::locale::classic(), new word_ctype});
  // հոսքից կարդալու երկու իտերատորներ
  std::istream_iterator sbegin(fin), send;
  // կարդալ հոսքը սկզբից մինչև վերջ և բառերն ավելացնել բառարանում
  std::for_each( sbegin, send, [&dict](std::string w){ ++dict[downcase(w)]; } );
  fin.close();
  
  // ստեղծել արտածման հոսք՝ բառարանը գրելու համար
  std::ofstream fout{outfile};
  // բառարանի ամեն մի գրառման համար ...
  for( auto w : dict )
    // ֆայլում գրել բառը և նրա քանակը
    fout << w.first << ',' << w.second << std::endl;
  fout.close();
}
Այս ֆունկցիայում հոսքից կարդացած բառի բոլոր տառերը փոքրատառ դարձնելու համար օգտագործված downcase ֆունկցիան սահմանված է հետևյալ կերպ։
std::string downcase( std::string sr )
{
  std::transform( sr.begin(), sr.end(), sr.begin(), ::tolower );
  return sr;
}

Thursday, March 13, 2014

Հայերեն LaTeX

Այս գրառման մեջ ուզում եմ մի քանի խոսքով պատմել այն մասին, թե ինչպես եմ ես LATEX համակարգի օգտագործմամբ պատրաստում հայերեն փաստաթղթեր։

Որպես LATEX իրականացում օգտագործում եմ xetex իրականացման xelatex ծրագիրը։ Այդ իրականացումը նախագծված է Unicode տեքստերի հետ աշխատելու համար և օգտագործում է համակարգում տեղադրված Unicode տառատեսակները։

LATEX-ն օգտագործում է երեք տեսքի տառատեսակներ՝ serif, sans և mono։ Լռելությամբ օգտագործվում են Computer Modern ընտանիքի տառերը, որոնցում չկան հայերենի այբուբենի տառերի պատկերները։ Համակարգում տեղադրված տառատեսակներն օգտագործելու համար նախ՝ հարկավոր է «ձեռագրի» ֆայլում հայտարարել, որ օգտագործվելու է fontspec փաթեթը։
\usepackage{fontspec}
Այնուհետև \setmainfont, \setsansfont և \setmonofont հրամաններով ընտրել serif, sans և mono տեսքերի համար օգտագործվող տառատեսակները։ Օրինակ, DejaVu ընտանիքի տառատեսակների հայերեն Unicode հատվածում կան հայերեն տառերի պատկերները։ Դա նշանակում է, որ հայերեն տեքստեր պատրաստելու համար կարելի է գրել հետևյալը.
\setmainfont{DejaVu Serif}
\setsansfont{DejaVu Sans}
\setmonofont{DejaVu Sans Mono}
Եվ վերջ (բայց սա դեռ ամենը չէ՛)։ Հիմա արդեն կարելի է փաստաթղթի մարմնում գրել հայերեն Unicode տեքստ և xelatex ծրագրով այն բարեհաջող կթարգմանվի։ Ահա մի օրինակ.
\documentclass[12pt,a4paper,draft]{article}
\usepackage{fontspec}

\setmainfont{DejaVu Serif}
\setsansfont{DejaVu Sans}
\setmonofont{DejaVu Sans Mono}

\begin{document}
\chapter{Առակներ}

Ճանաչել իմաստութիւնն ու խրատը, իմանալ հանճարի խօսքերը, 
ընկալել խօսքի բարդ դարձուածքները, հասկանալ ճշմարիտ 
արդարութիւնը եւ ուղղել իրաւունքը՝ պարզամիտներին 
խորագիտութիւն եւ երիտասարդներին միտք ու հանճար տալու 
համար, որպէսզի, դրանք լսելով, իմաստունն աւելի իմաստուն 
լինի, իսկ հանճարեղը առաջնորդութիւն ստանայ, թափանցի 
առակների եւ խորին ասոյթների մէջ, իմաստունների ճառերի 
եւ նրանց այլաբանութիւնների մէջ։ 
\end{document}
Այս «ձեռագրի» համար ստացված PDF-ը ունի ստորև բերված նկարի տեսքը։
Հենց առաջին հայացքից երևում են մի քանի խնդիրներ. ա) LATEX-ի \chapter հրամանը տեքստի գլուխը սկսել է «Chapter» անգլերեն բառով, շատ լավ կլինի, որ գրվի հայերեն «Գլուխ» բառը, բ) հայերեն տեքստերի համար չկան տողադարձի կանոններ և երկար բառերը դուրս են եկել տեքստի համար նախատեսված սահմաններից, գ) քանի որ հայերեն տառերից շատերն ունեն տողից կախված մաս, դրանք լցնում են ստանդարտ միջտողային տարածությունը և տեքստը դառնում է աչքի համար նվազ հաճելի։

Առաջին խնդիրը կարելի է լուծել ձեռագրի հայտարարությունների մասում (\documentclass և \begin{document} արանքում) \renewcommand հրամանով վերասահմանելով latex փաստաթղթի տրամաբանական մասերի գլխագրերը.
\renewcommand{\chaptername}{Գլուխ} % book, report դասերի համար
\renewcommand{\contentsname}{Բովանդակություն}
\renewcommand{\figurename}{Նկար}
\renewcommand{\tablename}{Աղյուսակ}
\renewcommand{\appendixname}{Հավելված}
\renewcommand{\bibname}{Գրականություն} % book, report դասերի համար
%\renewcommand{\refname}{Գրականություն} % article դասի համար
\renewcommand{\indexname}{Առարկայական ցանկ}
Երկրորդ՝ տողադարձերի հետ կապված, խնդիրը լուծելու երկու եղանակ կա։ Կամ հայտարարությունների մասում ավելացնել \sloppy հրամանը, որը երկար բառը կտեղափոխի հաջորդ տողը և ամեն մի տողի միջբառային տարածությունները կավելացնի այնպես, որ տեքստը հավասարեցվի երկու կողմերից։ Ահա այսպես.
Այս եղանակին կարելի է դիմել էյն դեպքում, երբ պատրաստվող փաստաթուղթը գեղագիտական նշանակություն չի ունենալու այլ ծառայելու է միայն որպես տեղեկատվության փոխանցման միջոց։
    Երբ LATEX-ն օգտագործվում է, օրինակ, հրատարակության պատրաստվող գրքի տեքստի ձևավորման համար, իմ կարծիքով, ավելի ճիշտ է անցնել տեքստի վրայով և կատարել տողադարձերը։ Տողադարձը կատարելու համար ձեռագրում բառը պետք է վանկատել «\-» նիշով, իսկ LATEX-ի ֆորմատավորման ալգորիթմը այդ վանկատումից օգտվելու կկատարի տողադարձերը։ Ահա տեքստը, որտեղ որոշ բառերում նշված է տողադարձի տեղը.
Ճանաչել իմաստությունն ու խրատը, իմանալ հանճարի խոս\-քերը, 
ընկալել խոսքի բարդ դարձվածքները, հասկանալ ճշմա\-րիտ 
արդարությունը եւ ուղղել իրավունքը՝ պարզամիտներին 
խորագիտություն եւ երիտասարդներին միտք ու հանճար տա\-լու 
համար, որպեսզի, դրանք լսելով, իմաստունն ավելի իմաս\-տուն 
լինի, իսկ հանճարեղը առաջնորդություն ստանա, թա\-փան\-ցի 
առակների եւ խորին ասույթների մեջ, իմաստունների ճառերի 
և նրանց այլաբանությունների մեջ։ 
Իսկ այս տեքստից ստացվել է հետևյալ ֆորմատավորված փաստաթուղթը (ձեռագրից հեռացված է \sloppy հրամանը).
Ամեն ինչ, կարծես թե, լավ է։ Բայց տողադարձի ժամանակ LATEX-ն օգտագործում է սովորոկան hyphen գծիկը։ Հայերեն կետադրական կանոնները պահանջում են տողադարձի ժամանակ (և միայն տողադարձի ժամանակ) օգտագործել «֊» (ենթամնա) նիշը։ Դրա համար \setmainfont և \setsansfont հրամանները պետք է համալրել HyphenChar="058A ոչ պարտադիր արգումենտով.
\setmainfont[HyphenChar="058A]{GHEAMariam}
Ստորև բերված նկարներում տողադարձերը կատարված են ենթամնա նիշի օգտագործմամբ (ձախ նկարը) և սովորական hyphen նիշի օգտագործմամբ (աջ նկարը).
Եվ վերջապես, միջտողային տարածությունը մեծացնելու համար պետք է օգտագործել \linespread հրամանը՝ արգումենտում տալով ընդլայնման գործակիցը։
\linespread{1.2}
Հիմա արդեն վերջ։ LATEX ձեռագրում կատարելով վերը բերված փոփոխությունները՝ վստահորեն կարելի է պատրաստել բարձրորակ հայերեն փաստաթղթեր։

Wednesday, February 26, 2014

Բինար բուրգի կիրառության օրինակ

«Common Lisp։ 12 օրինակ» գրքիս խնդիրներից մեկում պահանջվում է տրված անգլերեն տեքստի հիման վրա անգլերեն այբուբենի համար կառուցել Մորզեի կոդավորման սխեմա։ Մորզեի կոդում ամեն մի տառի համապատասխանեցվում է կետ և գիծ նիշերից բաղկացած հաջորդականություն։ Կառուցվելիք սխեմայի համար հիմնական պահանջն այն է, որ տեքստում ավելի հաճախակի հանդիպող տառերին պետք է համապատասխանացնել ավելի կարճ կոդեր։

ՈՒրեմն, նախ պետք է վերլուծել տրված տեքստը և հաշվել անգլերեն այբուբենի 26 տառերից ամեն մեկի հանդիպելու հաճախությունը (ինչքան ավելի մեծ է վերլուծվող տեքստը, այնքան ավելի լավ արդյունքներ կարող ենք ստանալ)։ Այնուհետև պետք է և՛ տառերը դասավորել ըստ հաճախությունների նվազման, և՛ կոդերը դասավորել ըստ երկարությունների աճման։ Վերջում՝ համադրել այս երկու ցուցակները։

Ենթադրենք ունեմ մի histogram ֆունկցիա, որն արգումենտում ստանում է վերլուծվող տեքստը պարունակող ֆայլի անունը և վերադարձնում է անգլերեն այբուբենի տառերի ցուցակը՝ կարգավորված ըստ տեքստում դրանց հանդիպելու հաճախությունների նվազման։ Առայժմ սա դնեմ մի կողմ։
Մորզեի կոդերը կառուցում եմ հետևյալ կերպ։ Քանի որ այբուբենի տառերը 26 հատ են, ապա բավական է կառուցել 1, 2, 2 և 4 երկարությամբ կոդերը, որոնց ընդհանուր քանակը 30 հատ է։ 1. կառուցում եմ մի լրիվ բինար ծառ՝ արմատից բացի ևս չորս մակարդակներով։ 2. ծառի հանգույցները ըստ մակարդակների լրացնում եմ histogram ֆունկցիայի օգնությամբ ստացված ցուցակի տառերով։ 3. վերջում ծառի բոլոր ձախ գնացող ճյուղերը նշում եմ «.» (կետ) նիշով, իսկ դեպի աջ գնացողները՝ «-» (գիծ) նիշով։

Ստանում եմ մոտավորապես այսպիսի պատկեր.
Այս ծառի որևէ հանգույցում գրված տառի Մորզեի կոդը արմատից դեպի տվյալ հանգույցը հասնող կողերի նիշերի հաջորդականությունն է։ Օրինակ E = ., N = -., K = .--.։ Ավելի կոնկրետ. եթե տառը գտնվում է իր ծնողի ձախ կողմում, ապա տվյալ տառի կոդը ստացվում է ծնողի կոդին կցելով «.» նիշը, եթե տառը ծնողի աջ կողմում է, ապա նրա կոդը ստանալու համար ծնողի կոդին պետք է կցել «-» նիշը։

Քանի որ կառուցված ծառը բինար բուրգ է, այն կարող եմ մոդելավորել սովորական միաչափ զանգվածով (մանրամասները «Նախապատվություններով հերթի իրականացումը» գրառման մեջ)։ Զանգվածի 1 և 2 ինդեքսներով դիրքերում գրում եմ «.» և «-» նիշերը, իսկ 3-ից 26 միջակայքի k դիրքերի համար Մորզեի կոդը հաշվում եմ հետևյալ արտահայտությամբ.
c[k] = (c[(k-1)//2] + '.') if k % 2 == 1 else (c[(k-2)//2] + '-')
Սա ասում է, որ եթե \(k\)-ն կենտ է, ապա նրա ծնողի ինդեքսը հաշվել \(\frac{k-1}{2}\) բանաձևով և ծնողի կոդին կցել «.» նիշը, իսկ եթե \(k\)-ն զույգ է, ապա ծնողի ինդեքսը հաշվել \(\frac{k-2}{2}\) բանաձևով և ծնողի կոդին կցել «-» նիշը։ Ահա morsecodes ֆունկցիան, որը տրված n թվի համար կառուցում է 1-ից n երկարությամբ բոլոր Մորզեի կոդերը։
def morsecodes(n):
  c = list(range(n+1))
  c[1] = '.'
  c[2] = '-'
  for k in range(3,n+1):
    c[k] = (c[(k-1)//2] + '.') if k % 2 == 1 else (c[(k-2)//2] + '-')
  return c[1:]
Հիմա արդեն կարող եմ histogram ֆունկցիայով ստանալ ըստ հաճախությունների նվազման դասավորված տառերի ցուցակը, morsecodes ֆունկցիայով ստանալ կոդերի ցուցակը և Python լեզվի zip դրանք միավորել իրար հետ։
result = list(zip(histogram('thevalleyofthemoon.txt'),morsecodes(26)))
* *
Որպես վերլուծվող տեքստ ես վերցրել եմ Ջեկ Լոնդոնի «Լուսնի հովիտը» վեպի անգլերեն տարբերակը։ Իսկ վերլուծությունը կատարել եմ ահա այս Python ֆունկցիայով.
def histogram(source):
  alphabet = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
  his = {c: 0 for c in alphabet}
  with open(source) as inp:
    while True:
      chars = inp.read(4096).upper()
      if chars == '': break
      for ch in filter(lambda c: c in alphabet, chars):
        his[ch] = his[ch] + 1
  return sorted(his, key=his.get, reverse=True)