SEWiki - Вклад участника [ru]

Формальные языки, 2 курс, весна 2016

2016-04-29T11:29:39Z

V.a.stepanov:

'''Лекции:''' Михаил Эдуардович Дворкин (mikhail.dvorkin@gmail.com)

'''Практика:''' Николай Карпов (I подгруппа), Михаил Слабодкин (slabodkinm@gmail.com) (II подгруппа).

Конспект http://yeputons.net/spbau/term4-formal_languages-lectures.pdf

== План ==

Лекция 1
* Языки и yes/no-задачи. Теоретико-множественное доказательство невозможности описания языков.
* Детерминированные конечные автоматы. Принятие слова.
* Эквивалентность состояний. Минимизация ДКА.
Лекция 2
* Правые контексты.
* Эквивалентность ДКА.
* Прямое произведение ДКА.
* Динамическое программирование по ДКА.
Лекция 3
* Академические регулярные выражения.
* Теорема Клини — эквивалентность КА и АРВ.
Лекция 4
* Операции над языками. Свойства регулярных языков.
* Лемма о разрастании.
Лекция 5
* КС-грамматики.
* Вывод, левосторонний вывод, дерево разбора.
* Однозначные КС-грамматики.
* Вложенность регулярных языков в КС-языки.
Лекция 6
* Нормальная форма Хомского.
* Удаление бесполезных нетерминалов, \eps-продукций, цепных продукций, терминалов в длинных продукциях, длинных продукций.
* Принадлежность слова КС-языку. Алгоритм Кока—Янгера—Касами.
Лекция 7
* Лемма о разрастании для КС-грамматик
* Автоматы с магазинной памятью, прием по пустому стеку и терминальному состоянию
Лекция 8
* Эквивалентность МП-автоматов и КС-грамматик
* Детеримированные автоматы с магазинной памятью, неэквивалетность двух видов приема
* Соотношение регулярных, ДМП- и КС-языков
Лекция 9
* Иерархия Хомского
* Регулярные грамматики, эквивалентность ДКА
* Контекстно-зависимые грамматики, неукорачивающие грамматики
* Нормальная форма Куроды для КЗ- и произвольных грамматик, приведение к ней
* Неограниченные грамматики, эквивалентность машинам Тьюринга

== К занятиям Николая Карпова ==

[https://drive.google.com/folderview?id=0B9NF86zbFMKkQlBDUHpLZDI0eHM&usp=sharing Все материалы и табличка].

[https://docs.google.com/spreadsheets/d/1_JhH9h8_k57iw3BEFnlMmK3sfSITwDWVOvlerSA5Wlk/edit?usp=drive_web Таблица с результатами]

=== Домашние задания ===
Осторожно, теоретически могут быть ссылки на старые версии - актуальные ищите в разделе "Все материалы и табличка" выше.

{| border="1" cellspacing="0" cellpadding="3"

|-
!№
!Дата

|-
!1
|align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkMzRQQ09uQmVsbWc/view На 19.02.2016]

|-
!2
|align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkWXA5UnE2Xy1uczQ/view На 26.02.2016]

|-
!3
|align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkZy1QY3dVZEhXbzg/view На 04.03.2016]

|-
!4
|align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkQkl1cUZuZ0FGUm8/view На 11.03.2016]

|-
!5
|align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkMFBKQmJBa25BYTQ/view На 18.03.2016]

|-
!6
|align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkZEFUMjRrVVRBTms/view На 25.03.2016]

|-
!7
|align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkaEVFZ2JxazY4bkE/view На 01.04.2016]

|-
!8
|align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkeDF1TFRDSktuUW8/view На 08.04.2016]

|-
!9
|align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkWUJ5YTBOb2RoYzQ/view На 22.04.2016]

|-
!10
|align=center|[https://drive.google.com/file/d/0B9NF86zbFMKkUGlYUEY2NjVxMFE/view На 29.04.2016]
|}

== К занятиям Михаила Слабодкина ==

