Проверочный тест к предыдущим лекциям

1. В кучке лежать N спичек. За ход можно брать a₁, a₂, ... a_k спичек. Играют двое. Проигрывает тот, кто не может сделать ход. Какая асимптотика у решения динамикой?
2. За какое время работает ретроанализ?
3. За какое время работает ретроанализ, если за один ход можно пройти вперед по двум ребрам графа?
4. Пусть у нас есть дерево игры. В нем N вершин. Если мы удачно применим AB-отсечение, на какое время работы следует рассчитывать?
5. В чем заключается метод Iterative Deepening?