Differences between revisions 1 and 70 (spanning 69 versions)
Revision 1 as of 2017-06-29 12:53:27
Size: 3470
Comment: first mockup
Revision 70 as of 2017-07-11 14:04:45
Size: 36069
Comment:
Deletions are marked like this. Additions are marked like this.
Line 1: Line 1:
== День 1 ==
 - Орг: конспекты (c двух строрнон: Linux+Python), практика обязательна
 - FOSS: сообщество и ПО, Linux, Python
 - Linux: «цветочек»+
   ⇒ командная строка
   - команды
   - программа
   - интеграция
   - переменные
   - где лежат команды (пространство имён)
     - PATH
     - ls -l / chmod
 - Python:
   - командная строка
   - объекты, их типы
   - действия над объектами
   - неявная динамическая типизация
   - программа на Python
   - Сценарий Linux, shebang
   - Использование geany
   - преобразование типов, type() (в т. ч. type(a)(b)) и простейший ввод-вывод
   - связывание объектов именами, dir()
 - Практика:
   - примитивный сценарий на shell
   - вычисление формул
   - ручное развёртывание бинарного возведения в степень
   - *TODO*

== День 2 ==
 - Python
   - условные операторы и выражения
   - условное выражение a if b else c
   - базовый if, форматирование отступами
   - if / elif / else
   - примеры
   - пустой объект, примеры
   - ⇒ _любое_ выражение в условии
   - операции сравнения
   - алгебра логики, таблицы истинности
   - логические операции Python, их таблицы истинности
   - примеры
   - цикл while (простой вариант)
   - использование math
 - Практика
   - нер-во тр-ка
   - биквадратное уравнение с ненулевым a
   - условные формулы
   - таблица умножения на N
   - цикл по вводу
   - *TODO*

== День 3 ==
- Python
  - Последовательности (введение)
  - Хранимые (строки, кортежи, списки)
    - индексирование, в т. ч. отрицательное
    - секционирование всякое
  - Вычисляемые (range(), enumerate())
  - цикл прохода по последовательности for
  - Каноническая схема цикла
  - break, continue
  - поиск первого, else
  - вложенные циклы
  - ленивый ввод с помощью eval(input())
  - методы объектов, dir(объект) — введение
  - форматирование строк
- Практика
  - Таблица умножения
  - *TODO*!

== День 4 ==
- Python
  - Функции

== День 5 ==
- Python
  - объекты и методы
  - списки и их методы
   - a is b

== День 6 ==
- Python
  - строки
  - словари

== День 7 ==
- Python
  - Классы

== День 8 ==
- Python
  - Ещё классы и примеры

== День 9 ==
- Какой-нибудь фреймворк

== День 10 ==
- Использование этого фреймворка
Примерный распорядок дня
 * 10:00-10:30 — повторение и ответы на вопросы
 * 10:30-13:30 — лекции+семинары
 * 13:30-14:00 — обед
 * 14:00-16:00 — практика