[https://docs.google.com/spreadsheets/d/13ELlUZn098B5opdQrn1UWfMmDbwosVZ5vKNX7NZDGc8/edit Результаты]

== Ссылки ==

* Важная книга для первой части курса: Хопкрофт, Мотвани, Ульман. Введение в теорию автоматов, языков и вычислений.
* [http://neerc.ifmo.ru/wiki/index.php?title=Теория_формальных_языков]
* [http://www.ics.uci.edu/~goodrich/teach/cs162/notes/]
* [http://www.eecs.wsu.edu/~ananth/CptS317/]
* [http://users.utu.fi/jkari/automata/fullnotes.pdf]

Java 2 2015

2015-09-18T07:25:24Z

V.a.stepanov:

Лектор — Антон Михайлович Кузнецов (anton.m.kuznetsov@gmail.com)

Практика — Денис Сергеевич Жарков (denis.zharkov@jetbrains.com), Николай Вадимович Обедин (nikolay.obedin@jetbrains.com)

== Лекции ==

:[[Медиа:Java_B_2015_01-1.pdf|Лекция 01 (часть 1)]]
:[[Медиа:Java_B_2015_01-2.pdf|Лекция 01 (часть 2)]]
:[[Медиа:Java_B_2015_02-1.pdf|Лекция 02 (часть 1)]]
:[[Медиа:Java_B_2015_02-2.pdf|Лекция 02 (часть 2)]]
:[[Медиа:Java2014 05 Examples.zip|Лекция 02 (примеры)]]

== Проекты ==

#Юрий Кравченко, Надежда Бугакова - контроллер для ПК с помощью android устройства
#Настя Гайдашенко, Саша Малышева - игра "гонки" с акселерометром
#Старкова Анастасия - финансовый помощник
#Дмитрий Лапшин, Степанов Всеволод - Война Вирусов
#Глеб Валин - Тайное послание
#Лиза Третьякова, Черникова Оля - календарь
#Дима Кравченко, Розплохас Дмитрий - расписание
#Подгузов Никита - приложение для прохождения квестов по городу
#Беляев Стас - Feed-агрегатор

== Домашние задания ==

[https://github.com/java-course-au/assignments/blob/master/README.mkdn Общая информация]

; StringSet (до 23.09)
: [https://github.com/java-course-au/assignments/tree/01-serializable-string-set Ссылка на ветку репозитория]
UPDATE: Строки состоят из только из заглавных и прописных букв латинского алфавита => сложные структуры данных (вроде HashMap/TreeMap) использовать нельзя

== Практики (Николай Обедин) ==

; 2015-09-02
: [[Медиа:java-practice-obedin-2015-09-02.pdf|Слайды]]
: [https://github.com/dancingrobot84/java-practice-2015/tree/master/2015-09-02 Примеры с практики]
: [http://rosettacode.org/wiki/Category:Java Примеры кода на Java c Rosetta Code]

; 2015-09-16
: [[Медиа:java-practice-2015-09-16.pdf|Слайды]]

== Практики (Денис Жарков) ==

: [https://github.com/openjdk-mirror/jdk/tree/jdk7/jdk7/master/src/share/classes/java Исходники стандартной библиотеки, как пример <<правильного>> кода]

; 2015-09-16
: [[Медиа:Java-16-09-2015.pdf|Слайды]]

Матан, 1 семестр, 2014/15

2014-09-21T14:18:36Z

V.a.stepanov: /* Домашнее задание к 25.09.14 */

= Группа Фёдора Петрова =

== Домашнее задание на семестр ==
Отчётность: без понятия

# Существует ли биективный многочлен <math>f(x, y)</math>:
## <math>\mathbb{Z}^2 \to \mathbb{Z}</math>
## <math>\mathbb{Q}^2 \to \mathbb{Q}</math>

== Домашнее задание к 11.09.14 ==

Отчётность: решаем, на занятии обсуждаем.

# [[Файл:calculus_2014_140911_b.svg|right|160px]] Доказать, что на плоскости можно расположить не более чем счётное число непересекающихся фигурок. Фигурка — это точка, из которой торчат 3 непересекающиеся ломаные.
# <math>F \subseteq 2^\mathbb{N}</math>. Может ли F быть несчётным? Два независимых пункта с условием:
## <math>\forall A, B \subseteq F, A \neq B:</math> либо <math>A \subseteq B</math>, либо <math>B \subseteq A</math>
## <math>\forall A, B \subseteq F, A \neq B: |A \cap B| < \infty</math>
# <math>E \subseteq \mathbb{N}, |E| = \infty</math>. Доказать, что существует <math>a \in \mathbb{R}, a > 1</math> такое, что существует существует бесконечно много натуральных <math>n</math> таких, что <math>\left\lfloor{a^n}\right\rfloor \in E</math> (<math>\left\lfloor x \right\rfloor</math> - целая часть <math>x</math> или округление вниз).

== Домашнее задание к 18.09.14 ==

Отчётность: в рамках усиления контроля предлагается его писать и сдавать в начале занятия.

[[Медиа:Dz2.pdf|PDF с заданием]]

== Домашнее задание к 25.09.14 ==

1. а) (1) Докажите, что ограниченная последовательность вещественных чисел имеет предел тогда и только тогда, когда она имеет единственный частичный предел (предел подпоследовательности).

б) (1) Докажите, что множество частичных пределов любой последовательности вещественных чисел замкнуто.

2. а) (1) Докажите, что если <math>X_1\subset X</math> и пространство <math>(X,\rho)</math> сепарабельно, то пространство <math>(X_1,\rho)</math> тоже сепарабельно.

б) (1) Пусть <math>X_n</math> --- последовательность подмножеств <math>(X,\rho)</math>, такая что <math>(X_n, \rho)</math> сепарабельны, а <math>\cup X_n</math> плотно в <math>X</math>.
Докажите, что <math>(X,\rho)</math> сепарабельно.

3. (2) Докажите, что если метрическое пространство сепарабельно, то любое его открытое подмножество представляется в виде счетного объединения шаров.

4. (1) Пусть <math>p</math> --- простое число. Для <math>x \in /mathbb{Q}, x \ne 0</math> определим <math>\|x\|_p=p^{-n}</math>, где число <math>x</math> представлено в виде <math>x=p^n\frac{a}{b}</math>, где <math>a, b, n \in /mathbb{Z}</math> и <math>a,b</math> не делятся на <math>p</math>. Положим <math>\|0\|_p=0</math>. Докажите, что функция <math>\rho_p(x,y)=\|x-y\|_p</math> является метрикой на множестве <math>/mathbb{Q}</math>.

5. (4) Докажите, что если <math>X</math> --- полное метрическое сепарабельное пространство без изолированных точек (изолированной называется точка, совпадающая с некоторой своей окрестностью), то найдется инъекция из множества бесконечных (0,1)-последовательностей в <math>X</math> (тем самым, <math>X</math> не счетно).

6. (4) Полное метрическое пространство представлено в виде счетного объединения замкнутых множеств.
Докажите, что хотя бы одно из них имеет непустую внутренность.

7. (4) Докажите, что если <math>\rho_1</math> и <math>\rho_2</math> --- две метрики на множестве <math>X</math>, такие что метрические пространства <math>(X,\rho_1)</math> и <math>(X,\rho_2)</math> сепарабельны, то метрическое пространство <math>(X,\rho_1+\rho_2)</math> тоже сепарабельно.

8. Найдите множество частичных пределов последовательности

а) (2) <math>\{\sqrt{n}\}</math> (<math>\{x\}=x-[x]</math> --- дробная часть числа <math>x</math>, то есть <math>0\leq \{x\}<1</math> и <math>[x]=x-\{x\}</math> --- целое число.)

б) (3) <math>\sin (\pi \sqrt{2} n)</math>.

= Группа Александра Логунова =

== Домашнее задание к 25.09.14 ==

Задачи нужно сдать на следующем занятии.
Каждая задача стоит от 1-го до 4-ех баллов. Рекомендуется решить все задачи, которые весят 1 - 2 балла. Остальные задачи считайте бонусными.

[[Медиа:Dz3.pdf|PDF с заданием]]

Участник:V.a.stepanov

2014-09-04T19:19:04Z

V.a.stepanov: Новая страница: «e-mail: tehnar5@gmail.com Телефон: +7(950)027-27-04»

e-mail: tehnar5@gmail.com Телефон: +7(950)027-27-04