Практические занятия по курсу ОиМП/Группа 101 1 — различия между версиями

Текущая версия на 14:49, 27 декабря 2014

Содержание

1 Консольные команды Linux
2 Немного о файловой системе
3 Перенаправление потоков
4 Конвейеры Linux
5 Пробный контест по вводу-выводу
6 Контест по геометрии
7 Контест по наследованию
8 Контест по обработке текстов
9 Множественное наследование и генераторы
10 Замыкание и декораторы
11 Графика
12 Первое домашнее задание
13 Параллельные вычисления
14 Введение в С++
15 Функции в C++
16 Классы в C++
17 Шаблонные функции и классы в C++
18 Второе домашнее задание
19 Наследование и интерфейсы в C++
20 Контрольная №1
21 Итераторы в C++
22 StyleGuide
23 Домашние работы 3 и 4
24 OpenGL и физика
25 Сетевые приложения
26 Пробный экзамен
27 Оценки

Консольные команды Linux

man <cmd> вывести помощь по команде (выход из помощи - :q)
python3 <file> запустить скрипт на языке python3
ls выводит содержимое текущей директории
cd <path> переходит в указанную директорию
mkdir <dirname> создает директорию
mv <old_name> <new_name> переместить или просто переименовать файл
rm <file> удаляет файл
less <file> открыть просмотр файла в less (выход - :q)
touch <file> создать пустой файл
echo <str> вывести строку
cat <file> вывести содержимое файла
head <file> вывести начало файла
tail <file> вывести конец файла

Немного о файловой системе

"~" - ваша домашняя директория
"." - текущая директория
".." - родительская директория
"/" - корень диска

Таким образом, "~/./any_dir/../" --- это то же самое, что и "~/any_dir/..", и "~/", и "~", "/home/guest-.../", и "~/../guest-...". Здесь "..." обозначают какую-то строку, которая может меняться в силу текущих настроек Linux.

Перенаправление потоков

Каждая команда в Linux принимает поток stdin и генерирует два потока - поток вывода stdout и поток ошибок stderr.
Для перенаправления этих потоков служат символы "<", ">", ">>".
Например, команда "python3 script.py > output.txt" перенаправит stdout вашего скрипта в файл output.txt.
А команда "python3 script.py < input.txt" направит в ваше решение содержимое файла input.txt.
Конечно же, их можно комбинировать. Важно заметить, что при использовании ">" уже имеющийся output.txt будет удален и появится новый output.txt.
Если вы хотите просто дописать строки в конец имеющегося файла, используйте ">>".

Конвейеры Linux

Один из наиболее мощных инструментов в консоли. Позволяет направить stdout предыдущей команды в stdin следующей. Пример:
cat sample.txt | grep -v "Test" | python3 solve.py >> result.txt
Здесь из файла sample.txt будут выброшены все строки, содержащие слово Test, а остальные будут направлены в ваш скрипт, после чего его результат допишется в конец файла result.txt.

Теперь приведу пример цикла:
for i in {1..10}; do echo $i | python3 solve.py; done
Этот цикл запустит ваше решение на всех числах от 1 до 10.

Пробный контест по вводу-выводу

http://official.contest.yandex.ru/contest/654/
Группы задач:

0 (Hello, world!)
1-6 (простые арифметические вычисления)
7-12 (условный оператор)
13-17 (циклы и делимость 1)
18-24 (циклы и делимость 2)
25-30 (системы счисления)
31-35 (прочее по циклам)
36-41 (форматированный вывод)

Из каждой группы надо решить по две задачи, а нулевую задачу нужно решить всем.

Контест по геометрии

Цель контеста --- знакомство с типами и перегрузкой операторов в Python.
http://official.contest.yandex.ru/contest/664/
Необходимо сдать хотя бы две задачи.

Контест по наследованию

Простейшие задачи на наследование в Python3.
Цель здесь --- это не решить эти задачи, а попробовать реализовать наследование.
http://official.contest.yandex.ru/contest/667/
Необходимо сдать обе задачи.

Контест по обработке текстов

Контест, связанный с лекционными материалами.
http://official.contest.yandex.ru/contest/669/
Группы задач:

0-8
9-14

Из каждой группы необходимо решить по две задачи.

Обратите внимание, что в этом контесте работает проверка PEP8!

Множественное наследование и генераторы

http://official.contest.yandex.ru/contest/675/
Всем нужно сдать задачу номер 0, а также любые другие две задачи.

Также советую еще раз попробовать осознать, что происходит вот в этом фрагменте кода:

```
  class MyType(type):
```

           def __new__(cls, name, bases, dict):

                   print("New instance of %s created with name %s, bases %s and params %s"

                           % (cls.__name__, name, str(bases), str(dict)))

                   return type.__new__(cls, name, bases, dict)

           def __init__(cls, name, bases, dict):

                   print("Instance of %s with name %s and bases %s initialized with params %s"

                           % (cls.__name__, name, str(bases), str(dict)))

                   return super(MyType, cls).__init__(name, bases, dict)

```
 
```
```
  MyObject = MyType("MyObject", (), {})
```
```
 
```
```
  class MyClass(MyObject):
```
```
          def __init__(self, s):
```
```
                  print(s)
```
```
 
```
```
  mc = MyClass("parameter")
```

Вкратце, примерно следующее: мы объясняем Python3, что у нас будет новый тип классов --- MyType.
Создаем аналог object для этого типа объектов. Именно от него мы будем наследовать все наши новые классы.
Унаследуем от него новый класс MyClass.

Вот что этот пример выводит:

  New instance of MyType created with name MyObject, bases () and params {}

  Instance of MyObject with name MyObject and bases () initialized with params {}

  New instance of MyType created with name MyClass, bases (<class '__main__.MyObject'>,) and params

  {'__init__': <function MyClass.__init__ at 0x100771d08>, '__module__': '__main__', '__qualname__': 'MyClass'}

  Instance of MyClass with name MyClass and bases (<class '__main__.MyObject'>,) initialized with params

  {'__init__': <function MyClass.__init__ at 0x100771d08>, '__module__': '__main__', '__qualname__': 'MyClass'}

```
  parameter
```

Почему так?
Вначале честно вызываются __new__ и __init__ при создании MyObject. Python смотрит вверх по дереву и ищет __new__ и __init__ от MyType и сразу же у него их и находит - выводит первые две строки и создает объект, как и написано в коде.
Далее, при создании MyClass мы создаем новый объект, а потому вызываются метод __new__ и __init__ для того класса, которому он принадлежит - MyObject. И мы получаем вывод 4, 5, 6 и 7 строчек - Python дополняет список параметров и передает их в наши методы __new__ и __init__ объекта MyObject.

Замыкание и декораторы

http://official.contest.yandex.ru/contest/687/
Нужно решить обе приведенные задачи.
Во второй задаче возможны проблемы с правильным ответом.
Если вы по необъяснимым причинам получаете WA, просто попробуйте сдать еще раз.

Графика

Основным руководством для нас будет вот эта вики страничка
http://ru.wikiversity.org/wiki/%CA%F3%F0%F1_%EF%EE_%E1%E8%E1%EB%E8%EE%F2%E5%EA%E5_Tkinter_%FF%E7%FB%EA%E0_Python
Наша основная задача на сегодняшнее занятие - написать графическое-приложение калькулятор.
Нужно это, чтобы познакомиться с графической библиотекой tkinter и основными ее методами.

Важно отметить, что в зависимости от версии Python на вашем ноутбуке, вам нужно писать Tkinter вместо tkinter в названии модуля.
Если пример не работает и python3 ругается на отсутствие библиотеки, просто измените регистр первой буквы в названии модуля, все должно заработать.

Начнем мы с самого простого приложения "Hello, world!":

```
  from tkinter import *
```
```
 
```
```
  tk = Tk()
```
```
 
```
```
  entry = Entry(tk)
```
```
  entry.pack()
```
```
  entry.insert(0, "Hello, world!")
```
```
 
```
```
  tk.mainloop()
```

