Редактирование: МФСП, 04 семинар (от 22 сентября)

Материал из eSyr's wiki.

Внимание: Вы не представились системе. Ваш IP-адрес будет записан в историю изменений этой страницы.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.

Спи ски

Спискм в RSL нз. упорядч. типизир. нбр эл-тов, эл-иы могут пвторяться. Списк в угловых скбкх, прядок вжен, все элементы дного типа

<1, 3, 1, 5, 4>
 <false, true>

Для спискв, кк и для всех типов в rsl пр. две перации: =, &ne;

Для список опр. дв типа: T-list, T-inflist (по ANSI); T*, T^&omega;

Определён пустой список: <>

пр. синтаксис <v1..vn>

Опр. синтксис: <expr|limit>

Пример:
 <2*n|n in <0..3>>

Список может быть опр. для лдюбго ип, не олько бзового: мнжества, списка...

Для того, чтобы добрться д эл-та, исп. перация index, "()", в которой ук. номер эл-та:
 <1,4,5,6>(2) = 4
 <2,5,3>,<3,1>>(2) = <3,1>
 <2,5,3>,<3,1>>(2)(2) = 1

Операции со списками:

Конктенция:
 Конк. мжно применять только к кнеч. спискм, второй эл-т мжет быть и конеч, и беск. Рез-т соотв. типа
 l1^l2

Head: Первый элемент
 hd: T^&omega; стрелочк с влной T
 hd<> = chaos

Tail: Хвст
 tl: T^&omega; стрпелчк с волной T^&omega;
 tl<> = chaos

Len: длина списка
 len:T^&omega; стрелочк с влной Nat
 len<n|n &dot; is_prime> == chaos

elems: Элементы
 elems: T^&omega; стрелочк с волнлй T-infset

inds: Индексы
 inds: T^&omega; стрелочк с волнлй Nat-infset

Задача: пр. функцию length, которя выч. длину списка
 '''value'''
   length: T* &rarr; Nat
     length(l) == if l &ne; <> then 1 + length(tl l) else 0 end

length2: T* &rarr; Nat 
     length2(l) == card inds l

Конструкция case:
 '''case''' ''cond'' '''of'''
   ''pattern1'' &rarr; ''expr1''
   ''pattern2'' &rarr; ''expr2''
   ...
   _ &rarr; ''def_expr''
 '''end'''

Как это исп. для работы со спискми (на том же примере):
 '''value'''
   length: T* &rarr; Nat
     length(l) ==
       '''case''' l '''of'''
         <> &rarr; 0
         &lt;i>^lr &rarr; length(lr) + 1
       '''end'''

Задач. Опр. функцию Pascal, гненер. тр. Пскаля д урвня n вкл. Результат --- список списков. Например:
 <<1>,
  <1,1>,
  <1,2,1>,
  <1,3,3,1>,
  <1,4,6,4,1>>

'''type'''
   T1={i | i:Nat &dot; i &ge; 1}
 
 '''value'''
   pascal:T1 &rarr; (T1*)*
     pascal(i) == if i=1 then <<1>> else pascal(i-1)^<<1>^<pascal(i-1)(i-1)(j)+pascal(i-1)(i-1)(j-)|j:T1 &dot; j in <2..i-1>>^<1>>

Задача. Реализовать функцию rev, кторая взвр. реверсивную версию списка.

'''value'''
   rev:T* &rarr; T*
     rev(l) == if l = <> then <> else rev(tl l)^ hd l end

Нерекурсивно, с пробеганием индекса

'''value'''
   rev:T* &rarr; T*
     rev(l) == <l(len(l)+1-n)|n in <1..len(n)>>

Даны следующие типы:
 '''type'''
   Page=Line*,
   Line=Word*,
   Word

(стандартный тип text в rsl н смом деле text=char*)

Для тких типов тр. опр. функцию is_on, проверяющую, встречется ли данне слово на странице

'''value'''
   is_on: Word &times; Page &rarr; Bool
     is_on(w,p) == if p=<> then False else w &isin; elems hd p &or; is_on(w, tl p) end