Предполагается последовательно проходить этот план, расставляя пометки, сколько удалось сделать за день.
 * {*} — лабораторные работы / семинары (воспроизведение доски или тривиальные упражнения)
 * {i} — практические задания ([[https://uneex.altlinux.org|решения выкладываются сюда]])

'''Рекомендации по самостоятельному изучению'''
 * Д/З: установить [[http://python.org|Python]] и [[http://geany.org|Geany]] (можно другие IDE) дома, если есть цель научиться чему-то ненулевому
 * Д/З: Щёлкать [[py3tut:|tutorial]] (определяем, кому интересно)

<<TableOfContents()>>

== День 1 (3 июля) ==
=== Знакомство ===
 * Знакомство, определение уровня знаний и глубины изложения (утро)
 * Орг: конспекты (c двух сторон: Linux+Python), практика обязательна
 * FOSS: сообщество и ПО, Linux, Python
=== Linux и командная строка ===
 * «цветочек»+
  * Ядро, программный интерфейс
  * Утилиты, командный интерфейс
  * ФС, пространство имён, файловые объекты
 * ⇒ командная строка (введение)
  * КС как диалог
  * shell: интерпретатор командной строки, ЯП, оболочка надо другими программами
  * договорённости о командной строке (ключи)
  * переменные, где лежат команды (пространство имён), PATH
  * Примеры команд: - ls, cp, rm, mv, mkdir, echo, перенаправление В/В
  * имена файлов, ln, ls -i
  * Встроенная помощь man
 * {*}
  * посмотреть содержимое корня
  * посмотреть все файлы в текущем каталоге
  * посмотреть документацию к известным командам
  * создать файл, переименовать
  * создать каталог, скопировать туда файл, удалить каталог
=== Python и командная строка ===
  * объекты, их типы
  * действия над объектами
  * неявная динамическая типизация
  * преобразование типов, type() (в т. ч. type(a)(b)) и простейший ввод-вывод
  * пространства имён, связывание объектов именами, dir()
  * множественное связывание, id()
  * help()
 * {*}
  * вычисление формул
  * поэтапное вычисление формул с использованием имён
  * online python tutor: демонстрация связывания
=== Сценарии ===
 * Текстовый редактор vs IDE
 * Linux, shebang
 * программа на Python
 * {*}
  * Использование geany
  * примитивный сценарий на shell
  * сделать сценарий исполняемым и переместить в каталог `$HOME/bin/`
  * примитивный сценарий на Python

== День 2 (4 июля) ==
 * понятие о модулях, `from math import *`
 * {i}
  * ручное развёртывание бинарного возведения в степень (например, как получить 3^21^?)
  * [[http://narhoz-chita.ru/zadachnik/Glava01/index01.htm|вычисление формул]]
=== Условные операторы и выражения ===
 * логический тип, операции сравнения
 * условное выражение a if b else c
 * базовый if
 * форматирование отступами
 * if / elif* / else
 * {*}
  * ввести два числа, вывести наибольшее
   * условным выражением
   * условным оператором
  * ввести два числа, вывести, больше, меньше или равно первое второму
  * ввести три числа, проверить неравенство треугольника (вложенный if)
 * {i}
  * ввести три числа, найти наибольшее (вложенный if)
   * условным выражением
   * условным оператором
=== Алгебра логики ===
 * пустой объект, примеры
 * ⇒ ''любое'' выражение в условии
 * таблицы истинности
 * логические операции Python, их таблицы истинности
 * примеры
 * {*}
  * ввести три числа, проверить неравенство треугольника (с помощью `or`)
 * {i}
  * квадратное уравнение с ненулевым '''a'''
  * [[http://narhoz-chita.ru/zadachnik/Glava02/index02.htm|условные формулы №57]]
=== Цикл while ===
 * каноническая схема цикла: инициализация, проверка условия, тело, изменение
  * пример: цикл по вводу
 * {*}
  * подсчёт произведения (ввод до 0)
  * сумма N элементов арифметической прогрессии (циклом)
  * факториал

 * {i}
  * с какого элемента сумма арифметической прогрессии превысит N?
  * таблица умножения на N (в столбик)
  * подсчёт среднего (ввод до 0)
=== Циклы (более сложные случаи) ===
 * условия внутри циклов, break, continue
 * поиск первого, else
 * вложенные циклы
 * {*}
  * Сумма только положительных (ввод до 0)
  * одновременный подсчёт суммы и произведения положительных чисел (используется continue для отрицательных)
  * ввести ненулевые числа, проверить, есть ли среди них отрицательные
   * без else (с break)
   * с else
  * большая таблица умножения в столбик
 * {i}
  * таблица умножения в виде матрицы ''по столбцам'' (без форматирования)

== День 3 (5 июля) ==
Последовательности (введение)
=== Хранимые последовательности ===
 * (строки, кортежи, списки)
  * индексирование, в т. ч. отрицательное
  * операции поэлементного сравнения
   * операция `is` на примере списков
  * операции `+` и `*`
  * секционирование
   * обычное
   * с шагом
   * умолчания
  * {*}
   * какая последовательность больше и почему?
   * начальный, средний и конечный элемент
   * элементы, стоящие на 1,4,7, и т. д. местах (NB off by 1)
  * {i}
   * сначала элементы, стоящие на нечётных местах, затем — на чётных, задом наперёд
 * цикл прохода по последовательности for
  * break, '''continue''', else
  * {*}
   * выбор максимума
   * поиск 0
=== Вычисляемые последовательности ===
 * (`range()`, `enumerate()`)
 * типичный `for`
 * {*}
  * переписать на for кое-какие примеры с while
 * {i}
  * ввести последовательность чисел, вывести ''второй максимум'', то есть элемент, больше которого в последоватнльности только одно значение, например, для 1,1,2,2,7,7,3,3,5,5 второй максимум — это 5
=== Циклические конструкторы ===
 * Конструктор списка
 * Конструктор генератора, работа генератора, цикл for и генераторы
 * Как работает множественное связывание
  * распаковка последовательностей при связывании
  * в цикле for (последовательность последовательностей)
  * `a,b,*c,d = "Qwertyuiop"`
=== Кратко о строках ===
  * +, *
  * {{{"".format()}}}
 * {i}
  * Вывести все стороны и площади треугольников, стороны которых — однозначные положительные целые числа (не надо использовать конструктор, это жесть!)
   * использовать формулу Герона
   * не забыть, что 1 2 3, 1 3 2 и прочие перестановки — один и тот же треугольник, выводить один раз1
  * вывести таблицу умножения от 1 до 12 (сначала без {{{"".format()}}}, потом (''если успеете'') с ним):
    {{{
    1*1 = 1 2*1 = 2 3*1 = 3
    1*2 = 2 2*2 = 4 3*2 = 6
    ...
    1*12 = 12 2*12 = 24 3*12 = 36
    4*1 = 4 5*1 = 5 6*1 = 6
    4*2 = 8 5*2 = 10 6*2 = 12
    ...
    4*12 = 48 5*12 = 60 6*12 = 72
    7*1 = 7 8*1 = 8 9*1 = 9
    7*2 = 14 8*2 = 16 9*2 = 18
    ...
    }}}
  * Ввести строку, вывести, сколько в ней гласных (подсказка: `c in "aeoiu"` :) ), ''методами не пользоваться''
  * Ввести список запрещённых слов в формате "слово1","слово2",..., затем вводить строки до тех пор пока последняя не окажется пустой (это так же, как ввод до 0). Вывести, сколько строк содержали запрещённые слова

== День 4 (6 июля) ==
=== Функции (введение) ===
 * Задача повторного использования кода — макросы и подпрограммы
 * Функции в Python
  * Функция — это запись алгоритма обработки данных, а не преобразование
  * ''duck typing''
  * вызов функции — выражение, всегда есть возвращаемое значение — любой объект (например, None)
  * возвращаемое значение можно не использовать
  * Определение функции, формальные параметры
   * {*} простые примеры
  * Локальное пространство имён функции
   * просто вывод `dir()`
   * независимость имён
   * `locals()` и `globals()`
    * {*} просто вывод
   * порядок просмотра пространств
   * автоопределение локальных имён; global
    * {*}
  * {i}
   * '''''с этого момента и до конца курса каждые модуль/функция/класс в заданиях {i} должны содержать docstring с пояснением, что они делают'''''
   * ''(задания в этом'' {i} ''-блоке оформить в виде интерактивной программы и в виде модуля)''
   * Функция — сумма цифр
    * Ввести последовательность, вывести элемент с минимальной суммой цифр
     * <!> можно с помощью `min()` — как?
   * функция — расстояние между точками ( <!> на самом деле есть :) )
    * Ввести список пар вида `(1,2), (3,4), (100,100) …`, найти самый удалённые точки
 * Распаковка и запаковка параметров функций
  * ничего и нет, только списки
  * Функции с переменным количеством параметров
   * {*}
  * Распаковка последовательности при вызове
   * {*}, в т. ч. `print(*seq)`
 * {i}
  * функция, возвращающая ''список'' только целочисленных из всех параметров
 * ''Всё остальное про функции — потом, не сегодня''

=== Методы объектов; модули ===
 * Поля объектов, инкапсуляция
  * `dir(объект)`
  * `объект.имя_поля`
  * методы и … поля
 * Модули, `sys.path`
  * программа на Python как модуль
  * встроенная и в среду Python, и в язык Python документация
   * `help()`
   * документирование собственного кода
    * docstring
    * `object.__doc__`
  * {*}

=== Строки и их методы ===
 * Строковые методы
  * все (в т. ч. `in`)
  * `replace()`
   * {*}
  * `split()` и `join()`
   * {*}
 * {i}
  * Ввести строку, заменить в ней последовательности "-" на один минус
  * Ввести запрещённое сочетание букв и строку. Вывести строку, в которой запрещённое сочетание букв не встречается (например, "ab" и "aabbcaabbb" → "cb")
  
=== Списки и их методы ===
 * все методы
 * стек, суть pop()/push(), эффективность
 * очередь и deque()
 * {i} ''Функция: список -> список''
  * Список всех делителей числа
  * Убрать из списка подряд идущие одинаковые элементы
   * <!> Для уверенных в себе: То же, но повторять, пока таких групп не останется.

== День 5 (7 июля) ==

=== Ещё немного обо всём ===
 * `zip(последовательность, последовательность, ...)`
  * удобнее всего одинаковой длины
  * столько же элементов, сколько в аргументе ''наименьшей'' длины, остальные отбрасываются
  * {*}
   * (07.02) Ввести матрицу N*M, выдать транспонированную матрицу
  * {i}
   * Ввести N строк, проделать то же самое
 * `lambda arguments: returnexpr`
 * `python3 matrix_generator.py | python3 another_program.py`
  * работает везде: Linux, Windows, OS X, any other Unix
  * в т. ч. возможность писать самые настоящие автоматические тесты для своих программ!

=== Про random ===
 * Случайное и неслучайное, зачем нужно
 * Датчик случайных чисел
  * неслучайность
  * воспроизводимость, seed()
 * Модуль `random`
  * `random()` , `randint()`, `randrange()`
  * `choice()`, `shuffle()`, `sample()`
  * `seed()`
 * {*}
  * Случайное число на отрезке A…B
   * Гистограмма (список частот для возможных значений)
  * Перемешать строку
  * Случайные слова случайной длины
  * Генератор значений для 07.02 (транспонирование матрицы)
 * {i}
  * ''в каждой функции, которую пишете, краткий docstring, к хорошему тону надо привыкать''
  * Функция, с вероятностью 1/3 выдающая `"yes"`, с 2/3 `"no"`. (без модуля `random`, кроме `random.random`)
   * Программа, выводящая выборку из N вызовов такой функции и гистограмму (кол-во "yes" и кол-во "no")
  * Функция, выдающая случайные '''произносимые''' слова случайной длины (запихать в модуль)
   * `if __name__ == "__main__":` краткое демо
  * Используя модуль произносимых слов: функция, генерирующая несколько предложений из нескольких случайных слов.
  * Используя модуль-генератор предложений: ввести слово; посчитать, сколько раз оно встретилось в сгенерированных предложениях.
   * ''можно не слово, а букву или комбинацию букв, с точки зрения Python одно и то же''
  * В первой программе сгенерировать двумерный список чисел случайно и вывести на экран
   * в другой: среди всех минимумов в строчках полученной матрицы найти максимум
   * ''тестируем при помощи конвейера (что-то сродни `python3 gen.py | python3 program.py`)''
   * ''обратите внимание, что по pipe между программами проходит текст, т. е. строчки символов''


=== Про черепаху ===
 * Модуль `turtle`
 * Основные команды
 * Как закрасить область
 * {i}
  * Функция, рисующая домик размера N пикселей.
  * Функция, рисующая ёлочку из n треугольников размера от k до l
  * лес с разными ёлочками
   * <!> немного не параллельными
 * ''дальше не успеем''

== День 6 (10 июля) ==

 * Q: был вопрос о разнице между `"` и `'` в Python.
  * A: Разницы нет никакой, кроме стилистической: хорошим тоном считается использовать для docstring двойные кавычки.
  * см. [[https://www.python.org/dev/peps/pep-0257/|PEP 257]] на эту тему

=== Работа с файлами ===
 * Текстовые файлы
  * open(), read() / write() / close()
  * readlines() он же сам файл, print(.. file=)
  * "b/t" — str или bytes
  * `with`
 * {*}
  * вводить числа до 0, записывать в файл только положительные
 * файлы с данными
  * если данные наши: сериализация/десериализация, `pickle` (json, xml, …)
   * dump[s]()/load[s]()
  * если данные готовы: `struct`
   * byte order :(
   * pack()/unpack()
 * {i}
  * Если в командной строке программы пять (с `argv[0]` — 6) параметров, то это:
   1. имя выходного файла
   1. имя,
   1. фамилия
   1. возраст (целое число
   1. средний балл (вещественное)
    сериализовать эти данные в файл;
   а если параметр только один (argv[1]), это имя входного файла, десериализовать их оттуда и вывести
  * То же, что и выше, но с помощью struct

=== Словари и множества ===
 * Задача хранения и индексирования
  * сложных данных
  * просто слишком больших данных
  * +невосстановимое хеширование
 * Свойства хеш-функции
  * неоднозначность
  * распределённость по ОЗ (на конкретных данных!)
   * разброс для почти похожих
  * невосстановимость объекта (сравнение без раскрытия)
⇒ Возможности
 * индексирование
 * сортировка и поиск
Примеры
 * a % b
 * int(sin(b)*1000)%100
 * `hash()`, какие объекты хешируются
 * ...
 * {*}
  * если есть различные значения синуса, какой к ним хороший хеш?
  * идентификаторы
Множество — просто хеш-таблица
 * Задание, в т. ч. циклический конструктор
 * Операции над множествами, методы
 * Типичное использование
 * {*}
  * каких букв не хватает
 * {i}
  * вводятся предложения, проверить, есть ли общее слово (регистр букв игнорировать)
Словарь — множество с атрибутами, т. е. соответствие множества хешируемых ключей множеству произвольных объектов
 * Задание, в т. ч. циклический конструктор
 * Операции над множествами, методы
 * Типичное использование:
  * ...
  * globals()/locals()
  * именные параметры функции
 * {*}
  * Словари и счётчики
   * ручная реализация счётчика
   * collections
   * тестирование хеш-функции: много входных данных и гистограмма
 * {i}
  * генератор файла с N случайными словами (N задаётся из командной строки), причём 1-е слово встречается ровно 1 раз, второе — 2 раза, …, N-е — N раз
  * подсчёт слов в файле, гистограмма вида
  {{{
  ######## word1
  ############################# word2
  ################### word3
  ...
  }}}
   где максимальная длина "#######" — 50 символов
  * самое популярное слово длиной >3 в файле [[attachment:anna.txt]]

== День 7 (11 июля) ==

=== Генераторы ===
 * позволяют по собственным правилам конструировать вычислимые последовательности
  * даже бесконечные!
 * выглядят как самые обычные функции...
  * ...но в них есть хотя бы одно ключевое слово `yield`
  * Как только Python видит в теле функции yield, он понимает, что это генератор
  * Отличия функции-генератора от не-генератора:
   * Функция-генератор создаёт и возвращает `generator object`, по которому можно ходить
    * `iterable(gen) == True`
    * `for i in gen: blabla`
    * `next(gen)`
     * ''...кстати, не что иное, как'' `gen.__next__()`
     * алгоритм в теле функции выполняется ''не'' при её вызове, а именно в методе `gen.__next__`
    * справедливы все остальные свойства вычислимой последовательности
   * `yield` не завершает выполнение алгоритма в функции-генераторе, а лишь приостанавливает
    * их может быть сколько угодно
    * `next(gen)` начинает (соотв. продолжает) выполнение функции до ближайшего `yield`
   * `return` в генераторе означает мгновенный выброс `StopIteration`
    * как и достижение конца тела
    * TODO а что происходит с возвращаемым значением? игнорируется?
 * {*}
  * Руками реализовать `range(10,70,2)`
 * {i}
  * Вычисление Пи с помощью генератора

=== PyPI ===
 * [[pypi.python.org]]
  * централизованное хранилище модулей для Python
 * `pip3`
  * кроссплатформенный!
  * `pip3 install <package>`
   * в Linux (как и в любой разумной системе) устанавливать что-то прямо в систему может только администратор
    * поэтому, чтобы поставить ''себе в домашний каталог'': `pip3 install --user <package>`
  * `pip3 search <package>`
 * `sys.path`
 
=== PyGame ===
 * не забываем о `help()`
 * огромный пакет, состоящий из множества модулей
 * {*}
  * Линии, примитивные фигуры, ёлки из треугольников
  * Квадрат, который можно тащить мышью
  * Анимированный движущийся квадратик (движение растянуто во времени)
 * {i}
  * Несколько квадратиков; иметь возможность плавно тащить мышью каждый
  * Заставить едущий квадрат отражаться от стенок окна
   * <!> Тормоз и газ
  * '''К зачёту''': Совместить две предыдущие.
-----

== TODO ==
=== turtle ===
 * {*}
  * Попробовать нарисовать черепахой график функции y=sin(x) в диапазоне -4<=x<=5 (использовать абсолютные координаты, то есть функцию goto(x,y))
  * Осознать, что:
   * График — это не кривая, а ломаная (передвижение черепашки от точки к точке по прямой)
   * Чем больше точек в этой ломаной, тем более она похожа на график, пускай точек будет N=100
   * Если рисовать синус, как он есть, получается еле заметный червячок
   * Чтобы график было хорошо видно, y-координаты надо как-то увеличивать, например, умножать на 100, а x-коордмнаты — на 50
 * {*}
  * Нарисовать черепахой график функции y=sin(x) из ста точек в диапазоне A<=x<=B, где A и B вводятся и поначалу равны, как и раньше, -4 и 5
  * Осознать, что
   * У забора 100 досок и 99 щелей (N и N-1). У графика N точек и N-1 отрезок. Это значит, что в цикле, который генерирует очередное X для того, чтобы вычислить sin(x), самое первое значение должно быть A, а самое последнее — B, и всего таких значений должно быть N
 * Написать для этого функцию diap(N,i,A,B):
  * A и B — диапазон
  * N — общее количество точек, включая первую и последнюю.
  * i — номер очередной точки
  * возвращать функция должна число в диапазоне от A до B, причём при i==0 — A, а при i==N-1 (да-да, не N же!) — B
 * Нарисовать черепахой график функции y=sin(x) из ста точек в диапазоне A<=x<=B, где A и B вводятся, и график получается разумный при abs(B-A)<200 (дальше частокол выйдет)

=== Немного про eval() ===
Осознать природу функции eval()
https://docs.python.org/3/library/functions.html?highlight=eval#eval

 * {*} Упражнение: ввести *в виде строки* произвольную формулу от x (в ней могут встречаться функции из math), ввести x, вывести (с помощью eval()) результат её вычисления
 * Решить предыдущее упражнение, написав *функцию* f(x): , при этом сама программа должна выглядеть примерно так:
{{{
formulae = input()
x = float(input())
print(f(x))
}}}
(очевидно, в этой функции будет использовано глобальное имя formulae и eval())

=== Рисуем график дальше ===
 * Вспомнить про аффинные преобразования координат. Из них нам нужно движение и перенос, а поворот не нужен. Если не вспоминается — не страшно. Общая идея
  * Есть вещественное число X на отрезке A…B. Нам нужно получить число P на отрезке Q…R, которое делит это отрезок в той же пропорции
  * Записать пропорцию и вывести из неё формулу P=что-то-там-от-X
 * Написать функцию scale(L,M,X,Q,R), которая по числу X на отрезке L…M вычисляет число P на отрезке Q…R, делящее этот отрезок в той же пропорции
 * scale(L,M,L,Q,R) == Q, scale(L,M,M,Q,R) == R, (подсказка) scale(L,M,(L+M)/2,Q,R) == (Q+R)/2
  * (спойлер!) вычесть начало старого отрезка (получится что-то от 0), поделить на длину отрезка (получится что-то от 0 до 10), умножить на длину нового отрезка, прибавить его начало
 * Осознать, что это более общий вариант функции diap()
  * Переписать «график синуса» с использованием scale() вместо diap()
  * Переписать его далее, с использованием scale() вместо тупого умножения X и Y кооринат (размер экрана мы, допустим, знаем, что-то типа -400,400/-300,300 или как-то так, проверить)
    * график наконец-то будет располагаться по центру
    
 * Попробовать вводить не только диапазон, но и саму формулу (см. выше упражнение про функцию f()), поначалу эта формула == "f(x)", с ней должно работать хорошо
 * Осознать, что
  * Область значений sin(x) — -1…1, а других формул — нет :)
  * Для того, чтобы нарисовать график произвольной функции на отрезке, надо знать диапазон её значений на этом отрезке
    * этот диапазон использовать в scale() при вычислении y-координаты очередной точки на экране
    * Можно, например, запустить цикл с вычислением функции на всех точках, но не рисовать ничего, а только искать минимум и максимум значений (Q и R), а потом уже запустить его ещё раз и рисовать, зная Q и R
 * Переписать программу так, чтобы
  * В цикле создавался список значений функции на отрезке (назовём его g[])
  * Тогда минимум и максимум — это просто min(g) и max(g) (спасибо, Питон!)
  * Можно и список x-ов тоже генерировать, чобы два раза не вычислять
 * Украсить
  * Нарисовать оси координат
  * Написать, где X, где Y
  * Написать, что за функция

=== О рекурсии ===
 * Определение рекурсии
 * прямая и непрямая
 * рекурсия — это цикл, но
  * своё пространство имён
  * ''рост'' пространств имён
 * Почему не факториал
 * {*}
  * '''TODO'''

-----
Здесь пока не разобрано

=== Неподшитое ===

 * Исключения
 * Генераторы, конструкторы генераторов
 * Декораторы, зачем нужны
 * Модули как пространства имён
 * Классы, …, перегрузка операций
 * Ещё классы, объектное планирование и ООП

=== Понятие оценки сложности алгоритма ===
 * Оценка сложности: количество операция на единицу обрабатываемых данных
  * насколько замедляется алгоритм при количестве данных
   * +1
   * *2
   * → производная!
 * Индексирование
 * Поиск
 * все возможные сочетания

=== Бинарный поиск и сортировка ===
 * Бинарный поиск и оценка его сложности
 * Примитивная сортировка и оценка её сложности
 * Сортировка слиянием
 * «Быстрая» сортировка, худший случай
 * Сортировка кучей
 * {i}
  * бинарный поиск строк в файле
  * сортировка файла слиянием

Примерный распорядок дня

  • 10:00-10:30 — повторение и ответы на вопросы
  • 10:30-13:30 — лекции+семинары
  • 13:30-14:00 — обед
  • 14:00-16:00 — практика

Предполагается последовательно проходить этот план, расставляя пометки, сколько удалось сделать за день.

  • {*} — лабораторные работы / семинары (воспроизведение доски или тривиальные упражнения)

  • {i} — практические задания (решения выкладываются сюда)

Рекомендации по самостоятельному изучению

  • Д/З: установить Python и Geany (можно другие IDE) дома, если есть цель научиться чему-то ненулевому

  • Д/З: Щёлкать tutorial (определяем, кому интересно)

День 1 (3 июля)

Знакомство

  • Знакомство, определение уровня знаний и глубины изложения (утро)
  • Орг: конспекты (c двух сторон: Linux+Python), практика обязательна
  • FOSS: сообщество и ПО, Linux, Python

Linux и командная строка

  • «цветочек»+
    • Ядро, программный интерфейс
    • Утилиты, командный интерфейс
    • ФС, пространство имён, файловые объекты
  • ⇒ командная строка (введение)
    • КС как диалог
    • shell: интерпретатор командной строки, ЯП, оболочка надо другими программами
    • договорённости о командной строке (ключи)
    • переменные, где лежат команды (пространство имён), PATH
    • Примеры команд: - ls, cp, rm, mv, mkdir, echo, перенаправление В/В
    • имена файлов, ln, ls -i
    • Встроенная помощь man
  • {*}

    • посмотреть содержимое корня
    • посмотреть все файлы в текущем каталоге
    • посмотреть документацию к известным командам
    • создать файл, переименовать
    • создать каталог, скопировать туда файл, удалить каталог

Python и командная строка

  • объекты, их типы
  • действия над объектами
  • неявная динамическая типизация
  • преобразование типов, type() (в т. ч. type(a)(b)) и простейший ввод-вывод
  • пространства имён, связывание объектов именами, dir()
  • множественное связывание, id()
  • help()
  • {*}

    • вычисление формул
    • поэтапное вычисление формул с использованием имён
    • online python tutor: демонстрация связывания

Сценарии

  • Текстовый редактор vs IDE
  • Linux, shebang
  • программа на Python
  • {*}

    • Использование geany
    • примитивный сценарий на shell
    • сделать сценарий исполняемым и переместить в каталог $HOME/bin/

    • примитивный сценарий на Python

День 2 (4 июля)

  • понятие о модулях, from math import *

  • {i}

    • ручное развёртывание бинарного возведения в степень (например, как получить 321?)

    • вычисление формул

Условные операторы и выражения

  • логический тип, операции сравнения
  • условное выражение a if b else c
  • базовый if
  • форматирование отступами
  • if / elif* / else
  • {*}

    • ввести два числа, вывести наибольшее
      • условным выражением
      • условным оператором
    • ввести два числа, вывести, больше, меньше или равно первое второму
    • ввести три числа, проверить неравенство треугольника (вложенный if)
  • {i}

    • ввести три числа, найти наибольшее (вложенный if)
      • условным выражением
      • условным оператором

Алгебра логики

  • пустой объект, примеры
  • любое выражение в условии

  • таблицы истинности
  • логические операции Python, их таблицы истинности
  • примеры
  • {*}

    • ввести три числа, проверить неравенство треугольника (с помощью or)

  • {i}

Цикл while

  • каноническая схема цикла: инициализация, проверка условия, тело, изменение
    • пример: цикл по вводу
  • {*}

    • подсчёт произведения (ввод до 0)
    • сумма N элементов арифметической прогрессии (циклом)
    • факториал
  • {i}

    • с какого элемента сумма арифметической прогрессии превысит N?
    • таблица умножения на N (в столбик)
    • подсчёт среднего (ввод до 0)

Циклы (более сложные случаи)

  • условия внутри циклов, break, continue
  • поиск первого, else
  • вложенные циклы
  • {*}

    • Сумма только положительных (ввод до 0)
    • одновременный подсчёт суммы и произведения положительных чисел (используется continue для отрицательных)
    • ввести ненулевые числа, проверить, есть ли среди них отрицательные
      • без else (с break)
      • с else
    • большая таблица умножения в столбик
  • {i}

    • таблица умножения в виде матрицы по столбцам (без форматирования)

День 3 (5 июля)

Последовательности (введение)

Хранимые последовательности

  • (строки, кортежи, списки)
    • индексирование, в т. ч. отрицательное
    • операции поэлементного сравнения
      • операция is на примере списков

    • операции + и *

    • секционирование
      • обычное
      • с шагом
      • умолчания
    • {*}

      • какая последовательность больше и почему?
      • начальный, средний и конечный элемент
      • элементы, стоящие на 1,4,7, и т. д. местах (NB off by 1)
    • {i}

      • сначала элементы, стоящие на нечётных местах, затем — на чётных, задом наперёд
  • цикл прохода по последовательности for
    • break, continue, else

    • {*}

      • выбор максимума
      • поиск 0

Вычисляемые последовательности

  • (range(), enumerate())

  • типичный for

  • {*}

    • переписать на for кое-какие примеры с while
  • {i}

    • ввести последовательность чисел, вывести второй максимум, то есть элемент, больше которого в последоватнльности только одно значение, например, для 1,1,2,2,7,7,3,3,5,5 второй максимум — это 5

Циклические конструкторы

  • Конструктор списка
  • Конструктор генератора, работа генератора, цикл for и генераторы
  • Как работает множественное связывание
    • распаковка последовательностей при связывании
    • в цикле for (последовательность последовательностей)
    • a,b,*c,d = "Qwertyuiop"

Кратко о строках

  • +, *
  • "".format()

  • {i}

    • Вывести все стороны и площади треугольников, стороны которых — однозначные положительные целые числа (не надо использовать конструктор, это жесть!)
      • использовать формулу Герона
      • не забыть, что 1 2 3, 1 3 2 и прочие перестановки — один и тот же треугольник, выводить один раз1
    • вывести таблицу умножения от 1 до 12 (сначала без "".format(), потом (если успеете) с ним):

      •     1*1 = 1   2*1 = 2   3*1 = 3
            1*2 = 2   2*2 = 4   3*2 = 6
            ...
            1*12 = 12 2*12 = 24 3*12 = 36
            4*1 = 4   5*1 = 5   6*1 = 6
            4*2 = 8   5*2 = 10  6*2 = 12
            ...
            4*12 = 48 5*12 = 60 6*12 = 72
            7*1 = 7   8*1 = 8   9*1 = 9
            7*2 = 14  8*2 = 16  9*2 = 18
            ...
    • Ввести строку, вывести, сколько в ней гласных (подсказка: c in "aeoiu" :) ), методами не пользоваться

    • Ввести список запрещённых слов в формате "слово1","слово2",..., затем вводить строки до тех пор пока последняя не окажется пустой (это так же, как ввод до 0). Вывести, сколько строк содержали запрещённые слова

День 4 (6 июля)

Функции (введение)

  • Задача повторного использования кода — макросы и подпрограммы
  • Функции в Python
    • Функция — это запись алгоритма обработки данных, а не преобразование
    • duck typing

    • вызов функции — выражение, всегда есть возвращаемое значение — любой объект (например, None)
    • возвращаемое значение можно не использовать
    • Определение функции, формальные параметры
      • {*} простые примеры

    • Локальное пространство имён функции
      • просто вывод dir()

      • независимость имён
      • locals() и globals()

        • {*} просто вывод

      • порядок просмотра пространств
      • автоопределение локальных имён; global
        • {*}

    • {i}

      • с этого момента и до конца курса каждые модуль/функция/класс в заданиях {i} должны содержать docstring с пояснением, что они делают

      • (задания в этом {i} -блоке оформить в виде интерактивной программы и в виде модуля)

      • Функция — сумма цифр
        • Ввести последовательность, вывести элемент с минимальной суммой цифр
          • <!> можно с помощью min() — как?

      • функция — расстояние между точками ( <!> на самом деле есть :) )

        • Ввести список пар вида (1,2), (3,4), (100,100) …, найти самый удалённые точки

  • Распаковка и запаковка параметров функций
    • ничего и нет, только списки
    • Функции с переменным количеством параметров
      • {*}

    • Распаковка последовательности при вызове
      • {*}, в т. ч. print(*seq)

  • {i}

    • функция, возвращающая список только целочисленных из всех параметров

  • Всё остальное про функции — потом, не сегодня

Методы объектов; модули

  • Поля объектов, инкапсуляция
    • dir(объект)

    • объект.имя_поля

    • методы и … поля
  • Модули, sys.path

    • программа на Python как модуль
    • встроенная и в среду Python, и в язык Python документация
      • help()

      • документирование собственного кода
        • docstring
        • object.__doc__

    • {*}

Строки и их методы

  • Строковые методы
    • все (в т. ч. in)

    • replace()

      • {*}

    • split() и join()

      • {*}

  • {i}

    • Ввести строку, заменить в ней последовательности "-" на один минус
    • Ввести запрещённое сочетание букв и строку. Вывести строку, в которой запрещённое сочетание букв не встречается (например, "ab" и "aabbcaabbb" → "cb")

Списки и их методы

  • все методы
  • стек, суть pop()/push(), эффективность
  • очередь и deque()
  • {i} Функция: список -> список

    • Список всех делителей числа
    • Убрать из списка подряд идущие одинаковые элементы
      • <!> Для уверенных в себе: То же, но повторять, пока таких групп не останется.

День 5 (7 июля)

Ещё немного обо всём

  • zip(последовательность, последовательность, ...)

    • удобнее всего одинаковой длины
    • столько же элементов, сколько в аргументе наименьшей длины, остальные отбрасываются

    • {*}

      • (07.02) Ввести матрицу N*M, выдать транспонированную матрицу
    • {i}

      • Ввести N строк, проделать то же самое
  • lambda arguments: returnexpr

  • python3 matrix_generator.py | python3 another_program.py

    • работает везде: Linux, Windows, OS X, any other Unix
    • в т. ч. возможность писать самые настоящие автоматические тесты для своих программ!

Про random

  • Случайное и неслучайное, зачем нужно
  • Датчик случайных чисел
    • неслучайность
    • воспроизводимость, seed()
  • Модуль random

    • random() , randint(), randrange()

    • choice(), shuffle(), sample()

    • seed()

  • {*}

    • Случайное число на отрезке A…B
      • Гистограмма (список частот для возможных значений)
    • Перемешать строку
    • Случайные слова случайной длины
    • Генератор значений для 07.02 (транспонирование матрицы)
  • {i}

    • в каждой функции, которую пишете, краткий docstring, к хорошему тону надо привыкать

    • Функция, с вероятностью 1/3 выдающая "yes", с 2/3 "no". (без модуля random, кроме random.random)

      • Программа, выводящая выборку из N вызовов такой функции и гистограмму (кол-во "yes" и кол-во "no")
    • Функция, выдающая случайные произносимые слова случайной длины (запихать в модуль)

      • if __name__ == "__main__": краткое демо

    • Используя модуль произносимых слов: функция, генерирующая несколько предложений из нескольких случайных слов.
    • Используя модуль-генератор предложений: ввести слово; посчитать, сколько раз оно встретилось в сгенерированных предложениях.
      • можно не слово, а букву или комбинацию букв, с точки зрения Python одно и то же

    • В первой программе сгенерировать двумерный список чисел случайно и вывести на экран
      • в другой: среди всех минимумов в строчках полученной матрицы найти максимум
      • тестируем при помощи конвейера (что-то сродни python3 gen.py | python3 program.py)

      • обратите внимание, что по pipe между программами проходит текст, т. е. строчки символов

Про черепаху

  • Модуль turtle

  • Основные команды
  • Как закрасить область
  • {i}

    • Функция, рисующая домик размера N пикселей.
    • Функция, рисующая ёлочку из n треугольников размера от k до l
    • лес с разными ёлочками
      • <!> немного не параллельными

  • дальше не успеем

День 6 (10 июля)

  • Q: был вопрос о разнице между " и ' в Python.

    • A: Разницы нет никакой, кроме стилистической: хорошим тоном считается использовать для docstring двойные кавычки.
    • см. PEP 257 на эту тему

Работа с файлами

  • Текстовые файлы
    • open(), read() / write() / close()
    • readlines() он же сам файл, print(.. file=)
    • "b/t" — str или bytes
    • with

  • {*}

    • вводить числа до 0, записывать в файл только положительные
  • файлы с данными
    • если данные наши: сериализация/десериализация, pickle (json, xml, …)

      • dump[s]()/load[s]()
    • если данные готовы: struct

      • byte order :(

      • pack()/unpack()
  • {i}

    • Если в командной строке программы пять (с argv[0] — 6) параметров, то это:

      1. имя выходного файла
      2. имя,
      3. фамилия
      4. возраст (целое число
      5. средний балл (вещественное)
        • сериализовать эти данные в файл;
        а если параметр только один (argv[1]), это имя входного файла, десериализовать их оттуда и вывести
    • То же, что и выше, но с помощью struct

Словари и множества

  • Задача хранения и индексирования
    • сложных данных
    • просто слишком больших данных
    • +невосстановимое хеширование
  • Свойства хеш-функции
    • неоднозначность
    • распределённость по ОЗ (на конкретных данных!)
      • разброс для почти похожих
    • невосстановимость объекта (сравнение без раскрытия)

⇒ Возможности

  • индексирование
  • сортировка и поиск

Примеры

  • a % b
  • int(sin(b)*1000)%100
  • hash(), какие объекты хешируются

  • ...
  • {*}

    • если есть различные значения синуса, какой к ним хороший хеш?
    • идентификаторы

Множество — просто хеш-таблица

  • Задание, в т. ч. циклический конструктор
  • Операции над множествами, методы
  • Типичное использование
  • {*}

    • каких букв не хватает
  • {i}

    • вводятся предложения, проверить, есть ли общее слово (регистр букв игнорировать)

Словарь — множество с атрибутами, т. е. соответствие множества хешируемых ключей множеству произвольных объектов

  • Задание, в т. ч. циклический конструктор
  • Операции над множествами, методы
  • Типичное использование:
    • ...
    • globals()/locals()
    • именные параметры функции
  • {*}

    • Словари и счётчики
      • ручная реализация счётчика
      • collections
      • тестирование хеш-функции: много входных данных и гистограмма
  • {i}

    • генератор файла с N случайными словами (N задаётся из командной строки), причём 1-е слово встречается ровно 1 раз, второе — 2 раза, …, N-е — N раз
    • подсчёт слов в файле, гистограмма вида
        ########                                  word1
        #############################             word2
        ###################                       word3
        ...
      • где максимальная длина "#######" — 50 символов
    • самое популярное слово длиной >3 в файле anna.txt

День 7 (11 июля)

Генераторы

  • позволяют по собственным правилам конструировать вычислимые последовательности
    • даже бесконечные!
  • выглядят как самые обычные функции...
    • ...но в них есть хотя бы одно ключевое слово yield

    • Как только Python видит в теле функции yield, он понимает, что это генератор
    • Отличия функции-генератора от не-генератора:
      • Функция-генератор создаёт и возвращает generator object, по которому можно ходить

        • iterable(gen) == True

        • for i in gen: blabla

        • next(gen)

          • ...кстати, не что иное, как gen.__next__()

          • алгоритм в теле функции выполняется не при её вызове, а именно в методе gen.__next__

        • справедливы все остальные свойства вычислимой последовательности
      • yield не завершает выполнение алгоритма в функции-генераторе, а лишь приостанавливает

        • их может быть сколько угодно
        • next(gen) начинает (соотв. продолжает) выполнение функции до ближайшего yield

      • return в генераторе означает мгновенный выброс StopIteration

        • как и достижение конца тела
        • TODO а что происходит с возвращаемым значением? игнорируется?
  • {*}

    • Руками реализовать range(10,70,2)

  • {i}

    • Вычисление Пи с помощью генератора

PyPI

  • pypi.python.org

    • централизованное хранилище модулей для Python
  • pip3

    • кроссплатформенный!
    • pip3 install <package>

      • в Linux (как и в любой разумной системе) устанавливать что-то прямо в систему может только администратор
        • поэтому, чтобы поставить себе в домашний каталог: pip3 install --user <package>

    • pip3 search <package>

  • sys.path

PyGame

  • не забываем о help()

  • огромный пакет, состоящий из множества модулей
  • {*}

    • Линии, примитивные фигуры, ёлки из треугольников
    • Квадрат, который можно тащить мышью
    • Анимированный движущийся квадратик (движение растянуто во времени)
  • {i}

    • Несколько квадратиков; иметь возможность плавно тащить мышью каждый
    • Заставить едущий квадрат отражаться от стенок окна
      • <!> Тормоз и газ

    • К зачёту: Совместить две предыдущие.


TODO

turtle

  • {*}

    • Попробовать нарисовать черепахой график функции y=sin(x) в диапазоне -4<=x<=5 (использовать абсолютные координаты, то есть функцию goto(x,y))

    • Осознать, что:
      • График — это не кривая, а ломаная (передвижение черепашки от точки к точке по прямой)
      • Чем больше точек в этой ломаной, тем более она похожа на график, пускай точек будет N=100
      • Если рисовать синус, как он есть, получается еле заметный червячок
      • Чтобы график было хорошо видно, y-координаты надо как-то увеличивать, например, умножать на 100, а x-коордмнаты — на 50
  • {*}

    • Нарисовать черепахой график функции y=sin(x) из ста точек в диапазоне A<=x<=B, где A и B вводятся и поначалу равны, как и раньше, -4 и 5

    • Осознать, что
      • У забора 100 досок и 99 щелей (N и N-1). У графика N точек и N-1 отрезок. Это значит, что в цикле, который генерирует очередное X для того, чтобы вычислить sin(x), самое первое значение должно быть A, а самое последнее — B, и всего таких значений должно быть N
  • Написать для этого функцию diap(N,i,A,B):
    • A и B — диапазон
    • N — общее количество точек, включая первую и последнюю.
    • i — номер очередной точки
    • возвращать функция должна число в диапазоне от A до B, причём при i==0 — A, а при i==N-1 (да-да, не N же!) — B
  • Нарисовать черепахой график функции y=sin(x) из ста точек в диапазоне A<=x<=B, где A и B вводятся, и график получается разумный при abs(B-A)<200 (дальше частокол выйдет)

Немного про eval()

Осознать природу функции eval() https://docs.python.org/3/library/functions.html?highlight=eval#eval

  • {*} Упражнение: ввести *в виде строки* произвольную формулу от x (в ней могут встречаться функции из math), ввести x, вывести (с помощью eval()) результат её вычисления

  • Решить предыдущее упражнение, написав *функцию* f(x): , при этом сама программа должна выглядеть примерно так:

formulae = input()
x = float(input())
print(f(x))

(очевидно, в этой функции будет использовано глобальное имя formulae и eval())

Рисуем график дальше

  • Вспомнить про аффинные преобразования координат. Из них нам нужно движение и перенос, а поворот не нужен. Если не вспоминается — не страшно. Общая идея
    • Есть вещественное число X на отрезке A…B. Нам нужно получить число P на отрезке Q…R, которое делит это отрезок в той же пропорции
    • Записать пропорцию и вывести из неё формулу P=что-то-там-от-X
  • Написать функцию scale(L,M,X,Q,R), которая по числу X на отрезке L…M вычисляет число P на отрезке Q…R, делящее этот отрезок в той же пропорции
  • scale(L,M,L,Q,R) == Q, scale(L,M,M,Q,R) == R, (подсказка) scale(L,M,(L+M)/2,Q,R) == (Q+R)/2
    • (спойлер!) вычесть начало старого отрезка (получится что-то от 0), поделить на длину отрезка (получится что-то от 0 до 10), умножить на длину нового отрезка, прибавить его начало
  • Осознать, что это более общий вариант функции diap()
    • Переписать «график синуса» с использованием scale() вместо diap()
    • Переписать его далее, с использованием scale() вместо тупого умножения X и Y кооринат (размер экрана мы, допустим, знаем, что-то типа -400,400/-300,300 или как-то так, проверить)
      • график наконец-то будет располагаться по центру
  • Попробовать вводить не только диапазон, но и саму формулу (см. выше упражнение про функцию f()), поначалу эта формула == "f(x)", с ней должно работать хорошо
  • Осознать, что
    • Область значений sin(x) — -1…1, а других формул — нет :)

    • Для того, чтобы нарисовать график произвольной функции на отрезке, надо знать диапазон её значений на этом отрезке
      • этот диапазон использовать в scale() при вычислении y-координаты очередной точки на экране
      • Можно, например, запустить цикл с вычислением функции на всех точках, но не рисовать ничего, а только искать минимум и максимум значений (Q и R), а потом уже запустить его ещё раз и рисовать, зная Q и R
  • Переписать программу так, чтобы
    • В цикле создавался список значений функции на отрезке (назовём его g[])
    • Тогда минимум и максимум — это просто min(g) и max(g) (спасибо, Питон!)
    • Можно и список x-ов тоже генерировать, чобы два раза не вычислять
  • Украсить
    • Нарисовать оси координат
    • Написать, где X, где Y
    • Написать, что за функция

О рекурсии

  • Определение рекурсии
  • прямая и непрямая
  • рекурсия — это цикл, но
    • своё пространство имён
    • рост пространств имён

  • Почему не факториал
  • {*}

    • TODO


Здесь пока не разобрано

Неподшитое

  • Исключения
  • Генераторы, конструкторы генераторов
  • Декораторы, зачем нужны
  • Модули как пространства имён
  • Классы, …, перегрузка операций
  • Ещё классы, объектное планирование и ООП

Понятие оценки сложности алгоритма

  • Оценка сложности: количество операция на единицу обрабатываемых данных
    • насколько замедляется алгоритм при количестве данных
      • +1
      • *2
      • → производная!
  • Индексирование
  • Поиск
  • все возможные сочетания

Бинарный поиск и сортировка

  • Бинарный поиск и оценка его сложности
  • Примитивная сортировка и оценка её сложности
  • Сортировка слиянием
  • «Быстрая» сортировка, худший случай
  • Сортировка кучей
  • {i}

    • бинарный поиск строк в файле
    • сортировка файла слиянием

Python/Summer2017 (last edited 2021-04-27 20:23:39 by FrBrGeorge)