Здесь в 3ей строке создается новое приложение, в 5ой - новое текстовое поле, в 6ой строке оно укладывается в окно, в 7ой изменяется его содержимое, а в 9ой мы запускаем цикл обработки событий окна.
Entry - это виджет библиотеки tkinter, который позволяет отображать одну строку текста.

Теперь давайте попробуем сделать кнопку в нашем приложении:

 1 from tkinter import *
 2 
 3 tk = Tk()
 4 
 5 button = Button(tk, text="Hello, world!")
 6 button.pack()
 7 
 8 tk.mainloop()

Но пока эта кнопка ничего не делает. Давайте сделаем так, чтобы при нажатии на кнопку в консоль писалось бы "Hello, world!". Для этого мы должны передать в конструктор кнопки функцию, которая будет вызвана при нажатии:

 5 def hello():
 6         print("Hello!")
 7 
 8 button = Button(tk, text="Hello, world!", command=hello)

В конструкторе кнопки добавился аргумент command, который указывает Pythonу, какая функция будет реагировать на нажатие кнопки.

Теперь давайте поговорим о том, как размещаются элементы на экране.
Pack - это очень простой упаковщик. Он может поместить виджет только в одно из крайних положений "top", "bottom", "left", "right". Делается это так:

 1 from tkinter import *
 2 
 3 tk = Tk()
 4 
 5 b1 = Button(tk, text="Left")
 6 b1.pack(side="left")
 7 
 8 b2 = Button(tk, text="Right")
 9 b2.pack(side="right")
10 
11 tk.mainloop()

Это дает возможность размещать элементы в определенном порядке, но особой свободы не дает.

Перейдем к упаковщику grid, который позволяет разбить окно на ячейки таблицы и размещать элементы в них. Простой пример:

 1 from tkinter import *
 2 
 3 tk = Tk()
 4 
 5 b1 = Button(tk, text="Left top")
 6 b1.grid(row=0, column=0)
 7 
 8 b2 = Button(tk, text="Right bottom")
 9 b2.grid(row=1, column=1)
10 
11 tk.mainloop()

Это уже значительно более общий метод.

Теперь вы знаете все необходимое для того, чтобы составить из кнопок простой калькулятор и добавить текстовое поле для вывода результата.
Попробуйте, используя все ваши знания про Python, написать теперь простой калькулятор.

Удачи!

Первое домашнее задание

Контест с задачами:
http://official.contest.yandex.ru/contest/689/
Распределение задач осуществляется по простому правилу:

всего есть пять типов задач;
из каждого типа задач надо решить ровно одну задачу;
номер задачи в группе определяется по какой-то букве:

1	2	3	4
АДЗЛПУЧЫЯ	БЕИМРФШЬ	ВЁЙНСХЩЭ	ГЖКОТЦЪЮ

для первых трех групп задач эти буквы - это первые три буквы вашего полного имени;
для последних двух групп задач эти буквы - это первые две буквы вашей фамилии.

Таким образом я, Павел Мельничук, должен был бы решить задачи A1 (П), B1 (А), C3 (В), D2 (М) и E2 (Е).

Параллельные вычисления

Контеста в этот раз нет, поскольку Яндекс.Контест не поддерживает многопроцессорные приложения.
Так что наша задача - научиться выполнять параллельные вычисления и решить с их помощью несколько задач, не сдавая их в тестирующую систему.

Ускорьте выполнение задачи про сумму k-ых степеней. Вход программы - числа k и n. Вывод - сумма k-ых степеней чисел от 0 до n - 1. Какой максимальный коэффициент ускорения вы смогли получить? Почему он именно такой?
Посчитайте скалярное произведение двух векторов размерности n. Чтобы не тратиться время на их ввод из файла, генерируйте их в программе по какой-нибудь простой формуле. Например, a_i = 1 / i.
Реализуйте обе предыдущие задачи, не компонуя ответ по результаты выполнения всех задач, а заполняя ответ из ветвей, используя локи.

Введение в С++

Ссылка на контест:
http://official.contest.yandex.ru/contest/719/
Задачки очень простые, поэтому решаем все, чтобы набить руку.

Также предлагается следующая задача на подумать: дан массив из N элементов и число K. Нужно найти K минимальных чисел. С каким асимптотическим потреблением памяти и времени вы умеете решать эту задачу?