is_on: Word &times; Page &rarr; Bool
     is_on(w,p) == &exist; i : Nat &dot; (i &isin; {1..len(p)}) &and; (w &isin; elems p(i))

Определить number_of, пдсчитывающую количество вхождений слоов в страницу

'''value'''
   number_of: Word &times; Page &rarr; Nat
     number_of(w,p) &rarr; if p=<> then 0 else number_of_line(w,l) + number_of(w, tl p)

number_of_line: Word &times; Line &rarr; Nat
     number_o_line(w,l) &rarr; if l=<> then 0 else (if w=hd l then 1 else 0) + number_of_line(w, tl l)
 
 
   number_of: Word &times; Page &rarr; Nat
     number_of(w,p) &rarr; {(i,j)|(i:Nat&dot;j:Nat; &dot; p(i)(j)=w &and; i&isin; p &and; &isin;p(i)}

Пожалуйста, обратите внимание, что все ваши добавления могут быть отредактированы или удалены другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. eSyr's_wiki:Авторское право).
НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Описание изменений:

Отменить | Справка по редактированию (в новом окне)

Шаблоны, использованные на этой странице:

Получено с http://esyr.org/wiki/%D0%9C%D0%A4%D0%A1%D0%9F%2C_04_%D1%81%D0%B5%D0%BC%D0%B8%D0%BD%D0%B0%D1%80_%28%D0%BE%D1%82_22_%D1%81%D0%B5%D0%BD%D1%82%D1%8F%D0%B1%D1%80%D1%8F%29

Редактирование: МФСП, 04 семинар (от 22 сентября)

Материал из eSyr's wiki.

Просмотры

Личные инструменты

Навигация

инструменты

Разделы

Спецкурсы

9 семестр

7 семестр

5 семестр

3 семестр

Поиск

Инструменты

@@ Строка 1: / Строка 1: @@
-=Списки=
+Спи ски
-Списки в RSL — упорядоченный типизированный набор элементов, элементы могут повторяться. Список в угловых скобках, порядок важен, все элементы одного типа
+Спискм в RSL нз. упорядч. типизир. нбр эл-тов, эл-иы могут пвторяться. Списк в угловых скбкх, прядок вжен, все элементы дного типа
  <1, 3, 1, 5, 4>
  <false, true>
-Для списков, как и для всех типов в rsl определены две операции: =, &ne;
+Для спискв, кк и для всех типов в rsl пр. две перации: =, &ne;
-Для списков определено два типа: T-list(для конечных), T-inflist(для бесконечных) (по ANSI); T&times;, T^&omega;
+Для список опр. дв типа: T-list, T-inflist (по ANSI); T*, T^&omega;
 Определён пустой список: <>
@@ Строка 14: / Строка 14: @@
 пр. синтаксис <v1..vn>
-Опр. синтаксис: <expr|limit>
+Опр. синтксис: <expr|limit>
 Пример:
- <2&times;n|n in <0..3>>
+ <2*n|n in <0..3>>
- <3..7> &equiv; < 3,4,5,6,7>
+Список может быть опр. для лдюбго ип, не олько бзового: мнжества, списка...
- <7..3 > &equiv; <>
-Список может быть определён для любого типа, не только базового: множества, списка...
+Для того, чтобы добрться д эл-та, исп. перация index, "()", в которой ук. номер эл-та:
-==Индексация==
-Для того, чтобы добраться до элемента, используется операция index, "()", в которой указан номер элемента:
  <1,4,5,6>(2) = 4
  <2,5,3>,<3,1>>(2) = <3,1>
  <2,5,3>,<3,1>>(2)(2) = 1
-Если по не существующему номеру, то возвращает chaos.
 Операции со списками:
-===Конкатенация===
+Конктенция:
-Конкатенацию можно применять только к конечным спискам, второй элемент может быть и конечным, и бесконечным. Результат соответствующего типа
+ Конк. мжно применять только к кнеч. спискм, второй эл-т мжет быть и конеч, и беск. Рез-т соотв. типа
  l1^l2
- ^:T-list x T-inflist -> T-inflist
 Head: Первый элемент
- hd: T^&omega; <math>\tilde\rightarrow</math> T
+ hd: T^&omega; стрелочк с влной T
  hd<> = chaos
-Tail: Хвост
+Tail: Хвст
- tl: T^&omega; <math>\tilde\rightarrow</math> T^&omega;
+ tl: T^&omega; стрпелчк с волной T^&omega;
  tl<> = chaos
 Len: длина списка
- len:T^&omega; <math>\tilde\rightarrow</math> Nat
+ len:T^&omega; стрелочк с влной Nat
- len<n|n &bull; is_prime> &equiv; chaos
+ len<n|n &dot; is_prime> == chaos
-===elems: Элементы===
+elems: Элементы
- elems: T^&omega; <math>\tilde\rightarrow</math> T-infset
+ elems: T^&omega; стрелочк с волнлй T-infset
- Возвращает множество элементов списка
-===inds: Индексы===
+inds: Индексы
- inds: T^&omega; <math>\tilde\rightarrow</math> Nat-infset
+ inds: T^&omega; стрелочк с волнлй Nat-infset
- inds FL={1..len FL}
-==Задача==
+Задача: пр. функцию length, которя выч. длину списка
-Задача: пр. функцию length, которя вычисляет длину списка
  '''value'''
-   length: T&times; &rarr; Nat
+   length: T* &rarr; Nat
-     length(l) &equiv; if l &ne; <> then 1 + length(tl l) else 0 end
+     length(l) == if l &ne; <> then 1 + length(tl l) else 0 end
-   length2: T&times; &rarr; Nat
+   length2: T* &rarr; Nat
-     length2(l) &equiv; card inds l
+     length2(l) == card inds l
-==Case==
 Конструкция case:
  '''case''' ''cond'' '''of'''
@@ Строка 78: / Строка 66: @@
  '''end'''
-===Список чисел Фибоначчи===
+Как это исп. для работы со спискми (на том же примере):
- type Nat1= {n:Nat &circle; n > 0 }
- value Fib:Nat1->Nat1
-       Fib(n) &equiv;
- case n of
-->1
-->2
-       _->Fib(n-2)+Fib(n-1)
- end
-=== ===
- '''value''' rev:int-list&times; &rarr; T&times;
-     rev(l) &equiv;
- case L of
- <> -> <>
- <_i>^L2 -> rev(L2)^<_i>
- end
-Как это используется для работы со списками (на том же примере):
  '''value'''
-   length: T&times; &rarr; Nat
+   length: T* &rarr; Nat
-     length(l) &equiv;
+     length(l) ==
        '''case''' l '''of'''
          <> &rarr; 0
@@ Строка 106: / Строка 75: @@
        '''end'''
-Задача. Определить функцию Pascal, генерирующую треугольник Паскаля до уровня n включительно. Результат --- список списков. Например:
+Задач. Опр. функцию Pascal, гненер. тр. Пскаля д урвня n вкл. Результат --- список списков. Например:
  <<1>,
   <1,1>,
@@ Строка 114: / Строка 83: @@
  '''type'''
-   T1={i | i:Nat &bull; i &ge; 1}
+   T1={i | i:Nat &dot; i &ge; 1}
  '''value'''
-   pascal:T1 &rarr; (T1&times;)&times;
+   pascal:T1 &rarr; (T1*)*
-     pascal(i) &equiv; if i=1 then <<1>> else pascal(i-1)^<<1>^<pascal(i-1)(i-1)(j)+pascal(i-1)(i-1)(j-)|j:T1 &bull; j in <2..i-1>>^<1>>
+     pascal(i) == if i=1 then <<1>> else pascal(i-1)^<<1>^<pascal(i-1)(i-1)(j)+pascal(i-1)(i-1)(j-)|j:T1 &dot; j in <2..i-1>>^<1>>
-Задача. Реализовать функцию rev, которая возвращает реверсивную версию списка.
+Задача. Реализовать функцию rev, кторая взвр. реверсивную версию списка.
  '''value'''
-   rev:T&times; &rarr; T&times;
+   rev:T* &rarr; T*
-     rev(l) &equiv; if l = <> then <> else rev(tl l)^ hd l end
+     rev(l) == if l = <> then <> else rev(tl l)^ hd l end
 Нерекурсивно, с пробеганием индекса
  '''value'''
-   rev:T&times; &rarr; T&times;
+   rev:T* &rarr; T*
-     rev(l) &equiv; <l(len(l)+1-n)|n in <1..len(n)>>
+     rev(l) == <l(len(l)+1-n)|n in <1..len(n)>>
 Даны следующие типы:
  '''type'''
-   Page=Line&times;,
+   Page=Line*,
-   Line=Word&times;,
+   Line=Word*,
    Word
-(стандартный тип text в rsl на самом деле text=char&times;)
+(стандартный тип text в rsl н смом деле text=char*)
-Для таких типов требуется определить функцию is_on, проверяющую, встречается ли данне слово на странице
+Для тких типов тр. опр. функцию is_on, проверяющую, встречется ли данне слово на странице
  '''value'''
    is_on: Word &times; Page &rarr; Bool
-     is_on(w,p) &equiv; if p=<> then False else w &isin; elems hd p &or; is_on(w, tl p) end
+     is_on(w,p) == if p=<> then False else w &isin; elems hd p &or; is_on(w, tl p) end
    is_on: Word &times; Page &rarr; Bool
-     is_on(w,p) &equiv; &exist; i : Nat &bull; (i &isin; {1..len(p)}) &and; (w &isin; elems p(i))
+     is_on(w,p) == &exist; i : Nat &dot; (i &isin; {1..len(p)}) &and; (w &isin; elems p(i))
-Определить number_of, подсчитывающую количество вхождений слов в страницу
+Определить number_of, пдсчитывающую количество вхождений слоов в страницу
  '''value'''
    number_of: Word &times; Page &rarr; Nat
      number_of(w,p) &rarr; if p=<> then 0 else number_of_line(w,l) + number_of(w, tl p)
    number_of_line: Word &times; Line &rarr; Nat
      number_o_line(w,l) &rarr; if l=<> then 0 else (if w=hd l then 1 else 0) + number_of_line(w, tl l)
@@ Строка 160: / Строка 129: @@
    number_of: Word &times; Page &rarr; Nat
-     number_of(w,p) &rarr; card {(i,j)|(i:Nat&bull;j:Nat; &bull; p(i)(j)=w &and; i&isin; p &and; &isin;p(i)}
+     number_of(w,p) &rarr; {(i,j)|(i:Nat&dot;j:Nat; &dot; p(i)(j)=w &and; i&isin; p &and; &isin;p(i)}
-=== еще задачки ===
-является упорядоченным?
- value isStore: Int-list &right; bool
- isStore(l)= &forall; i:int &bull; i >= 1; &and; i < len(l) => l(i+1) > l(i)
-==== длина списка ====
- value len2: Elem-list-> Nat
- len2(E) &equal; ( if (E=<>) then 0 else 1+len2(tl E ) end )
- len3(E) - card inds E
-==== удаляем  заданный элем-т из списка ====
- value del: E-list &times; E &rarr; E-list
-       del(l, x): &equal; < E(i) | i in <1..len L > &bull; L(i) != x >
-==== подсчет ====
- value numOf: E-list &times; E -> Int
- NumberOf(L,x) = if ( LL=<> ) then 0 else
-     if( hd(L) = x ) then NumberOf( tl L, x ) +1 else NumberOf( tl L, x)
-==отображения==
-<math>[3 \rightarrow , 5 \rightarrow false](1) = chaos</math>
-операция взятия домена
-<math>dom:(T[d] \overset{m}{\rightarrow} T[r] ) \rightarrow T[d]-infset</math>
-<math>rng:(T[A] \overset{m}{\rightarrow} T[r] ) \rightarrow T[r]-infset</math>
 {{МФСП}}
 {{Lection-stub}}