Для тех, кто участвовал в четверть-финале прошлого года: дан массив из N элементов и числа L и R. Нужно найти число подотрезков этого массива, сумма которых лежит в отрезке от L до R.

Функции в C++

Ссылка на контест:
http://official.contest.yandex.ru/contest/735/
Задачки простые, подумать надо (или не надо) только над последней, поэтому решаем все задачки подряд.

Классы в C++

Ссылка на контест:
http://official.contest.yandex.ru/contest/746/
Вы эти задачи уже решали, так что проблем с семантикой быть не должно. Важно правильно реализовать все необходимые структуры, методы и операторы.

Шаблонные функции и классы в C++

Ссылка на контест:
http://official.contest.yandex.ru/contest/784/
Задачки простые, решаются и без шаблонов, но наша задача - потренироваться в их написании.

Второе домашнее задание

Контест с задачами:
http://official.contest.yandex.ru/contest/763/
Распределение задач такое же, как и в первой домашней работе.

Наследование и интерфейсы в C++

Контест с задачами:
http://official.contest.yandex.ru/contest/797/
Первую задачу надо решить. Вторую - если хватит сил и времени.

Контрольная №1

Контест:
http://official.contest.yandex.ru/contest/828/

Итераторы в C++

Контест с задачами:
http://official.contest.yandex.ru/contest/806/

StyleGuide

Ссылка на Google StyleGuide, на примере которого мы разбираем общие правила написания кода
http://google-styleguide.googlecode.com/svn/trunk/cppguide.html

Домашние работы 3 и 4

Ссылка на контест:
http://official.contest.yandex.ru/contest/946/
Распределение задач старое, как на первых двух домашках.

OpenGL и физика

Ссылка на пример кода:
http://pastebin.com/JeuXPV9Z
Компилировать его надо строкой
g++ main.cpp -lGL -lGLU -lglut -std=c++0x
Задача на семинар - попытаться сымитировать физику двух атомов.
Они должны притягиваться, если отлетели далеко друг от друга, и отталкиваться, если приблизились слишком сильно.
Если это получится, попробуйте построить из них кристаллическую решетку.
Если решетка не развалится сама, попробуйте задать начальные скорости нескольким атомам и посмотреть, что будет :)

Сетевые приложения

Ссылка на код сервера:
http://pastebin.com/fzF8yR6W
Сслыка на архив с сервером астероидов:
https://yadi.sk/d/4JCWLAIZdQQXs
Старая ссылка на архив с клиентом:
https://yadi.sk/d/CtPlQDGRdVnxZ

Пробный экзамен

На странице основы и методологии программирования есть ссылки на пробный экзамен и его решения.

Оценки

На данный момент результаты такие:

	Фамилия	Имя	Отчество	ДЗ-1	ДЗ-2	КР	ДЗ-3	ДЗ-4	Accum	Exam	Sum
1	Гущенко-Чеверда	Иван	Ильич	10	10	10	10	9	9,8	9	9,6
2	Деркач	Денис	Анатольевич	10	10	10	10	8	9,6	9	9,45
3	Исхаков	Тимур	Рашидович	10	10	10	10	10	10	10	10
4	Кузнецов	Георгий	Алексеевич	6	8	10	5	7	7,2	9	7,65
5	Мельниченко	Пётр	Валерьевич	10	4	10	0	0	4,8	10	6,1
6	Носков	Степан	Алексеевич	10	8	10	5	5	7,6	10	8,2
7	Пособин	Глеб	Игоревич	10	10	10	10	10	10	10	10
8	Пролеев	Лев	Николаевич	10	10	10	10	5	9	9	9
9	Рябушев	Антон	Федорович	10	10	10	10	9	9,8	9	9,6
10	Сайранов	Айдар	Дамирович	10	8	10	10	5	8,6	10	8,95
11	Святокум	Полина	Олеговна	8	10	10	10	5	8,6	10	8,95
12	Султанов	Арсен	Русланович	10	10	10	0	0	6	10	7
13	Трофимов	Иван	Андреевич	2	8	10	10	8	7,6	10	8,2